本文關(guān)鍵詞：求解大規(guī)模VCVRP問題的快速動態(tài)規(guī)劃算法

  更多相關(guān)文章： 車輛路徑問題 VCVRP問題 動態(tài)規(guī)劃 組合優(yōu)化 快速算法 啟發(fā)式算法

【摘要】：車輛路徑問題是一類典型的組合優(yōu)化問題,大部分研究都只考慮車輛能力固定的情形,實際中受貨物形狀特性及客戶需求變化,車輛的能力是受限變化的,針對能力受限變化的車輛路徑問題(varied capacitated vehicle routing problem,VCVRP),基于動態(tài)規(guī)劃理論,提出一種求解大規(guī)模VCVRP問題的快速動態(tài)規(guī)劃算法.該算法以傳統(tǒng)的最佳適應(yīng)降序算法(best fit decreasing,BFD)和最小生成樹(minimum spanning tree,MST)算法為基礎(chǔ),引入K步回溯,短途優(yōu)先原則,實現(xiàn)了VCVRP中的貨物裝箱問題和路由選擇問題的近似解耦.同時給出了該算法的優(yōu)化目標(biāo)車輛旅程的理論上界,短途優(yōu)先原則的局部最小的理論分析與證明.最后以乘用車物流運輸案例為背景,給出了計算實例,并從算法參數(shù)與算例規(guī)模多個角度進(jìn)行求解質(zhì)量與算法性能的分析.
【作者單位】： 國防科學(xué)技術(shù)大學(xué)信息系統(tǒng)與管理學(xué)院國防采辦與體系工程管理教研室;國防科學(xué)技術(shù)大學(xué)信息系統(tǒng)與管理學(xué)院C4ISR國防科技重點實驗室;
【關(guān)鍵詞】： 車輛路徑問題 VCVRP問題 動態(tài)規(guī)劃 組合優(yōu)化 快速算法 啟發(fā)式算法
【基金】：國家自然科學(xué)基金(71201168)~~
【分類號】：O221.3
【正文快照】： (1.國防科學(xué)技術(shù)大學(xué)信息系統(tǒng)與管理學(xué)院國防采辦與體系工程管理教研室,長沙410073;2.國防科學(xué)技術(shù)大學(xué)信息系統(tǒng)與管理學(xué)院C4ISR國防科技重點實驗室,長沙410073)Fast dynamic programming algorithm for the large scale VCVRPproblemZHANG Pengle1,XIAO Kaiming2,FU Chunxiao

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 李菲;肖洪祥;;基于神經(jīng)動態(tài)規(guī)劃算法的最優(yōu)路徑選擇[J];桂林工學(xué)院學(xué)報;2009年01期

2 羅宗俊;;高維0-1瓶頸問題的動態(tài)規(guī)劃算法[J];數(shù)值計算與計算機應(yīng)用;2013年01期

3 周靜;;運用動態(tài)規(guī)劃算法解決最大價值路線圖問題[J];硅谷;2013年15期

4 李樂園;林詒勛;;電力網(wǎng)調(diào)度時間表問題的動態(tài)規(guī)劃算法[J];河南科學(xué);1988年02期

5 徐緒松;工序問題的動態(tài)規(guī)劃算法[J];武漢大學(xué)學(xué)報(自然科學(xué)版);1994年05期

6 趙鈺;徐濤;陳紅軍;;炮兵營火力分配的二階動態(tài)規(guī)劃算法[J];四川兵工學(xué)報;2009年09期

7 陳捷;;基于動態(tài)規(guī)劃算法的最值問題分析[J];電腦與信息技術(shù);2013年06期

8 廖慧芬;邵小兵;;動態(tài)規(guī)劃算法的原理及應(yīng)用[J];中國科技信息;2005年21期

9 劉瑩;;改進(jìn)的動態(tài)規(guī)劃算法在最優(yōu)航線選擇中的應(yīng)用[J];邵陽學(xué)院學(xué)報(自然科學(xué)版);2007年01期

10 王雪瑞;秦勤;李建;;Possible Winner問題參數(shù)算法研究及核心化[J];湘潭大學(xué)自然科學(xué)學(xué)報;2012年04期

中國重要會議論文全文數(shù)據(jù)庫 前2條

1 顧文彬;高梅國;;基于改進(jìn)動態(tài)規(guī)劃算法的雷達(dá)微弱目標(biāo)檢測[A];中國航空學(xué)會信號與信息處理專業(yè)全國第八屆學(xué)術(shù)會議論文集[C];2004年

2 唐玲娜;唐雪飛;葉昌偉;;動態(tài)規(guī)劃算法正序?qū)崿F(xiàn)及其改進(jìn)[A];2008'中國信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（二）[C];2008年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 PALADIN;動態(tài)規(guī)劃算法設(shè)計[N];電腦報;2003年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 許虎;基于動態(tài)規(guī)劃算法的網(wǎng)癮戒除輔助活動規(guī)劃系統(tǒng)的研究與實現(xiàn)[D];東北大學(xué);2013年

2 劉昭;基于DP算法插電式柴電混合動力汽車控制策略研究[D];重慶交通大學(xué);2015年

3 李強;動態(tài)規(guī)劃算法時間效率優(yōu)化策略研究[D];中南民族大學(xué);2015年

4 丁偉軍;結(jié)合近似動態(tài)規(guī)劃算法的串行生產(chǎn)系統(tǒng)風(fēng)險管理研究[D];清華大學(xué);2011年

5 張玉斌;迭代動態(tài)規(guī)劃算法及并行化研究[D];中國石油大學(xué);2008年

6 吳濤;動態(tài)規(guī)劃算法應(yīng)用及其在時間效率上的優(yōu)化[D];南京理工大學(xué);2008年

7 李前興;工業(yè)過程迭代動態(tài)規(guī)劃算法研究[D];浙江大學(xué);2011年

8 農(nóng)健恒;同尺寸物品裝箱的動態(tài)規(guī)劃算法[D];廣西大學(xué);2014年

9 杜君;MPP環(huán)境中面向動態(tài)規(guī)劃算法的混合并行系統(tǒng)的研究[D];天津大學(xué);2014年

10 楊再新;高頻雷達(dá)運動目標(biāo)多幀檢測技術(shù)研究[D];哈爾濱工業(yè)大學(xué);2014年

，

本文編號：625134