需求可拆分的車輛路徑問題及其研究進展

1、<p>　　需求可拆分的車輛路徑問題及其研究進展</p><p>　　摘要：車輛調(diào)度是運輸環(huán)節(jié)優(yōu)化的關(guān)鍵所在，可拆分車輛路徑問題作為車輛路徑問題的一個重要分支，具有更切合車輛配送的實際情況，更能滿足企業(yè)經(jīng)營管理的實際需求。本文首先對需求可拆分的車輛路徑問題進行了簡要介紹，然后對其國內(nèi)外研究進展進行了詳細分析。 </p><p>　　Abstract： Vehicle schedu

2、ling is the key of the transportation optimization， vehicle routing problem with split demand is an important branch， is more in line with the actual situation of vehicle delivery， and can better meet the actual needs of

3、 the enterprise management. This paper briefly introduces the vehicle routing problem with split demand， and then makes a detailed analysis of the domestic and foreign research progress. </p><p>　　關(guān)鍵詞：需求可拆分；

4、車輛路徑問題；研究進展 </p><p>　　Key words： split demand；vehicle routing problem；research progress </p><p>　　中圖分類號：TP301.6 文獻標識碼：A 文章編號：1006-4311（2016）34-0097-03 </p><p><b>　　0 引言 </b

5、></p><p>　　運輸是整個物流活動體系中非常重要的一個環(huán)節(jié)，貫穿著生產(chǎn)和銷售的整個過程。通常，運輸成本在企業(yè)的運營成本中占有較大的比重，尤其是在加工制造，能源等行業(yè)。同時，運輸?shù)母咝砸矊ζ髽I(yè)的倉儲、生產(chǎn)和管理等環(huán)節(jié)有著很大影響。另外，作為聯(lián)系企業(yè)和最終用戶的紐帶和橋梁，運輸?shù)男手苯佑绊懼髽I(yè)對客戶需求的響應速度，影響客戶對企業(yè)服務的滿意程度。因此，運輸環(huán)節(jié)的優(yōu)化程度對于企業(yè)運營成本的降低，運行效

6、率的提高以及競爭力的提高有著至關(guān)重要的影響。 </p><p>　　車輛調(diào)度是運輸環(huán)節(jié)優(yōu)化的關(guān)鍵所在，其要解決的問題是如何在滿足各種限制條件下，如車輛載重量，時間和客戶需求量等，合理安排車輛的行駛路線和對客戶進行服務的順序，以達到降低運輸成本的目的?？刹鸱周囕v路徑問題作為車輛路徑問題的一個重要分支，具有更切合車輛配送的實際情況，更能滿足企業(yè)經(jīng)營管理的實際需求的特點，因此在理論研究方面也得到越來越多的關(guān)注。 <

7、;/p><p>　　1 可拆分的車輛路徑問題 </p><p>　　合理的車輛調(diào)度方案能夠有效地降低物資運輸成本，提高運輸效率，然而，在實際的企業(yè)運營過程中，車輛調(diào)度方案的確定通常是由相關(guān)工作人員根據(jù)經(jīng)驗制定的，這樣的車輛調(diào)度方案往往存在許多的不合理性，尤其是在信息量非常龐大的情況下。因此，如何幫助企業(yè)制定科學合理的車輛調(diào)度方案成為學者們?nèi)找骊P(guān)注的問題。 </p><p&g

8、t;　　在這種背景下，Dantzig和Ramser在1959年提出了車輛路徑問題（Vehicle Routing Problem， 簡稱VRP），迄今為止已有不同領(lǐng)域的眾多專家學者對該問題進行了大量的研究。但是傳統(tǒng)的VRP問題中存在一個限定條件：每個客戶點只能由一輛車服務且只能服務一次，即客戶點的需求不能進行拆分配送。但是在現(xiàn)實的車輛調(diào)度過程中往往會存在以下兩種情況：①某個客戶對物品的需求量超過車輛的最大載重量；②大多數(shù)客戶的需求量都超

