前言

車輛路徑問題（Vehicle Routing Problem，VRP）最早由Dantzig和Ramser于1959年提出，它是指一定數(shù)量的客戶各自有不同數(shù)量的貨物需求，配送中心向客戶提供貨物，由車隊負責分送貨物，規(guī)劃適當?shù)男熊嚶肪€，目標是使客戶的需求得到滿足，并能在一定的約束下，達到路程最短、成本最少、耗費時間最少等目的。

取送貨車輛路徑問題是對傳統(tǒng)車輛路徑問題的擴展，可簡要描述如下：在某個供求系統(tǒng)中，有若干個取貨節(jié)點和送貨節(jié)點（有些節(jié)點既是取貨節(jié)點也是送貨節(jié)點），在貨物取送量、最大車載量、最長行駛時間等約束條件下，合理安排客戶的訪問次序和貨物取送量，把客戶需求的貨物從取貨節(jié)點運送至送貨節(jié)點，并實現(xiàn)所需車輛數(shù)最少、行駛距離最短、總運輸成本最少等優(yōu)化目標。

本書研究了供需未匹配多商品取送貨車輛路徑問題。在此問題中，客戶點之間的供需匹配關系事先未知；每個客戶點的取貨需求和送貨需求必須被滿足；需要做供需匹配決策和車輛路徑?jīng)Q策。本書在供需匹配關系未知的情況下，研究了在單次訪問和多次訪問情況下供需未匹配的多商品取送貨車輛路徑問題。

本書所研究的問題是經(jīng)典的車輛路徑問題的一種復雜衍生體，普遍存在于國際原油運輸、煙草制造行業(yè)中生產(chǎn)原料調(diào)撥、零售行業(yè)的商品庫存重新布局及共享單車系統(tǒng)的自行車重新分配等網(wǎng)絡中。問題高度復雜且受到的關注較少，因此本書分別從模型構(gòu)建、問題特性分析、啟發(fā)式算法設計和精確算法設計、數(shù)值測試的角度對所研究問題進行深入研究。本書的主要研究成果如下：

（1）多次訪問條件下的供需未匹配多商品取送貨車輛路徑問題模型構(gòu)建與問題特性分析方面：首先，借鑒相關文獻的研究成果，建立一個混合整數(shù)線性規(guī)劃模型作為基礎模型。其次，為消除決策變量之間的耦合關系，提出了一個單元化思想以拆分頂點，進而建立了一個單元化數(shù)學模型。再次，提出了6類多項式型有效不等式來加強單元化模型構(gòu)建。最后，基于數(shù)值實驗驗證了單元化模型相對基礎模型具有明顯的優(yōu)勢（需要較少的決策變量），以及本書提出的有效不等式可顯著提高模型的性能。

（2）多次訪問條件下的供需未匹配多商品取送貨車輛路徑問題啟發(fā)式算法設計方面：為快速求解現(xiàn)實中常見的較大規(guī)模的問題，基于本書提出的模型，首先，設計一個貪婪式算法來構(gòu)建初始解。其次，基于優(yōu)化供需匹配決策和車輛路徑?jīng)Q策的思想，提出高效的鄰域結(jié)構(gòu)。再次，提出一個禁忌搜索算法來改善初始解的質(zhì)量。最后，為驗證該算法的效果，借助CPLEX[1]設計求解問題下界的方法。實驗結(jié)果表明，本書提出的禁忌搜索算法在較短時間內(nèi)能夠?qū)λ芯康膯栴}提供最優(yōu)或近似最優(yōu)解。

（3）多次訪問條件下的供需未匹配多商品取送貨車輛路徑問題精確算法設計方面：為針對現(xiàn)實中中小規(guī)模的問題求出最優(yōu)解，首先，基于單元化模型具有的優(yōu)勢，建立一個更簡便的數(shù)學模型。其次，提出2類新的多項式型有效不等式和6類指數(shù)型有效不等式來加強模型。再次，針對每類指數(shù)型有效不等式設計了相應的分離算法。最后，基于初始上界選取、預處理操作、分支策略和分離算法調(diào)用策略的深入討論，設計了一個分支切割算法。實驗結(jié)果表明，本書設計的分支切割算法在規(guī)定時間內(nèi)能夠求解9個客戶和5種商品的算例，且在求解規(guī)模、求解時間和上下界值方面相對優(yōu)化軟件CPLEX均具有明顯優(yōu)勢。

（4）單次訪問條件下的供需未匹配多商品取送貨車輛路徑問題模型構(gòu)建與問題特性分析方面：首先，借鑒相關文獻的研究成果，通過采用更簡便的方式來表示“服務次序約束”和“裝卸約束”，以建立一個更簡便的混合整數(shù)線性規(guī)劃模型。其次，基于對問題特性的深入分析，提出了6類多項式型有效不等式來加強模型構(gòu)建。最后，基于數(shù)值實驗驗證了本書提出的改進模型具有明顯的優(yōu)勢（求解性能提高），以及本書提出的有效不等式可顯著提高模型的性能。

（5）單次訪問條件下的供需未匹配多商品取送貨車輛路徑問題啟發(fā)式算法設計方面：為快速求解現(xiàn)實中常見的較大規(guī)模的問題，基于本書提出的模型，首先，設計一個基于運輸效率提升的貪婪式算法來構(gòu)建初始解。其次，基于優(yōu)化供需匹配決策和車輛路徑?jīng)Q策的思想，對已有的相關鄰域結(jié)構(gòu)進行整合改進，進而提出一個改進的變鄰域搜索算法來改善初始解的質(zhì)量。最后，為驗證該算法的效果，借助CPLEX設計求解問題下界的方法。實驗結(jié)果表明，本書提出的改進的變鄰域搜索算法在較短時間內(nèi)能夠?qū)λ芯康膯栴}提供最優(yōu)或近似最優(yōu)解，且在求解質(zhì)量和求解效率方面均優(yōu)于文獻中已有變鄰域搜索算法。

（6）單次訪問條件下的供需未匹配多商品取送貨車輛路徑問題精確算法設計方面：為針對現(xiàn)實中中小規(guī)模的問題求出最優(yōu)解，首先，基于前面建立的數(shù)學模型，通過松弛一些較松弛的約束來建立一個容易求解的數(shù)學模型。其次，基于對問題特性的深入分析，提出3類指數(shù)型有效不等式來加強模型。再次，針對每類指數(shù)型有效不等式設計了相應的分離算法。最后，基于初始上界選取、預處理操作、分支策略和分離算法調(diào)用策略的深入討論，設計了一個分支切割算法。實驗結(jié)果表明，本書設計的分支切割算法在規(guī)定時間內(nèi)能夠求解10個客戶和6種商品的算例，且在求解規(guī)模和求解時間方面均優(yōu)于優(yōu)化軟件CPLEX。

---

[1] CPLEX是一種數(shù)學優(yōu)化技術，主要用于提高效率、快速實現(xiàn)策略并提高收益率。