網絡中供需匹配與多批次取送貨車輛路徑問題研究.pdf

1、本論文研究了供需匹配與多批次取送貨車輛路徑問題。在此問題中，客戶點之間的供需匹配關系事先未知；每個客戶點的取貨請求和送貨請求允許通過多次訪問該客戶點來分批次滿足；需做供需匹配決策和車輛路徑決策。此問題是經典車輛路徑問題的一種復雜衍生體，普遍存在于國際原油運輸、煙草制造行業(yè)中的生產原料調撥、零售行業(yè)中的商品庫存重新布局及共享單車系統(tǒng)中的自行車重新分配等網絡中?；诖藛栴}高度復雜且受到的關注較少，本文分別從模型建立、啟發(fā)式算法求解和精確算法

2、求解的角度對此問題進行深入研究。本文的主要研究成果呈現(xiàn)如下：
　?。?）本文所研究的問題包含了兩個相互影響的決策：供需匹配和車輛路徑。先建立一個混合整數(shù)線性規(guī)劃模型作為基礎模型。然后，通過消除兩個決策變量之間的耦合關系，提出一個新穎的單元化模型。緊接著，提出一系列多項式型有效不等式來加強單元化模型。實驗結果表明，單元化模型比基礎模型更容易求解，且所提出的有效不等式顯著地提高了單元化模型的性能。最后，驗證了所提出的模型和不等式對文獻

3、中相關問題的有效性。
　?。?）為快速求解現(xiàn)實中的較大規(guī)模的問題，基于所提出的單元化模型，先設計一個貪婪式算法來構建初始解。然后，基于優(yōu)化供需匹配決策和車輛路徑決策的思想，提出7個高效的鄰域結構。緊接著，提出一個禁忌搜索算法來改善初始解的質量。為驗證該算法的效果，借助于CPLEX設計求解問題下界的方法。實驗結果表明，本文所提出的禁忌搜索算法在較短時間內能夠對本文所研究的問題提供高質量的解。最后，驗證了本文所提出的啟發(fā)式算法求解文獻