【摘要】：已有同時(shí)集散貨物車輛路徑問題中一般假設(shè)客戶間的需求是相互獨(dú)立的,車輛從配送中心出發(fā),送貨至各客戶點(diǎn)并從客戶處集貨后返回配送中心；而在客戶取送貨需求存在成對(duì)關(guān)系的集散貨物車輛路徑問題中,客戶只有取貨或者只有送貨的需求。但是在大型制造企業(yè)的生產(chǎn)園區(qū)內(nèi),各工廠不同庫位之間原材料、半成品運(yùn)輸通常存在成對(duì)的取送貨關(guān)系,并且各個(gè)庫位既需要收取來自其他庫位或者倉庫的貨物,又需要向其他庫位提供半成品。本文針對(duì)此,提出了一種帶容量和最大工作時(shí)間約束的集散貨物車輛路徑問題(Capacitated Pickup and Delivery Problem with Max Duration, CPDPMD).在該問題中,各個(gè)客戶可以同時(shí)有取貨和送貨的需求,而且取貨點(diǎn)和送貨點(diǎn)之間有成對(duì)關(guān)系,目標(biāo)在于在滿足車輛載重約束和最大工作時(shí)間約束的情況下選擇運(yùn)輸成本最小的路徑。該問題可應(yīng)用于大型制造企業(yè)生產(chǎn)園區(qū)內(nèi)原材料、半成品運(yùn)輸。本文為CPDPMD問題建立了以行駛里程最小為目標(biāo)函數(shù)的數(shù)學(xué)模型,設(shè)計(jì)了改進(jìn)的分散搜索算法。并對(duì)該算法從編碼、多樣性產(chǎn)生方法、參考集生成及更新方法、局域改進(jìn)方法、子集產(chǎn)生方法和解組合方法六個(gè)方面進(jìn)行設(shè)計(jì)和改進(jìn)。首先基于貪婪插入算法設(shè)計(jì)多樣性產(chǎn)生方法；其次基于局部搜索的思想對(duì)多樣性解改進(jìn)得到質(zhì)量更高的解而后建立初始參考集,通過子集產(chǎn)生方法產(chǎn)生子集,有二元組、三元組、四元組和最好r個(gè)解；然后采用基于弧組合和掃描算法的解組合方法產(chǎn)生新解并更新參考集直至搜索結(jié)束最終得到優(yōu)化結(jié)果。為了驗(yàn)證本文算法的有效性,首先通過修改帶時(shí)間窗的VRPPD(Vehicle Routing Problems with Pickups and Deliveries)問題數(shù)據(jù)建立了CPDPMD問題的相關(guān)測(cè)試算例,然后進(jìn)行算法參數(shù)實(shí)驗(yàn),進(jìn)而比較了算法改進(jìn)前后的結(jié)果；為了進(jìn)一步評(píng)估該算法的有效性,將該算法運(yùn)用于求解CPDPMD問題的特例--單車輛的TSPPD (Traveling Salesman Problem with Pickup and Delivery)問題,并與精確算法比較,驗(yàn)證了該算法的有效性。此外,本文立足于企業(yè)的實(shí)際背景,將CPDPMD問題的模型應(yīng)用于A公司配送中心、各工廠庫位之間的原材料、半成品運(yùn)輸。通過對(duì)訂單進(jìn)行編碼,訂單需求劃分、裝卸貨時(shí)間計(jì)算、配送點(diǎn)之間里程與配送時(shí)間的確定等一系列步驟實(shí)現(xiàn)訂單標(biāo)準(zhǔn)化,使用設(shè)計(jì)好的算法求解標(biāo)準(zhǔn)化后的問題,得到園區(qū)內(nèi)各個(gè)班次車輛行駛的最優(yōu)路徑,證明了模型的有效性及實(shí)用性。
【圖文】：

本文研巧的ＣＰＤＰＭＤ問題，屬于客戶點(diǎn)之間的集散貨物車輛路徑問題，即取逡逑貨需求與送貨需求具有成對(duì)約束，但是與ＶＲＰＰＤ問題區(qū)別是：每個(gè)客戶可同時(shí)逡逑有取貨的需求和送貨的需求。如圖１－３所示，每個(gè)客戶都有兩種需求：取貨需求ｄｐ和逡逑送貨需求耍求如，如果客戶只有取貨需求，那么送貨需求扣＝0，反之則相反。若逡逑根據(jù)客戶點(diǎn)的需求類型將圖１－３所示問題中的客戶點(diǎn)吃分成取貨點(diǎn)集合和送貨點(diǎn)逡逑集合邋Ｋｄ，則邋＾）＝化，（２，【＇３邋山，＜５，邐＝邋｛／１，７２，７３，＿／４，７５，７６｝，由于邋ｉ＇２邋＝邐＝／３，＜１邋＝知逡逑之６邋＝八，故ｌ／ｐ邋ｎ邋單０。所Ｗ，ＣＰＤＰＭＤ問題可看作是ＶＲＰＢ問題和ＶＲＰＰＤ問逡逑題Ｗ的組合，更具一般性。逡逑

