1.2 國內外研究現狀

自從Dantzig和Ramser（1959）首次提出并定義了車輛路徑問題，此問題就一直是研究的熱點。Campbell等（2002）、Moin和Salhi（2007）、Bertazzi等（2008）以及Liu等（2011）分別對VRP的研究成果進行了總結與歸納。孫麗君等（2006）總結了有關VRP的模型及算法研究。當前文獻中與本課題相關的3個問題分別是供需匹配關系未知的取送貨車輛路徑問題、分批次取送貨車輛路徑問題、允許多次訪問的取送貨車輛路徑問題。故本章接下來對這3個相關問題已取得的研究成果進行歸納與總結。

1.2.1 供需匹配關系未知的取送貨車輛路徑問題研究現狀

當前文獻關于供需匹配關系事先已知的取送貨問題的研究較多（Toth and Vigo，2002；Lin et al.，2011；Pandelis et al.，2013；Parragh and Schmid，2013；Simonin and Sullivan，2014；Masmoudi et al.，2016）。在此類問題中，網絡中各客戶點之間的供需匹配關系事先已確定，即任意兩點之間需轉運的產品類型及數量已確定。相對此類問題，供需匹配關系事先未知的取送貨車輛路徑問題為節約運輸成本提供了機遇，因為后者相對前者松弛了網絡中各客戶點之間已固定的供需匹配關系，使網絡中各客戶點之間的供需匹配關系變成一項決策，因此可以通過尋找更好的供需匹配關系來獲得更好的運輸方案，進而降低運輸成本。最近幾年，供需匹配關系未知的取送貨車輛路徑問題吸引了許多學者的目光（Battara et al.，2014），接下來將對文獻中關于此類問題的研究進行分類與歸納。

1.2.1.1 單車運輸情況下供需匹配關系未知的取送貨車輛路徑問題

單車運輸情況下的供需匹配關系未知的取送貨車輛路徑問題在當前文獻中被稱作“取送貨旅行商問題”（Pickup and Delivery Traveling Salesman Problem，PDTSP），以運輸網絡中產品類型數目劃分以下兩種情況討論。

（1）單產品

單產品取送貨旅行商問題（1-PDTSP）是對經典旅行商問題（TSP）的擴展，Hernández-Pérez和Salazar-Gonzalez（2004a）引進了此問題。在此問題中，所有的客戶點根據需求類型不同（送貨需求或取貨需求）被劃分為兩個不同的團體。每個有送貨需求的客戶點通常需要一定數量的產品，每個有取貨需求的客戶點通常可以供應一定數量的產品，且每個有取貨需求的客戶點均可以向任何一個有送貨需求的客戶點提供任何數量的產品。目標是如何設計一個運輸成本最小的產品調運方案，在滿足車容量約束條件的前提下，通過訪問每個客戶點一次性滿足所有客戶點的需求。此問題普遍存在于多個現實行業中，如在銀行系統中，對各個支行之間的現金存量重新分配（Hernández-Pérez and Salazar-Gonzalez，2004a）；在共享單車系統中，對各站點之間自行車庫存重新布局（Chemla et al.，2013）。針對該問題，Hernández-Pérez和Salazar-Gonzalez（2004a）建立了0～1整數線性規劃模型，并提出了一個分支切割算法來求解該問題；Salazar-Gonzalez（2004b）提出了兩個啟發式算法：一個是基于提高k-optimality的貪婪算法，另一個是基于分支切割進程的局部最優算法；Hernández-Pérez和Salazar-Gonzalez（2007）改進了有能力約束的車輛路徑問題（CVRP）的有效不等式，并提出了一些新的有效不等式和一個分支切割算法。實驗結果表明，提出的算法如果使用新的有效不等式就能夠求解100個客戶點的算例，否則只能夠求解50個客戶點的算例；Hernández-Pérez等（2009）提出了一個貪婪式隨機自適應搜索（Greedy Randomized Adaptive Searching，GRASP）和變量領域下降法（Variable Neighborhood Descent，VND）的混合算法，并把計算結果與Hernández-Pérez和Salazar-Gonzalez（2004b）的結果做比較，對比結果表明Hernández-Pérez等（2009）提出的算法具有明顯的優勢；Zhao等（2009）提出了一個遺傳算法，該算法能夠對500個客戶點的算例求得最優解；Mladenovi?等（2012）提出了一個變鄰域搜索算法，該算法能夠對文獻中客戶點數為200～500的標準算例提供更好的解；Chemla等（2013）提出了一個嵌入禁忌搜索的分支切割算法來改善問題的上界；Ho和Szeto（2014）提出了一個迭代的禁忌搜索算法；Vogel等（2014）提出了一個嵌入大鄰域搜索的元啟發式算法；Kadri等（2016）提出了一個分支定界算法。Erdog?an等（2015）、Salazar-Gonzalez和Santos-Hernández（2015）探索了允許多次訪問每個客戶點的情況，其中Salazar-Gonzalez和Santos-Hernández（2015）只研究了允許每個客戶點最多被訪問2次和3次的情況。

