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