9、過車輛最大載重量的一半。傳統(tǒng)的VRP問題顯然不適用于情況①，對于情況②而言，傳統(tǒng)的VRP問題也不能達到很好的優(yōu)化效果。如圖1所示，V0為車場，V1，V2，V3，V4，V5為五個等待服務的客戶點，且每個客戶點的需求量均為6單位，假設(shè)每兩個顧客之間的距離均為1，車輛的最大載重量Q=15，則圖1（a）為傳統(tǒng)VRP下的最優(yōu)解，圖1（b）為對需求進行拆分后的得到最優(yōu)解。 </p><p>　　從圖1中可以看出圖1 （a）、

10、1 （b）中車輛的總行駛路程都是8，但是在允許拆分配送的情況下僅需要2輛車就能完成對全部顧客點的服務，而圖1 （a）情況下則需要3輛車才能完成，這樣就必然會出現(xiàn)空車駛回的情況，造成車輛資源的浪費和物流成本的提高?？紤]到上述兩種情況的存在，Dror和Trudeau]在1989年提出了需求可拆分的車輛路徑問題（Split Delivery Vehicle Routing Problem，簡稱SDVRP），即取消了傳統(tǒng)的VRP問題中每個顧客點

11、能且僅能被一輛車服務一次的約束條件，允許一個客戶點被服務多次。顯然，SDVRP更符合實際中車輛配送的特點，也更能滿足現(xiàn)實生活中優(yōu)化車輛調(diào)度的目的。 </p><p>　　2 SDVRP的研究進展 </p><p>　　2.1 國外研究進展 </p><p>　　Dror和Trudeau最早提出的并構(gòu)建了SDVRP的數(shù)學模型，Dror和Trudeau還證明了配送中心在

12、對客戶點進行產(chǎn)品配送時，如果客戶點的需求允許被拆分配送，那么，無論是從車輛的行駛距離還是所使用車輛的數(shù)量上看，都優(yōu)于客戶需求只能被一輛車服務一次的情況，同時，作者還使用算例證明了當客戶點數(shù)趨于無窮大時，拆分配送求解得到的最優(yōu)值可能僅是傳統(tǒng)VRP最優(yōu)值的一半。 </p><p>　　Dror和Trudeau在提出SDVRP時就指出了該問題是一個NP難題，求解具有很大的難度。但是，由于可拆分的車輛路徑問題更符合現(xiàn)實中

13、車輛配送的情況，而且也更有利于降低配送企業(yè)的成本，因此，可拆分的車輛路徑問題一經(jīng)提出后就有大量學者根據(jù)不同的背景和假設(shè)條件對其進行了研究，目前對該問題的研究主要集中在帶時間窗、帶集送貨需求和利潤最大化等領(lǐng)域。 </p><p>　　2.1.1 時間窗 </p><p>　　對于帶時間窗的可拆分車輛路徑問題可用精確算法進行求解，首先采用Dantzig-Wolfe分解法將問題進行分解，再用分支

14、定界發(fā)對子問題進行求解，同時采用列生成算法求解主問題。隨后，有學者又提出了一種不同的Dantzig-Wolfe分解法，引入一種極端配送方式，即對于所有的客戶，其需求如果無法被全部滿足那么就不對其進行配送。Archetti等對求解該問題的算法進行了改進，用禁忌搜索算法求解子問題。 　　2.1.2 集送貨需求 </p><p>　　Mitra就帶集送貨需求的可拆分車輛路徑問題構(gòu)造了混合整數(shù)線性規(guī)劃模型，與傳統(tǒng)集送貨

15、問題的假設(shè)不同之處在于一個客戶點可以同時擁有取貨和集貨需求，而且需求數(shù)量沒有限制，可以超過車輛的最大載重量。對這個問題的求解作者構(gòu)造了一種啟發(fā)式方法，首先決定車輛的最小需求量，然后根據(jù)節(jié)約插入的標準設(shè)計路徑。將拆分配送在集送貨問題中的優(yōu)勢進行了量化，可以證明對于一個給定的配送網(wǎng)絡，當需求量正好是車輛容量的一半時，拆分配送的節(jié)約值最大。Thangiah等研究了帶集送貨需求和時間窗因素的可拆分車輛路徑問題。 </p><