（2）多產品

Hernández-Pérez和Salazar-Gonzalez（2014）引進了多產品取送貨旅行商問題（m-PDTSP）。在該問題中，運輸網絡中有多種產品，任何一種產品的供應客戶點都可以向任何需求該種產品的客戶點供應任何數量的產品。他們提出了一個混合整數線性規劃模型，討論了經典的分解技術，提出了一些有效不等式及一系列分離算法來提高線性松弛規劃模型的性能。實驗結果表明提出的分支切割算法能夠求解30個客戶點，3種產品的算例。緊接著，Hernández-Pérez等（2016）針對此問題提出了一個三階段的混合啟發式算法，并基于隨機產生的算例檢驗了此算法的性能。Li等（2016）基于共享單車系統，對多種類型的自行車重新布局問題提出了混合遺傳算法，實驗結果表明，此算法在較短時間內能夠對所研究的問題提供高質量的解。

1.2.1.2 多車運輸情況下供需匹配關系未知的取送貨車輛路徑問題

多車運輸情況下的供需匹配關系未知的取送貨車輛路徑問題在當前文獻中被稱作“取送貨車輛路徑問題”（Pickup and Delivery Vehicle Routing Problem，PDVRP）。相對于PDTSP，文獻中關于PDVRP的研究較少，同樣分為以下兩種情況討論：

（1）單產品

Shi等（2009）首次引進單產品取送貨車輛路徑問題（1-PDVRP）。自Raviv等（2013）通過探索共享單車系統的自行車重新布局問題（Bike Rebalancing Problem，BRP），研究了1-PDVRP以來，針對此問題的相關研究逐漸增多。Rainer-Harbach等（2013）針對此問題提出了一個變鄰域搜索算法，并基于現實的算例做了一系列實驗分析。Dell' Amico等（2014）提出了4個不同的混合整數規劃模型和一系列標準算例。Angeloudis等（2014）提出了一個被稱作“重新構建匹配關系”（repair）的算法。Forma等（2015）提出了一個三階段啟發式算法。Dell' Amico等（2016）提出了一個被稱作“破壞后重新構建匹配關系”（destroy and repair）的元啟發式算法，該算法能夠對文獻中的算例求出更好的解。Di和Urli（2016）建立了一個新穎的模型，實驗結果表明提出的分支定界精確算法和大鄰域搜索啟發式算法均優于當前文獻中的算法。

（2）多產品

Chen等（2014）通過考慮單次訪問和無限供應（每個供應客戶點的產品供應量無限大）引進了多產品取送貨車輛路徑問題（m-PDVRP）。提出的變鄰域搜索算法在1800秒內能夠對研究的問題提供高質量的解。本書研究的問題是對Chen等（2014）的多次訪問和有限供應的擴展，這些擴展使本書研究的問題雖更復雜但更接近現實。

