摘要：SDVRP允許單一節(jié)點的訂單需求由多個車輛進行配送，與傳統(tǒng)VRP相比可提高車輛利用率并降低車輛使用數(shù)目和運輸成本。文中在國內(nèi)外研究的基礎(chǔ)上，重點介紹了SDVRP的主要分支，并與國內(nèi)研究現(xiàn)狀對比，發(fā)現(xiàn)我國在該領(lǐng)域的研究仍處于起步階段。

關(guān)鍵詞：需求可拆分車輛路徑問題；分支；國內(nèi)現(xiàn)狀

一.引言

傳統(tǒng)的VRP一直是網(wǎng)絡(luò)最優(yōu)化問題中最基本的問題之一，由于其應(yīng)用的廣泛性和經(jīng)濟上的重大價值，多年以來，受到國內(nèi)外廣泛關(guān)注。傳統(tǒng)的VRP假定每個客戶端的需求只能由一輛車來完成，即需求不可以被拆分，但實際應(yīng)用中，有可能會存在相當(dāng)一部分任務(wù)點的需求量比較大，此時，如果仍然要求每個客戶點只能由一輛車來完成服務(wù)，勢必會造成車輛的空載率提高，浪費運輸資源。1989年Dror Trudeau首次提出了SDVRP的概念[1]，并指出 SDVRP 是一種約束松弛的 VRP，即每個客戶點的需求由傳統(tǒng)VRP中的只能由一輛車滿足，擴展為可以由多輛車滿足，這可使得車輛數(shù)量和路線總長得到節(jié)約。

二.SDVRP的分類

根據(jù)研究重點的不同，SDVRP 有多種分類方式。雖然諸如帶時間窗、帶集貨和配送的VRP在傳統(tǒng)VRP問題中已經(jīng)被大量研究，但是，在SDVRP情況下，仍然會得出一些有意義的結(jié)論。根據(jù)對國內(nèi)外文獻進行歸納，常見的SDVRP的分支主要有以下幾類：

（一）帶時間窗限制（SDVRPTW）。

帶時間窗限制，意味著訂單必須在顧客規(guī)定的時間段內(nèi)到達，帶時間窗限制的車輛路徑問題（VRPTW）屬于傳統(tǒng)VRP分支。Archetti et al.提出了第一個求解SDVRPTW的精確算法 [2]。他們運用禁忌搜索算法和新的有效不等式對子問題分別求解，一種新的啟發(fā)式算法則被用于尋找最優(yōu)拆分點。實驗結(jié)果表明，該求解方法對顧客規(guī)模為100的SDVRPTW同樣具有良好的求解效果。目前，基于禁忌搜索求解SDVRPTW的啟發(fā)式算法，是由Ho Haugland提出的[3]，該算法將SDVRPTW的求解規(guī)模擴大至100以上。

（二）帶集貨和配送限制（SDVRPPD）。

在SDVRPPD中，無時間窗和最大車輛路線限制，但每一節(jié)點只能被一輛車訪問一次，且每一節(jié)點可能同時具有收貨和配送兩種需求，任一節(jié)點的需求都可能超過車輛容量。其目標(biāo)函數(shù)是通過最小化車輛使用數(shù)目來最小化總運輸成本。這一應(yīng)用在實際生活中非常常見，如快遞員在送貨的過程中，經(jīng)常也會收到客戶寄送貨物的需求.Nowak et al.通過研究證明[3]，在同一地理分布的顧客群下，當(dāng)訂單平均大小為車載容量一半時，拆分能夠獲得最大的收益。

（三）利潤最大化

一般情況下，SDVRP的目標(biāo)函數(shù)是最小化車輛行駛路線或運輸成本，有時也對使用成本進行優(yōu)化。但是，由于需求可拆分，可能帶來額外收益。Brnmo et al.通過數(shù)學(xué)規(guī)劃模型并整合分區(qū)的方法對此類問題進行求解[3]，結(jié)果證明允許拆分可以提高物流企業(yè)利潤率。

（四）庫存和生產(chǎn)