16、p>　　2.1.3 利潤最大化 </p><p>　　一般的可拆分車輛路徑問題在目標函數(shù)的設(shè)定時只是考慮最小化車輛所行駛的距離，F(xiàn)eillet等將車輛的使用成本也加入到目標函數(shù)，作為衡量求解結(jié)果滿意程度的標準之一。在這種情況下，配送中心需要從潛在的客戶點中選擇一部分能使利潤最大化的客戶點，只對這些客戶點進行服務。 </p><p>　　除此之外，也有部分學者對其他條件下的可拆分車輛路

17、徑問題進行了研究，例如Bertazzi等將庫存問題與可拆分車輛路徑問題相結(jié)合進行了研究；Tavakkoli-Moghaddam等考慮了多車隊的情況，構(gòu)造了最小化車隊成本和距離成本的目標函數(shù)，其中車隊成本包括使用的車輛數(shù)量以及車輛的非滿載懲罰，并設(shè)計了相應的模擬退火算法對模型進行求解；Bouzaiene-Ayari等考慮顧客需求量為隨機的情況；Nagao和Nagamochi對多產(chǎn)品可拆分車輛路徑問題進行了研究，該研究中配送中心可以提供多種

18、產(chǎn)品，每個客戶對不同的產(chǎn)品都有不同的需求，客戶可以被服務多次，但是每種產(chǎn)品只能由一輛車服務，作者使用動態(tài)規(guī)劃算法對實際數(shù)據(jù)進行了求解實驗。 </p><p>　　2.2 國內(nèi)相關(guān)研究現(xiàn)狀 </p><p>　　可拆分車輛調(diào)度問題近幾年才得到國內(nèi)學者的重視，研究相對較少。下面本文從模型和算法兩部分對國內(nèi)在可拆分車輛路徑問題領(lǐng)域的研究成果進行簡單的回顧和總結(jié)。 </p><

19、p>　　2.2.1 問題模型 </p><p>　　侯立文等構(gòu)造了同時考慮客戶需求可拆分和配送中心有時間窗限制的車輛路徑模型，該模型中的時間窗為硬時間窗，車輛可以提前到達客戶點，但是不允許晚于客戶點的最晚開始服務時間。譚家美，徐瑞華假設(shè)只有當客戶需求大于車輛剩余載重量時才進行拆分運輸，構(gòu)造了基于這一假設(shè)的新的需求可拆分車輛調(diào)度模型，并利用實驗證明當客戶點的需求與車輛載重的比例較大時，拆分運輸?shù)慕Y(jié)果優(yōu)于不可拆

20、分情況下的結(jié)果。楊亞?b，靳文舟等在Mitra的基礎(chǔ)之上對集送貨可拆分車輛路徑問題繼續(xù)進行了研究，假設(shè)各任務點即具有送貨需求又具有集貨需求，車輛在進行服務的時候采用先卸后裝的方式。李三彬等提出了需求可拆分的多種車輛的開放式車輛路徑問題，即車輛在服務完所有客戶點后不必返回車場，同時在目標函數(shù)中對非滿載車輛的剩余載重量進行懲罰。在現(xiàn)實生活中，客戶往往有多個可以接受送貨的時間窗，根據(jù)這一情況，馬華偉等構(gòu)建了需求可拆分的多時間窗車輛調(diào)度問題的模

21、型，并用蟻群算法進行了求解。 </p><p>　　2.2.2 求解算法 </p><p>　　在求解方面，謝毅根據(jù)需求可拆分車輛調(diào)度問題模型分別設(shè)計了禁忌搜索算法和遺傳算法，將最近鄰插入法應用到初始解的構(gòu)造中，提高了算法的有效性，并通過對比兩種算法的求解結(jié)果和所需時間發(fā)現(xiàn)禁忌搜索算法的整體質(zhì)量要優(yōu)于遺傳算法。侯立文，譚家美，趙元將蟻群算法中的轉(zhuǎn)移概率和最大最小螞蟻算法相結(jié)合重新設(shè)計了算法