1.2.2 分批次取送貨車輛路徑問題研究現狀

基于企業實際需求，取送貨車輛路徑問題一直受到廣泛關注（Dumas et al.，1991；R?pke et al.，2006；R?pke and Cordeau，2009；Pelikán and Fábry，2012；Yu and Liu，2014；Wang et al.，2015；Kalayci and Kaya，2016）。眾所周知，允許分批次送貨和允許分批次取貨為企業節省運輸成本提供了可能。接下來將依次總結文獻中關于分批次送貨車輛路徑問題、分批次取貨車輛路徑問題及分批次取送貨車輛路徑問題的研究現狀。

1.2.2.1 分批次送貨車輛路徑問題

分批次送貨車輛路徑問題（Split Delivery Vehicle Routing Problem，SDVRP）是指允許客戶點的需求通過多次投放來滿足，相對經典VRP為降低運輸成本和節約運輸車輛提供了機遇。Dror和Trudeau（1989）首先提出了可分批次送貨車輛路徑問題，即在經典VRP的基礎上，允許每個客戶點的需求分批次滿足。他們提出了兩階段搜索的啟發式算法。實驗結果表明，允許需求分批次滿足，相對需求一次性滿足的情況節約了近14%的運輸成本，且只需要較少的車輛來完成運輸任務。緊接著，Dror等（1990，1994），Frizzell和Griffin（1992），Sierksma和Tijssen（1998），Belenguer等（2000），Archetti等（2006a，2008，2014），Chen等（2007），Jin等（2007，2008），譚家美和徐瑞華（2008），Derigs等（2009），孟凡超等（2010），Archetti和Speranza（2012），Wilck IV和Cavalier（2012a，2012b），Silva等（2015）對此問題分別做了相關研究。其中，Dror等（1990）提出了混合整數線性規劃模型，驗證了SDVRP是一個NP-難題，且只要運輸距離滿足三角不等式原則，被分批次滿足的客戶點就不可能出現在最優解的不同路線中。Frizzell和Griffin（1992）提出了三種構建式啟發算法。Dror等（1994）提出了幾類新的有效約束，并通過實驗驗證了選擇合適的約束組合可以獲得更緊的上下界。Sierksma和Tijssen（1998）提出了一個基于列生成（column generation）的啟發式算法。Belenguer等（2000）提出了新的建模方法并對此問題的解空間進行了探索。Archetti等（2006a）首次提出了客戶點分批次送貨的定義與概念，即服務一個客戶點的實際車輛數多于服務該客戶點所需的最小車輛數。如車輛的容積為1個單位，針對需求量為3.6個單位的客戶點，如果使用5輛車或更多的車來滿足該客戶點的需求，那么此客戶點被稱作“分批送貨”。Chen等（2007）首先對當前階段SDVRP的應用背景、模型和求解算法等相關研究進行了總結，然后通過結合整數規劃和禁忌搜索提出了一個新的啟發式算法。Archetti等（2008）通過一系列實驗驗證了當網絡中客戶點之間的需求量差別較小且平均需求量剛剛超過車容量的一半時，分批次送貨節約的運輸成本最大。Jin等（2007）提出了一個基于有效不等式的兩階段算法，實驗結果表明該算法優于文獻中已有的精確算法。Jin等（2008）提出了一個列生成算法。譚家美和徐瑞華（2008）基于蟻群算法原理設計了相應的優化算法。Derigs等（2009）提出了基于局部搜索的元啟發式算法。孟凡超等（2010）提出了禁忌搜索算法，通過數值實驗同樣得出允許客戶點需求分批滿足可以減少運輸成本、減少所需車輛數和提高車輛裝載率的結論。Archetti和Speranza（2012）回顧了SDVRP的數學模型、主要特性、求解算法研究，并對文獻中SDVRP的衍生問題進行了總結。Wilck IV和Cavalier（2012b）提出了一個構建式啟發算法，并基于32個標準算例與文獻中列生成方法和兩階段方法做比較，實驗結果表明提出的構建式啟發算法優于這兩個方法，且能夠為其他啟發算法或精確算法提供較好的初始可行解。Wilck IV和Cavalier（2012b）提出了一個混合遺傳算法。Archetti等（2014）基于兩個松弛模型提出了兩個精確算法，并針對4類標準算例做了實驗，實驗結果表明提出的方法能夠對17個新算例求得最優解。Silva等（2015）通過考慮波動機制提出了反復迭代的局部搜索算法。該算法能夠改善文獻中324個標準算例中243個算例的解質量。解的質量最大提高了2.81%，平均提高了1.15%。隨著對SDVRP研究的相繼深入，目前出現了如下幾個SDVRP的變種：

