多點(diǎn)互運(yùn)的車輛路徑問題研究.pdf

1、本論文對傳統(tǒng)的VRP問題進(jìn)行拓展，供應(yīng)點(diǎn)和需求點(diǎn)之間的匹配及其運(yùn)量未預(yù)先給定，而是與路徑一樣作為決策變量。此類VRP問題在有原材料和產(chǎn)品互運(yùn)的多點(diǎn)生產(chǎn)系統(tǒng)中比較常見，可定義為多點(diǎn)互運(yùn)車輛路徑問題。根據(jù)產(chǎn)品種類數(shù)量多少，可進(jìn)一步將此問題分為復(fù)雜度各異的兩個子問題，本文為每個子問題建立相應(yīng)的數(shù)學(xué)模型，并提出求解算法。具體而言，本文主要的創(chuàng)新性工作總結(jié)如下：
　　一是建立單產(chǎn)品模式下的多點(diǎn)互運(yùn)車輛路徑問題數(shù)學(xué)模型。在該模型中不僅考慮車輛

2、運(yùn)輸成本，同時也考慮產(chǎn)品變動生產(chǎn)成本。該問題是NP難題，優(yōu)化軟件CPLEX只能求解小規(guī)模的此類問題。針對該模型，提出了快速有效的禁忌搜索算法，通過拉格朗日松弛算法和改進(jìn)的Dijkstra算法求得該問題解的下界。最后采用隨機(jī)生成的算例測試，確認(rèn)拉格朗日松弛算法得出的下界是緊的，且禁忌搜索算法可以為大規(guī)模的算例求得滿意的結(jié)果。
　　二是建立多產(chǎn)品模式下的多點(diǎn)互運(yùn)車輛路徑問題數(shù)學(xué)模型。在該模型中，允許車輛多次對客戶開展取貨或送貨服務(wù)，而

3、送貨或取貨的地點(diǎn)和產(chǎn)品數(shù)量是未預(yù)知的。針對該模型，首先提出易于操作的啟發(fā)式方法快速獲得可行的初始方案；然后基于變鄰域搜索算法提出6類鄰域結(jié)構(gòu)，改進(jìn)和優(yōu)化初始解；最后，算例測試結(jié)果驗(yàn)證了變鄰域搜索算法能在合理的運(yùn)算時間內(nèi)獲得最優(yōu)或近似最優(yōu)的解決方案。
　　三是建立基于產(chǎn)品單元化的多點(diǎn)互運(yùn)車輛路徑問題數(shù)學(xué)模型。采用單元化供需產(chǎn)品數(shù)量方法消除供需匹配和車輛路徑的耦合關(guān)系。針對該模型，以命題形式分析了8個最優(yōu)解特性，并提出8類有效不等式。

4、最后，CPLEX基于分支定界方法計算了Hennig et al.（2012b）中同等規(guī)模算例，測算結(jié)果驗(yàn)證了產(chǎn)品單元化方法以及這些特性和有效不等式能有助于更快求解問題。
　　四是結(jié)合產(chǎn)品單元化方法，提出基于變鄰域搜索的啟發(fā)式算法求解更大規(guī)模問題。為了獲得更好的解，在進(jìn)行擾動操作后，采用基于改進(jìn)最短路徑法的局域搜索方法進(jìn)一步改善每個鄰域解。在線路延伸計算時，充分利用所得的最優(yōu)解性質(zhì)來減少節(jié)點(diǎn)數(shù)，并在節(jié)點(diǎn)標(biāo)簽更替控制條件中增加車容積和