配送企業(yè)車輛路徑問題模型與算法研究.pdf

1、隨著市場經(jīng)濟(jì)的發(fā)展，配送對(duì)經(jīng)濟(jì)活動(dòng)的影響越來越明顯。車輛路徑問題(VRP)一直是配送活動(dòng)優(yōu)化的重要內(nèi)容，是最大限度的降低配送成本、提高顧客滿意度的保障。本文在全面綜述了國內(nèi)外車輛路徑問題研究現(xiàn)狀的基礎(chǔ)上，主要針對(duì)配送企業(yè)的實(shí)際需求，研究了目前最常見、配送發(fā)展迫切需要解決的三種車輛路徑問題，并給出了智能啟發(fā)式求解算法。主要貢獻(xiàn)如下:
　　1.考慮同時(shí)取送貨的車輛路徑問題(VRPSPD)
　　由于配送中顧客有送貨和取貨需求，企業(yè)

2、需要構(gòu)建產(chǎn)品正向配送和逆向回收相整合的配送系統(tǒng)。因此，本文設(shè)計(jì)了配送企業(yè)在考慮顧客有同時(shí)取送貨需求時(shí)的車輛路徑問題，并提出一種基于禁忌規(guī)則的模擬退火算法(HSA)求解。HSA算法借鑒禁忌搜索算法(TS)的思想，在退火過程中引入禁忌表，一定程度上避免曾經(jīng)訪問過的解，并加速了搜索過程。HSA算法首先使用剩余承載力和徑向附加費(fèi)(RCRS)算法求得一個(gè)可行初始解，然后使用4種鄰域搜索方法在模擬退火算法(SA)框架下對(duì)初始解進(jìn)行優(yōu)化。
　　

3、為了檢驗(yàn)HSA算法的有效性，采用國際上通用的Dethloff數(shù)據(jù)集(40個(gè)小型顧客規(guī)模算例)、Salhi和Nagy數(shù)據(jù)集（14個(gè)中型顧客規(guī)模算例）、Montane和Galvao數(shù)據(jù)集（18個(gè)大型顧客規(guī)模算例），優(yōu)化目標(biāo)是最小化車輛總行駛距離(TD)。因此，共使用了72個(gè)測試算例，顧客數(shù)從50到400不等。與文獻(xiàn)中已知算法的計(jì)算結(jié)果比較，從解的質(zhì)量角度分析，HSA算法是一種有效的算法，可以找到近似最優(yōu)的車輛配送路徑;從求解時(shí)間角度分析，由

4、于求解時(shí)計(jì)算機(jī)的配置不同，雖然慢于其它算法，但求解時(shí)間是可接受的。
　　2.考慮帶時(shí)間窗和同時(shí)取送貨的車輛路徑問題（VRPSPDTW）
　　除了顧客有同時(shí)取貨和送貨的需求外，配送中顧客往往還有具體的服務(wù)時(shí)間窗限制，為了提高服務(wù)質(zhì)量，企業(yè)往往會(huì)考慮顧客的時(shí)間窗需求。因此，構(gòu)建基于時(shí)間窗和同時(shí)取送貨的車輛路徑問題（VRPSPDTW）。提出一種并行模擬退火算法(p-SA)求解。p-SA算法利用多馬爾科夫鏈(MMC)方法，整合同步和

5、異步MMC策略，在主從模式下將傳統(tǒng)的SA算法并行化。
　　本文采用Wang和Chen數(shù)據(jù)集(65個(gè)小型和中型顧客規(guī)模的算例)，并將計(jì)算結(jié)果與GA算法的結(jié)果進(jìn)行比較。測試結(jié)果顯示提出的p-SA算法可以有效的求解該問題。并且，構(gòu)造了30個(gè)顧客規(guī)模為200、400、600、800和1000的大型顧客規(guī)模的算例作為新算例。目前國際上尚無可用于計(jì)算大型顧客規(guī)模的算例，p-SA算法的結(jié)果可為后續(xù)學(xué)者通過大型算例測試算法有效性提供參考。

6、　　3.考慮配送網(wǎng)點(diǎn)優(yōu)化的車輛路徑問題（2E-LRPSPDTW）
　　隨著城市中交通擁堵的日益加重，多數(shù)大中城市對(duì)廂式貨車進(jìn)入城區(qū)采取了一系列的限制措施。因此，對(duì)于配送企業(yè)無法通過廂式貨車實(shí)現(xiàn)從中央配送中心到顧客的直接配送，需要在設(shè)施點(diǎn)與需求點(diǎn)之間建立中轉(zhuǎn)站，通過小貨車將從中央配送中心運(yùn)來的貨物，在區(qū)域配送網(wǎng)點(diǎn)通過電動(dòng)三輪車進(jìn)行中轉(zhuǎn)，如此形成中央配送中心—區(qū)域配送網(wǎng)點(diǎn)、區(qū)域配送網(wǎng)點(diǎn)—顧客的兩級(jí)配送系統(tǒng)?？紤]配送網(wǎng)點(diǎn)選址，優(yōu)化車輛配

7、送路徑，這是一個(gè)集成車輛選徑和網(wǎng)點(diǎn)選址的問題(稱為選址—路徑問題，LRP)。本文構(gòu)建帶時(shí)間窗和同時(shí)取送貨的兩級(jí)選址—路徑問題（2E-LRPSPDTW），提出并行模擬退火路徑重連算法(p-SA-PR)求解。常規(guī)的求解LRP問題的方法是把選址問題和車輛路徑問題作為兩個(gè)獨(dú)立的問題進(jìn)行兩階段求解，這種方法沒有考慮設(shè)施選址和車輛路徑兩個(gè)問題之間的影響和制約關(guān)系。p-SA-PR算法將LRP的解看做一個(gè)整體，通過對(duì)LRP的解的結(jié)構(gòu)進(jìn)行分析，重新進(jìn)行設(shè)

8、計(jì)和改進(jìn)。
　　為了檢驗(yàn)提出的p-SA-PR算法的有效性，采用國際上通用的Nguyen數(shù)據(jù)集(24個(gè)算例)、Prodhon數(shù)據(jù)集(30個(gè)算例)、Sterle數(shù)據(jù)集（30個(gè)算例）。共使用了84個(gè)測試算例，顧客規(guī)模從8到200不等。與文獻(xiàn)中已知算法的計(jì)算結(jié)果比較可知，p-SA-pR算法是一種有效的算法，可以在快速的時(shí)間內(nèi)求解2E-LRPSPDTW問題。
　　4.調(diào)研了CSYB配送企業(yè)，優(yōu)化了CSYB的車輛配送路徑。
　　該