（1）考慮時間窗約束的SDVRP（SDVRPTW）

Frizzell和Griffin（1995）通過考慮客戶點的送貨時間要求，引進了SDVRPTW，并首先提出了一個構建式啟發式算法來獲得初始解，然后提出了兩個啟發算法來改善初始解的質量。接下來，Mullaseril等（1997）提出了構建式啟發算法；Ho和Haugland（2004）用100個客戶點的算例來檢驗提出的禁忌搜索算法的效果；Gendreau等（2006）提出了分支定界（branch and bound）算法；Desaulniers（2010）、Salani和Vacca（2011）提出了分支定價切割（branch price and cut）算法。Archetti等（2011）采用禁忌搜索算法求解子問題，提出有效不等式，引進新的分離算法進而設計了更強的分支定價切割算法；Yan等（2015）提出了兩階段求解算法，并通過求解現實問題驗證了所提出算法的有效性。McNabb等（2015）檢驗了局部搜索對問題求解的影響。

（2）考慮最少投貨量約束的SDVRP（SDVRP-MDA）

Gulczynski等（2010）通過考慮最低投貨量約束研究了SDVRP-MDA。他們基于文獻中標準的VRP和SDVRP算例來驗證提出的啟發式算法的效果。針對此問題，Han和Chu（2016）提出了基于多個初始解的變鄰域搜索方法，并基于文獻中32個標準算例和4個不同標準的最低取貨量做了一系列測試，測試結果表明提出的算法能夠對128個算例中43個算例求得更好的解。

（3）考慮多車場的SDVRP（MDVRP）

Gulczynski等（2011）引入了多車場情況下的分批次送貨車輛路徑問題（Multi-Depot SDVRP，MDVRP），并提出了基于整數規劃的啟發式算法來求解該問題。此外，他們還分析了在相同車場允許分批次送貨和不同車場允許分批次送貨減少的運輸成本情況。針對此問題，Ray等（2014）研究了一個更有效的模型和算法；Wang等（2016）研究了每個客戶點都有特定服務時間限制的情況，并設計了相應的啟發式算法。該算法除了能夠對文獻中37個標準算例求得當前最好解外，還能夠對其他21個新算例求得近似最優解。

（4）考慮多商品的SDVRP（MCSDVRP）

據我們所知，只有Archetti等（2015）與Moshref-Javadi和Lee（2016）研究了多商品分批次送貨車輛路徑問題（Multi-commodity Vehicle Routing Problem with Split Delivery，MCSDVRP）。其中，Archetti等（2015）在研究分批次送貨時考慮了商品類型限制，即限制只有當客戶需求多種不同商品時才允許分批送貨，同種商品不允許分批送貨。測試結果表明提出的分支定價切割算法在兩小時內能夠求解40個客戶點，3種商品的算例。Moshref-Javadi和Lee（2016）相對于Archetti等（2015）松弛了商品類型限制，提出了兩個混合整數規劃模型，并通過改進文獻中模擬退火和變鄰域搜索算法設計了相應的啟發式算法。