自從供應(yīng)鏈管理的觀念提出以來，庫存路徑問題已為很多學(xué)者關(guān)注。由于庫存的概念是基于時間、庫存成本以及庫存容量之上，時間成為SDVRP中考慮的一個重要因素。在這些問題中，一個顧客通常在特定的時間范圍可以被訪問多次，但是一個配送日內(nèi)只能訪問一次。同時，庫存路徑模型還會考慮生產(chǎn)制造策略。

（五）其他

除了以上四種主要的SDVRP分支以外，考慮最小損耗率、混合車輛編隊、隨機性、需求的離散性以及弧路徑的SDVRP分支也逐漸出現(xiàn)在國內(nèi)外研究中，限于文章篇幅不在此一一贅述。

三.國內(nèi)研究現(xiàn)狀

當(dāng)前，國內(nèi)對SDVRP的研究尚不多見。隋露斯，唐加福等用蟻群算法求解SDVRP[4]，給出了基于整數(shù)規(guī)劃的描述方法；通過仿真實驗發(fā)現(xiàn)，該算法對車輛數(shù)目和運輸距離的改進顯著。魯強等用遺傳算法求解K-SDVRP[5]，數(shù)值試驗表明，某些條件下，SDVRP較VRP車輛使用數(shù)和車輛運輸距離更少。孟凡超等通過改進傳統(tǒng)的數(shù)學(xué)模型[6]，建立SDVRP數(shù)學(xué)模型，利用禁忌搜索算法對SDVRP進行求解。算例結(jié)果表明，該模型可以節(jié)省車輛數(shù)目、縮短路線長度、提高車輛裝載率。楊亞璪等等對SDVRPPD進行研究[7]，算例結(jié)果表明，所設(shè)計的算法可以得到合理的車輛路徑，特別當(dāng)集貨需求的總量小于送貨需求的總量時，優(yōu)化效果更好。

無論是使用蟻群算法、禁忌搜索算法還是遺傳算法，隋露斯、魯強、孟凡超以及楊亞璨等人關(guān)于可拆分車輛路徑問題的研究，都是在需求確定的情況下研究SDVRP，并未考慮客戶的時間窗以及需求的隨機性。

四.結(jié)論

在對SDVRP的主要分支以及常用求解方法進行總結(jié)的基礎(chǔ)上，我們發(fā)現(xiàn)目前對SDVRP的求解方法主要是通過混合整數(shù)規(guī)劃建模并整合精確或者啟發(fā)式算法對問題進行求解，但隨著問題規(guī)模的擴大，其求解面臨著維數(shù)災(zāi)難的問題。計算機仿真作為一種新的建模方法，隨著計算機技術(shù)的發(fā)展，使研究者可以通過搜索海量解空間找到問題的次優(yōu)解或者最優(yōu)解，為求解SDVRP提供了一種新的解決途徑。（作者單位：深圳大學(xué)）

參考文獻

[1]Dror， M.， Trudeau， P.， 1989. Savings by split delivery routing. Transportation Science 23， 141–145.

[2]Archetti， C.， Bouchard， M.， Desaulniers， G. Enhanced branch-and-price-and-cut for vehicle routing with split deliveries and time windows. Transportation Science.2011.

[3]Archetti C.， M. G. Speranza. Vehicle routing problems with split deliveries. International Transactions in Operational Research. 19（2012）：3-22

[4]隋露斯，唐加福. 用蟻群算法求解需求可拆分車輛路徑問題[C]. 中國控制與決策會議. 2008：997-1001

[5]魯強，唐加福等. 用遺傳算法求解可拆分運輸?shù)能囕v路徑問題[C].第二屆中國智能計算大會論文集，洛陽，2008年8月3-7日， pp1-5

[6]孟凡超，陸志強等，需求可拆分車輛路徑問題的禁忌搜索算法[J]. 計算機輔助工程. 2010（1）：78-83

[7]楊亞璪，靳文舟等. 求解集送貨可拆分車輛路徑問題的啟發(fā)式算法[J]. 華南理工大學(xué)學(xué)報（自然科學(xué)版）. 2010.38（3）： 58-63