本文研巧的ＣＰＤＰＭＤ問題，屬于客戶點(diǎn)之間的集散貨物車輛路徑問題，即取逡逑貨需求與送貨需求具有成對(duì)約束，但是與ＶＲＰＰＤ問題區(qū)別是：每個(gè)客戶可同時(shí)逡逑有取貨的需求和送貨的需求。如圖１－３所示，每個(gè)客戶都有兩種需求：取貨需求ｄｐ和逡逑送貨需求耍求如，如果客戶只有取貨需求，那么送貨需求扣＝0，反之則相反。若逡逑根據(jù)客戶點(diǎn)的需求類型將圖１－３所示問題中的客戶點(diǎn)吃分成取貨點(diǎn)集合和送貨點(diǎn)逡逑集合邋Ｋｄ，則邋＾）＝化，（２，【＇３邋山，＜５，邐＝邋｛／１，７２，７３，＿／４，７５，７６｝，由于邋ｉ＇２邋＝邐＝／３，＜１邋＝知逡逑之６邋＝八，故ｌ／ｐ邋ｎ邋單０。所Ｗ，，ＣＰＤＰＭＤ問題可看作是ＶＲＰＢ問題和ＶＲＰＰＤ問逡逑題Ｗ的組合，更具一般性。逡逑
【學(xué)位授予單位】：南京農(nóng)業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 陸琳;蔡紹洪;;一類隨機(jī)顧客車輛路徑問題及其算法[J];南京航空航天大學(xué)學(xué)報(bào);2010年04期

2 陳森;姜江;陳英武;沈永平;;一類非確定性車輛路徑問題模型及其算法設(shè)計(jì)[J];計(jì)算機(jī)工程;2011年14期

3 楊亞萍;;基于車輛路徑問題的建模及算法的研究[J];電腦開發(fā)與應(yīng)用;2012年12期

4 駱正山,王小完;基于模糊條件下車輛路徑問題的研究[J];微電子學(xué)與計(jì)算機(jī);2005年03期

5 陳寶文;宋申民;陳興林;;模糊需求車輛路徑問題及其啟發(fā)式蟻群算法[J];計(jì)算機(jī)應(yīng)用;2006年11期

6 蔣忠中;汪定偉;;車輛路徑問題的捕食搜索算法研究[J];計(jì)算機(jī)集成制造系統(tǒng);2006年11期

7 朱才華;何渝;;帶時(shí)間窗和貨物權(quán)重的車輛路徑問題的研究[J];北京工商大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年04期

8 李三彬;柴玉梅;王黎明;;需求可拆分的開放式車輛路徑問題研究[J];計(jì)算機(jī)工程;2011年06期

9 孫國華;;帶軟時(shí)間窗的開放式滿載車輛路徑問題研究[J];計(jì)算機(jī)工程與應(yīng)用;2011年17期

10 尹傳忠;卜雷;蒲云;趙宜;;帶回送和時(shí)間窗的車輛路徑問題的模型及算法[J];西南交通大學(xué)學(xué)報(bào);2006年03期

相關(guān)會(huì)議論文 前10條

1 符卓;陳斯衛(wèi);;車輛路徑問題的研究現(xiàn)狀與發(fā)展趨勢(shì)[A];中國運(yùn)籌學(xué)會(huì)第七屆學(xué)術(shù)交流會(huì)論文集（下卷）[C];2004年

2 楊世堅(jiān);陳韜;;隨機(jī)車輛路徑問題研究綜述[A];中國系統(tǒng)工程學(xué)會(huì)決策科學(xué)專業(yè)委員會(huì)第六屆學(xué)術(shù)年會(huì)論文集[C];2005年

3 李桂平;陳楠;;多中心車輛路徑問題的解決思路[A];中國地理信息系統(tǒng)協(xié)會(huì)第四次會(huì)員代表大會(huì)暨第十一屆年會(huì)論文集[C];2007年

4 李大衛(wèi);王夢(mèng)光;;廣義車輛路徑問題——模型及算法[A];1997中國控制與決策學(xué)術(shù)年會(huì)論文集[C];1997年

5 符卓;聶靖;;開放式車輛路徑問題及其若干研究進(jìn)展[A];中國運(yùn)籌學(xué)會(huì)第八屆學(xué)術(shù)交流會(huì)論文集[C];2006年

6 陳寶文;宋申民;陳興林;單志眾;;應(yīng)用于車輛路徑問題的多蟻群算法[A];第25屆中國控制會(huì)議論文集（下冊(cè)）[C];2006年

7 戎麗霞;;模糊需求條件下的多車場(chǎng)車輛路徑問題[A];第三屆中國智能計(jì)算大會(huì)論文集[C];2009年

8 張鳳姣;張興芳;;基于不確定理論的車輛路徑問題[A];第九屆中國不確定系統(tǒng)年會(huì)、第五屆中國智能計(jì)算大會(huì)、第十三屆中國青年信息與管理學(xué)者大會(huì)論文集[C];2011年

9 肖雁;符卓;李育安;;帶軟時(shí)間窗的車輛路徑問題及其應(yīng)用前景探討[A];中國運(yùn)籌學(xué)會(huì)第六屆學(xué)術(shù)交流會(huì)論文集（下卷）[C];2000年

10 許鑫;范文慧;馮雅U

本文編號(hào)：2673561