1.2.2.2 分批次取貨車輛路徑問題

在分批次送貨研究的基礎上，Lee等（2006）研究了一個分批次取貨車輛路徑問題（Vehicle Routing Problem with Split Pick-ups，VRPSP）。在該問題中，網絡中有許多客戶點和唯一的車場（depot），每個客戶點都向車場供應一定數量的產品，每個客戶點所供應的產品都允許分批次取貨，目標是如何安排成本最低的運輸方案使所有客戶點供應的產品都運送到車場。Nowak等（2008）分析并驗證了允許分批次取貨能夠為取送貨車輛路徑問題節省運輸成本和運輸車輛。另外，通過數值實驗驗證了分批次取貨帶來的利益大小與取貨數量、取貨點和送貨點之間的運輸成本，以及在同一客戶點取送貨的頻繁程度密切相關。緊接著，Nowak等（2009）基于現實中的算例，探索了允許分批次取貨帶來的利益大小與客戶平均取貨量、取貨點相對送貨點的數量、取貨點和送貨點的聚集程度的關系。實驗結果表明，當客戶點的平均取貨量恰好超過車容量的一半時，允許分批次取貨帶來的利益最大。Nowak等（2012）研究了帶優先順序約束的VRPSP，即在訪問任何送貨點之前都必須訪問所有的取貨點。Lai等（2015）基于集裝箱運輸研究了一個類似的問題。Flisberg等（2009）基于卡車在森林伐木操作的優化路徑需求研究了此類問題。Korsvik等（2011）和Andersson等（2011）在海上運輸系統中對現貨分批次運輸做了研究。Mar-Ortiz等（2013）以搜集浪費的電子設備（Waste of Electric and Electronic Equipment，WEEE）為背景對此問題做了研究。Oncan等（2011）研究了一個一對一取送貨的VRPSP，并提出了一個分支切割（branch and cut）算法。Sahin等（2013）進一步針對Oncan等（2011）研究的問題提出了一個禁忌搜索和模擬退火的混合啟發式算法。Wang等（2013）研究了一個帶時間窗約束的VRPSP，并提出了線性規劃模型和混合啟發式算法。

1.2.2.3 分批次取送貨車輛路徑問題

當前文獻關于分批次取送貨車輛路徑問題（Vehicle Routing Problem with Split Deliveries and Pickups，VRPSDP）的研究相對較少，Mitra（2005）通過探索一個回程車輛路徑問題（Vehicle Routing Problem with Backhauling，VRPB）研究了此問題。在VRPB中，需要用一系列車輛把一些產品從車場運送到各個客戶點，再把各個客戶點中剩余的產品運送到車場，每個客戶點的取貨和送貨請求允許分批次滿足。顯然，此問題屬于VRPSDP。針對此問題，Mitra（2005）首先提出了混合整數線性規劃模型和路徑構建式啟發算法；Mitra（2008）進一步提出了一個并行集群技術（parallel clustering technique）來構建路徑；楊亞璪等（2010）設計了一個三階段啟發式算法；王科峰等（2011）通過實例驗證了允許分批次取送貨車輛路徑問題和不允許分批次取送貨車輛路徑問題在最優解的結構和性質上存在的差異。Hennig等（2012）基于原油運輸背景研究了此問題，并提出了列生成算法。Izuno等（2012）、Asefeh和Reza（2012）、Wang等（2014）針對此問題提出了包含初始解算法和混合算法的兩階段啟發式算法。楊鵬等（2015）、Nagy等（2015）為更好地理解此問題，對該問題的精確求解算法和啟發式求解算法進行了深度分析。Pelikan（2015）為此問題提供了新的數學模型并證明了此問題是NP-難題。

1.2.3 允許多次訪問的取送貨車輛路徑問題研究現狀

