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

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10 許鑫;范文慧;馮雅U

本文編號(hào)：2673561