22、，成功求解了帶時間窗的可拆分車輛調(diào)度問題。劉旺盛等人將可拆分車輛調(diào)度問題分成兩個階段進行求解，分別設(shè)計了先分組后路徑和先路徑后分組兩種啟發(fā)式算法，隨后又證明了當客戶需求大于車輛最大載重量時則該客戶點的需求不宜被拆分，在此基礎(chǔ)上采用先分組后路徑的原則設(shè)計了一個兩階段的聚類算法。謝秉磊等對需求可拆分車輛路徑問題的模型進行了改進，縮小了最優(yōu)解的搜索空間，并用2-opt法對螞蟻算法進行了優(yōu)化。 </p><p><

23、b>　　3 總結(jié) </b></p><p>　　車輛調(diào)度是運輸環(huán)節(jié)優(yōu)化的關(guān)鍵所在，可拆分車輛路徑問題作為車輛路徑問題的一個重要分支，具有更切合車輛配送的實際情況，更能滿足企業(yè)經(jīng)營管理的實際需求，本文首先對需求可拆分的車輛路徑問題進行了簡要介紹，然后對其國內(nèi)外研究進展進行了詳細分析。希望本文能對企業(yè)的經(jīng)營決策以及相關(guān)研究人員提供有益的借鑒和參考。 </p><p><

24、b>　　參考文獻： </b></p><p>　　[1]Dantzig，DB， Ramser，JH. The truck dispatching problem. Management Science，1959，6：80. </p><p>　　[2]Archetti，C.，Bouchard，M.，Desaulniers，G.. Enhanced branch </

25、p><p>　　-and-price-and-cut for vehicle routing with split deliveries and time windows. Transportation Science，2011，45：285-298. </p><p>　　[3]Mitra，S.. An algorithm for the generalized vehicle routin

26、g problem with backhauling. Asia-Pacific Journal of Operational Research，2005，22：153-169. </p><p>　　[4]Thangiah，SR.，F(xiàn)ergany，A.，Awan，S.. Real-time split-delivery pickup and delivery time window problems with

27、transfers. Central European Journal of Operations Research，2007，15：329-349. </p><p>　　[5]Tavakkoli-Moghaddam，R.，Safaei，N.. A new capacitated vehicle routing problem with split service for minimizing fleet co

28、st by simulated annealing. Journal of the Franklin Institute，2007，344：406-425. </p><p>　　[6]李三彬，柴玉梅，王黎明.需求可拆分的開放式車輛路徑問題研究[J].計算機工程，2011，37（6）：168-171. </p><p>　　[7]劉旺盛，黃娟.需求可拆分的車輛路徑問題的分段求解[J].集美

29、大學學報，2011，16（1）：38-44. </p><p>　　[8]劉旺盛，楊帆.需求可拆分車輛路徑問題的聚類求解算法[J].控制與決策，2012，27（4）：535-541. </p><p>　　[9]馬華偉，葉浩然，夏維.允許分割配送的多時間窗車輛調(diào)度問題的改進蟻群算法求解[J].中國管理科學，2012，20：43-4. </p><p>　　[10]譚

30、家美，徐瑞華.客戶需求可分的車輛路徑問題求解[J].系統(tǒng)管理學報，2008，17（1）：43-46. </p><p>　　[11]吳悅，汪定偉.用遺傳/禁忌搜索混合算法求解可變加工時間的調(diào)度問題[J].控制與決策，1998，13：428-432. </p><p>　　[12]謝秉磊，胡小明，張一??.需求可分的車輛路徑問題模型與算法[J].運籌與管理，2012，21（3）：72-76.

31、 </p><p>　　[13]楊亞?b，靳文舟.求解集送貨可拆分車輛路徑問題的啟發(fā)式算法[J].華南理工大學學報，2010，38（3）：58-63. </p><p>　　[14]汪婷婷，倪郁東，何文玲.需求可拆分車輛路徑問題的蜂群優(yōu)化算法[J].合肥工業(yè)大學學報（自然科學版），2014（8）：1015-1018. </p><p>　　[15]熊浩，鄢慧麗.需求