從車輛路徑的角度來看，導致本研究涉及的問題高度復雜的主要原因是考慮了“多次訪問”。由于“多次訪問”給車輛路徑規劃帶來了很大挑戰，因此在取送貨車輛路徑問題的相關領域中，考慮“多次訪問”的研究相對較少。通過查閱相關文獻可知，考慮“多次訪問”的取送貨車輛路徑問題的研究幾乎都集中在海上路徑規劃問題（Maritime Routing and Scheduling Problem，MRSP）。Mckay和Hartley（1974）受美國軍方的邀請研究了如何優化國防燃料供應中心向分布在不同地區的軍隊運輸石油問題，進而提出了海上路徑規劃問題。此問題也受到許多學者的關注，如Miller（1987）、Dror和Ball（1987）、Bausch等（1991）。接下來將對文獻中允許多次訪問的取送貨車輛路徑問題的研究進行分類與總結。

1.2.3.1 允許多次訪問帶庫存約束的取送貨車輛路徑問題

針對海上路徑規劃問題，考慮庫存約束的研究較多，此類問題在文獻中被稱作“海上庫存路徑問題”。接下來分以下兩種情況討論：

（1）單產品

Christiansen和Nygreen（1998a）研究了單產品的海上庫存路徑問題，在此運輸網絡中，有些港口生產氨，有些港口消耗氨，生產和消耗速率恒定。在每個港口的取貨或送貨操作都必須在特定時間內進行，每個生產港口都可以向任何其他消耗港口提供任何數量的氨，每個港口在計劃周期內都允許被相同或不同船只訪問多次，目標是設計一個總成本最低的運輸方案，使得各港口的需求得到滿足。他們針對此問題提出了一個數學規劃模型和一個嵌入分支定界的列生成方法。緊接著，Christiansen和Nygreen（1998b）提出了一個路線流模型。Christiansen（1999）研究了類似的問題，不同處在于限制每個港口最大被訪問次數和非同質的運輸船只，并提出了一個弧流模型。Song和Furman（2010）通過考慮日常變化的生產速率和消耗速率擴展了Christiansen（1999）的研究成果。Engineer等（2012）通過考慮船只的停靠時間、生產速率隨時間變化、消耗速率隨時間變化、庫容隨時間變化等，研究了一個更普遍的單產品海上庫存路徑問題。Agra等（2013a）探索了兩個離散時間模型。Papageorgiou等（2014）對文獻中單產品海上庫存路徑問題的研究進行了回顧。Jiang和Grossmann（2015）提出了幾個可替代的混合整數線性規劃模型。Mirzaei和Seifi（2015）研究了綜合考慮運輸成本、庫存成本及滯銷成本的情況，他們提出的模型能夠精確求解小規模問題，提出的元啟發式算法對大規模問題能夠提供較好的解。

（2）多產品

Al-Khayyal和Hwang（2007）以液態氣體運輸為背景，引入了多產品的海上庫存路徑問題：通過把每艘輪船隔成多個不同的艙來運輸不同的產品；考慮同質的船只，允許每個港口被相同或不同的輪船訪問多次。目標是在計劃周期內設計一個總運輸成本和裝卸成本最低的路徑規劃方案。他們先建立了一個混合整數非線性規劃模型，然后提出了一個等價的混合整數線性規劃模型。由于研究的問題很復雜，他們并沒有設計求解算法，只是借助優化軟件CPLEX用小規模算例來驗證問題求解難度隨“訪問次數”的增加而呈指數增長。針對同樣的問題，Siswanto等（2011）研究了不隔艙的情況。針對水泥工業中存在的類似問題，Christiansen等（2011）提出了一個嵌入構建式啟發的遺傳算法。Agra等（2013b）探索了一個近海原油分配問題并提出了幾個混合整數規劃模型。Agra等（2014）針對Agra等（2013b）的問題提出了一個混合啟發式算法。Agra等（2015）通過考慮隨機航行和停靠時間進一步擴展了Agra等（2013b）的研究工作。Hemmati等（2016）同樣基于近海運輸研究了類似的問題，提出了一個兩階段的混合啟發式算法，并基于小規模算例，把此混合算法與文獻中的精確算法做了比較。

