題-1_100_100.jpg)
基本信息
- 項(xiàng)目名稱：
- 網(wǎng)購(gòu)物流快速配送研究--基于最小生成樹(shù)的動(dòng)態(tài)規(guī)劃最優(yōu)路徑選擇
- 來(lái)源：
- 第十二屆“挑戰(zhàn)杯”省賽作品
- 小類：
- 數(shù)理
- 簡(jiǎn)介：
- 本文研究了貨運(yùn)配送中的最優(yōu)路線選擇問(wèn)題，為了綜合考慮到配送中航行路程、停留時(shí)間等影響因素，利用動(dòng)態(tài)規(guī)劃建立算法選擇最優(yōu)配送路線。其中我們制定的路線選擇指數(shù)和以最小生成樹(shù)的葉子結(jié)點(diǎn)劃分階段的基本思路是本文的創(chuàng)新之處，同時(shí)編寫出上述模型的c語(yǔ)言程序，進(jìn)一步對(duì)實(shí)際貨運(yùn)配送問(wèn)題提供可推廣的基礎(chǔ)。本文所研究的貨運(yùn)配送路線的算法思路有一定的可推廣性，在解決貨運(yùn)配送這一熱點(diǎn)問(wèn)題有切實(shí)、可行的研究?jī)r(jià)值。
- 詳細(xì)介紹：
- 貨物配送路徑優(yōu)化問(wèn)題是一個(gè)NP-hard問(wèn)題，隨著送貨地點(diǎn)增加，可選的配送路徑數(shù)量將急劇增長(zhǎng)。為了提高貨物運(yùn)送效率，本文在最小生成樹(shù)的研究基礎(chǔ)上，用動(dòng)態(tài)規(guī)劃的方法，在運(yùn)輸路徑盡可能短的情況下，綜合考慮?？亢椭貜?fù)?？繒r(shí)間對(duì)結(jié)果的影響，研究耗時(shí)最短的送貨路徑。 本文通過(guò)編程求解最優(yōu)路徑，脫離人工的手動(dòng)優(yōu)化，提高了解決問(wèn)題的嚴(yán)謹(jǐn)性和科學(xué)性。另外，為了綜合考慮運(yùn)輸工具的路程消耗和停留消耗，本文制定了路徑選擇指數(shù)α，通過(guò)比較α的大小即可選擇出最優(yōu)路線。本文以全國(guó)20個(gè)省市的運(yùn)輸為實(shí)例，在具體問(wèn)題中探討該方法的可行性。實(shí)驗(yàn)結(jié)果表明，本文研究的方法對(duì)于解決貨物配送路徑優(yōu)化問(wèn)題是有效的，具有較大的應(yīng)用價(jià)值。 最后，根據(jù)實(shí)際情況，對(duì)方法思路進(jìn)行拓展，解決了在各地區(qū)需求量不同時(shí)的路線優(yōu)化問(wèn)題。
作品專業(yè)信息
撰寫目的和基本思路
- 撰寫目的：網(wǎng)上購(gòu)物成為了現(xiàn)代購(gòu)物的一種重要形式，快遞公司合理的、快速的選擇出最優(yōu)運(yùn)輸路線，提高物流配送的效率是一個(gè)亟需解決的重要問(wèn)題。本文提出了快速配送路線選擇算法，并加以推廣。 基本思路：在最小生成樹(shù)的基礎(chǔ)上，建立最優(yōu)路徑選擇的算法，并編制了可推廣應(yīng)用的C語(yǔ)言程序，實(shí)現(xiàn)貨物配送路線的優(yōu)化、提高配送效率。
科學(xué)性、先進(jìn)性及獨(dú)特之處
- 論文在最小生成樹(shù)的基礎(chǔ)上選擇運(yùn)輸路線，刪除在動(dòng)態(tài)規(guī)劃選擇路徑時(shí)可能重復(fù)經(jīng)過(guò)或造成環(huán)路的路徑，結(jié)合制定的指數(shù)選擇路線，減少運(yùn)輸所需時(shí)間的消耗。本文獨(dú)特之處是建立了路線選擇指數(shù)，分析其科學(xué)性與合理性，使用C程序求解方便快捷，論文力求從運(yùn)輸所需時(shí)間最少的角度選擇最優(yōu)運(yùn)輸方案，以滿足公司和消費(fèi)者的需求。并論證了對(duì)從經(jīng)濟(jì)角度也為很好方案。
應(yīng)用價(jià)值和現(xiàn)實(shí)意義
- 動(dòng)態(tài)規(guī)劃是解決最優(yōu)問(wèn)題的一種普遍性方法，具有較強(qiáng)的推廣性。本作品結(jié)合最小生成樹(shù)和路線選擇指數(shù)的創(chuàng)新性運(yùn)用，可以廣泛應(yīng)用于物流快遞、旅游路徑選擇等實(shí)際問(wèn)題中。 作品利用最小生成樹(shù)特性為切入點(diǎn)，建立的相關(guān)數(shù)學(xué)模型，可用于快遞公司高效、合理地選擇最優(yōu)運(yùn)輸路徑，有效地縮短快遞運(yùn)輸時(shí)間，極大地推動(dòng)科學(xué)化設(shè)計(jì)最優(yōu)路徑技術(shù)的發(fā)展，具有重要的學(xué)術(shù)價(jià)值，可以產(chǎn)生重大社會(huì)效益和經(jīng)濟(jì)效益。
學(xué)術(shù)論文摘要
- 隨著經(jīng)濟(jì)社會(huì)發(fā)展，人們的消費(fèi)觀念、購(gòu)物方式發(fā)生了很大改變。相比于傳統(tǒng)的商店實(shí)體銷售方式，近年來(lái)剛剛興起并迅速占領(lǐng)市場(chǎng)的網(wǎng)購(gòu)具有貨物齊全、物美價(jià)廉等諸多優(yōu)勢(shì)?，F(xiàn)今，網(wǎng)購(gòu)的人越來(lái)越多、商品需求量日益增加，消費(fèi)者對(duì)貨物運(yùn)送效率的要求也隨之提高。物流公司要在市場(chǎng)競(jìng)爭(zhēng)中脫穎而出，合理選擇、優(yōu)化配送路線方案、提高配送效率就顯得至關(guān)重要。 貨物配送路徑優(yōu)化問(wèn)題是一個(gè)NP-hard問(wèn)題，隨著送貨地點(diǎn)增加，可選的配送路徑數(shù)量將急劇增長(zhǎng)。為了提高貨物運(yùn)送效率，本文在最小生成樹(shù)的研究基礎(chǔ)上，有選擇地減少了參與考慮的可行路線方案，用動(dòng)態(tài)規(guī)劃的方法研究耗時(shí)最短的送貨路徑。 本文通過(guò)編程求解最優(yōu)路徑，脫離人工的手動(dòng)優(yōu)化，提高了解決問(wèn)題的嚴(yán)謹(jǐn)性和科學(xué)性。另外，為了綜合考慮運(yùn)輸工具的路程消耗和停留消耗，本文制定了路徑選擇指數(shù)α，通過(guò)比較α的大小即可選擇出最優(yōu)路線。本文以全國(guó)20個(gè)省市的運(yùn)輸為實(shí)例，在具體問(wèn)題中探討該方法的可行性。實(shí)驗(yàn)結(jié)果表明，本文研究的方法對(duì)于解決貨物配送路徑優(yōu)化問(wèn)題是有效的，具有較大的應(yīng)用價(jià)值。 最后，根據(jù)實(shí)際情況，對(duì)方法思路進(jìn)行拓展，解決了在各地區(qū)需求量不同時(shí)的路線優(yōu)化問(wèn)題。
獲獎(jiǎng)情況
- 無(wú)
鑒定結(jié)果
- 動(dòng)態(tài)規(guī)劃解決最優(yōu)路徑選擇問(wèn)題已見(jiàn)諸多篇文獻(xiàn)報(bào)道，但結(jié)合最小生成樹(shù)特性及綜合考慮路線消耗和停留消耗而制定路線選擇指數(shù)來(lái)解決路徑選擇問(wèn)題的方法未見(jiàn)有。
參考文獻(xiàn)
- [1] 陳思勇，供應(yīng)商選擇與貨物配送路徑規(guī)劃研究及其應(yīng)用[D]， 2009 - 北京交通大學(xué)：計(jì)算機(jī)科學(xué)與技術(shù) [2] 范恩海.用于配送調(diào)度的節(jié)約法德又一種模型[J].太原理工大學(xué)學(xué)報(bào),1999,3 [3] 李嘉，王夢(mèng)光，唐立新等．一類特殊車輛路徑問(wèn)題(VRP)[J]．東北大學(xué)學(xué)報(bào)(自然科學(xué)版)，2001，6 [4] 程世東,劉小明,王兆賡. 物流配送車輛調(diào)度研究的回顧與展望 [J]交通運(yùn)輸工程與信息學(xué)報(bào) , 2004,(03) . [5] 田青，繆立新，鄭力. 基于運(yùn)輸規(guī)劃和組合GA的基本物流網(wǎng)絡(luò)設(shè)計(jì).[J] 《清華大學(xué)學(xué)報(bào)（自然科學(xué)版）》
同類課題研究水平概述
- 隨著互聯(lián)網(wǎng)在中國(guó)的進(jìn)一步普及應(yīng)用，網(wǎng)上購(gòu)物逐漸融入人們的消費(fèi)生活，網(wǎng)購(gòu)的物流配送問(wèn)題也在持續(xù)地改進(jìn)和優(yōu)化。物流公司要在市場(chǎng)競(jìng)爭(zhēng)中脫穎而出，合理組織貨物配送、優(yōu)化配送路線方案、提高配送效率就顯得至關(guān)重要。 國(guó)外將優(yōu)化配送問(wèn)題歸結(jié)為VSP問(wèn)題，最早由Dantzig和Ramser在1959年提出。 VSP是一個(gè)NP-hard問(wèn)題，隨著顧客數(shù)量的增加，可選的配送路徑數(shù)量將呈指數(shù)速度增長(zhǎng)，所以學(xué)者們也不斷地創(chuàng)新，提出新的方法，目前主要的研究方法有： 1、運(yùn)籌方法和優(yōu)化方法。運(yùn)用線性規(guī)劃、非線性規(guī)劃數(shù)學(xué)技術(shù)，以便求得最優(yōu)決策。Dantzig和Ramser最初用整數(shù)規(guī)劃模型來(lái)處理一些規(guī)模較小的問(wèn)題，大約10到20個(gè)顧客的問(wèn)題。 2、啟發(fā)式方法。指通過(guò)經(jīng)驗(yàn)法則來(lái)求解運(yùn)輸過(guò)程滿意解的數(shù)學(xué)方法。最具代表性的就是由Clarck和Wright提出的節(jié)約法以及Gillett和Miller所提出的掃描算法，西南交大的李軍針對(duì)有時(shí)間窗的車輛調(diào)度安排問(wèn)題提出了一種利用節(jié)約法的啟發(fā)式算法。 3、模擬方法。利用數(shù)學(xué)公式、邏輯表達(dá)式、圖表、坐標(biāo)圖形等抽象概念表示實(shí)際運(yùn)輸系統(tǒng)內(nèi)部狀態(tài)和輸入輸出的關(guān)系，以便通過(guò)計(jì)算機(jī)模型進(jìn)行試驗(yàn)，進(jìn)而取得改善運(yùn)輸系統(tǒng)或設(shè)計(jì)新運(yùn)輸系統(tǒng)所需的信息。 4、交互式優(yōu)化法。這是一種通用方法。在這種方法中，把人的知識(shí)、經(jīng)驗(yàn)結(jié)合到問(wèn)題的求解過(guò)程中去。這種方法的早期雛形是由Krolak,Felts和Marble以及Nelson等人提出的。 我國(guó)在對(duì)車輛路線問(wèn)題的研究起步較晚，與國(guó)外的研究水平還有差距。我國(guó)大部分的研究采用的是遺傳算法。 目前，除了對(duì)VSP問(wèn)題研究方法的繼續(xù)探索外， VSP問(wèn)題的形式已有很大的發(fā)展，從最初的汽車運(yùn)輸領(lǐng)域發(fā)展至今，在水運(yùn)、航空、通訊、電力、計(jì)算機(jī)等領(lǐng)域也有一定的應(yīng)用，其算法對(duì)于輪船公司運(yùn)送貨物經(jīng)過(guò)港口、貨物安排的優(yōu)化設(shè)計(jì)、交通車線路安排、生產(chǎn)系統(tǒng)中的計(jì)劃與控制等多種組合優(yōu)化問(wèn)題同樣適用。 本研究利用最小生成樹(shù)的特性劃分階段、選擇性的增減路徑，以及綜合考慮路線消耗和停留消耗制定了路線選擇指數(shù)，有效的減少了參與考慮的可選配送路徑方案的數(shù)量，合理地選擇出了最優(yōu)運(yùn)輸路徑。極大地推動(dòng)科學(xué)化設(shè)計(jì)最優(yōu)路徑技術(shù)的發(fā)展，具有重要的學(xué)術(shù)價(jià)值，可以產(chǎn)生重大社會(huì)效益和經(jīng)濟(jì)效益。