1.2.3.2 允許多次訪問不帶庫存約束的取送貨車輛路徑問題

Hennig等（2012a）研究了原油運輸路徑規劃問題，該問題可以被看作允許多次訪問不帶庫存約束的取送貨車輛路徑問題。它雖然與海上庫存路徑問題類似，但不同處在于此問題研究運輸時不考慮生產，不考慮庫存約束。因此在該問題中，網絡中每個港口針對每種產品的供應信息和需求信息確定。他們的研究以原油提煉行業為背景，網絡中各個港口生產不同規格的原油，一些港口只供應一種規格的原油，另一些港口可以供應多種規格的原油。在每個港口取貨或送貨需在特定的時間窗內進行。他們建立了此問題的線性規劃模型，并提出了路徑生成算法來求解小規模問題。緊接著，Hennig等（2012b）針對此問題提出了嵌套的列生成算法來求解更大規模的問題。Hennig等（2015）比較了兩個可替代的路線流模型。Siddiqui和Verma（2015）研究了每個港口有多個時間窗約束的情況，并提出了復合粒子群算法。實驗結果表明，此算法優于簡單的粒子群算法和遺傳算法。針對類似問題，De等（2015）建立了一個魯棒性較好的數學模型并提出了一個分支定界算法。De等（2016）探索了以操作成本和運輸風險成本為雙目標的情況，并提出了復合粒子群算法。

1.2.4 取送貨車輛路徑問題求解算法研究現狀

1.2.4.1 分批次取送貨車輛路徑問題求解算法

（1）啟發式算法

針對分批次送貨車輛路徑問題（SDVRP），Dror和Trudeau（1989）、Yan等（2015）提出了兩階段啟發式算法；Frizzell和Griffin（1992，1995）、Mullaseril等（1997）、Wilck IV和Cavalier（2012a）提出了構建式啟發算法；Sierksma和Tijssen（1998）提出了一個基于列生成的啟發式算法；Chen等（2007）、Ho和Haugland（2004）以及孟凡超等（2010）提出了禁忌搜索算法；譚家美和徐瑞華（2008）基于蟻群算法思想設計了啟發式算法；Gulczynski等（2011）提出了基于整數規劃的啟發式算法；Wilck IV和Cavalier（2012a）提出了一個混合遺傳算法；Silva等（2015）和McNabb等（2015）提出了一個反復迭代的局部搜索算法；Han和Chu（2016）提出了一個基于多個初始解的變鄰域搜索算法；Moshref-Javadi和Lee（2016）基于文獻中的模擬退火和變鄰域搜索設計了啟發式求解算法。

針對分批次取貨車輛路徑問題（VRPSL），自Nowak等（2008）研究了一個啟發式算法以來，Korsvik等（2011）探索了一個大鄰域搜索算法；Mar-Ortiz等（2013）提出了一個貪婪式隨機自適應搜索算法；Sahin等（2013）提出了一個禁忌搜索和模擬退火相結合的啟發式算法；Lai等（2015）研究了一個自適應啟發式算法。

針對分批次取送貨車輛路徑問題（VRPSDP），Mitra（2005）和Mitra（2008）提出了一個路徑構建啟發式算法；楊亞璪等（2010）提出了一個三階段啟發式算法；Izuno等（2012）、Asefeh和Reza（2012）、Wang等（2014）提出了一個兩階段混合啟發式算法。

（2）精確算法

針對SDVRP，Dror等（1990，1994）和Gendreau等（2006）探索了分支定界算法；Belenguer等（2000）提出了一個切平面算法（Cutting Plane Algorithm）；Jin等（2007）基于有效不等式設計了一個兩階段求解算法；Jin等（2008）提出了一個列生成算法；Desaulniers（2010）、Salani和Vacca（2011）、Archetti等（2011）和Archetti等（2015）提出了一個分支切割算法。

針對VRPSL，Lee等（2006）基于最短路思想設計了動態規劃算法；Nowak等（2012）提出了一個前向搜索的最短路算法；Andersson等（2011）提出了一個分支定界算法；Oncan等（2011）提出了一個分支切割算法。

1.2.4.2 供需匹配關系未知的取送貨車輛路徑問題求解算法

（1）啟發式算法

針對單車、單產品的情況，Salazar-Gonzalez（2004b）提出了兩個啟發式算法：一個是基于提高k-optimality，另一個是基于分支切割進程的局部最優；Hernández-Pérez等（2009）提出了一個GRASP和VND的混合啟發式算法；Zhao等（2009）提出了一個遺傳算法；Mladenovi?等（2012）提出了一個廣義的變鄰域搜索算法；Ho和Szeto（2014）提出了一個反復迭代的禁忌搜索算法；Vogel等（2014）提出了一個嵌入大鄰域搜索的元啟發式算法。針對單車、多產品的情況，Hernández-Pérez等（2016）設計了一個三階段的混合啟發式算法；Li等（2016）設計了一個混合遺傳算法。針對多車、單產品的情況，Rainer-Harbach等（2013）提出了一個變鄰域搜索算法；Angeloudis等（2014）和Dell'Amico等（2016）提出了一個重新構建匹配關系的元啟發式算法；Forma等（2015）提出了一個三階段啟發式算法；Di和Urli（2016）探索了一個大鄰域搜索算法。針對多車、多產品的情況，Chen等（2014）提出了一個變鄰域搜索算法。

（2）精確算法

針對單車、單產品的情況，Hernández-Pérez和Salazar-Gonzalez（2004a，2007）、Chemla等（2013）、Erdog?an等（2015）、Salazar-Gonzalez和Santos-Hernández（2015）探索了一個分支切割算法；Kadri等（2016）提出了一個分支定界算法。針對單車、多產品的情況，Hernández-Pérez和Salazar-Gonzalez（2014）提出了一個分支切割算法。針對多車、單產品的情況，Raviv等（2013）、Di和Urli（2016）探索了分支定界算法；Dell'Amico等（2014）提出了一個分支切割算法。

1.2.4.3 允許多次訪問的取送貨車輛路徑問題求解算法

（1）啟發式算法

針對單產品、帶庫存約束的情況，Song和Furman（2010）提出了一個基于優化的啟發式算法（An Optimization based Heuristic Method）；Mirzaei和Seifi（2015）提出了一個基于模擬退火和禁忌搜索的元啟發式算法。針對多產品、帶庫存約束的情況，Siswanto等（2011）提出了一系列貪婪式啟發式算法；Christiansen等（2011）提出了一個嵌入構建式啟發的遺傳算法；Agra等（2014）提出了一個混合啟發式算法；Hemmati等（2015）提出了一個被稱作“ICGR”（Iterative Cargo Generating and Routing）的啟發式算法；Hemmati等（2016）提出了一個改進的大鄰域搜索算法。針對不帶庫存約束的情況，Siddiqui和Verma（2015）、De等（2016）提出了一個復合粒子群啟發式算法。

（2）精確算法

針對單產品、帶庫存約束的情況，Christiansen和Nygreen（1998a，1998b）、Christiansen（1999）提出了一個嵌入分支定界的列生成方法；Engineer等（2012）探索了一個分支定價切割算法；Jiang和Grossmann（2015）提出了一個分支定界算法。針對多產品、帶庫存約束的情況，Al-Khayyal和Hwang（2007）、Agra等（2013b）提出了一個分支定界算法；Agra等（2015）提出了一個列生成算法。針對不帶庫存約束的情況，Hennig等（2012a，2012b）提出了一個嵌套的列生成算法。