需求可拆分的車(chē)輛路徑問(wèn)題及其研究進(jìn)展

1、<p>　　需求可拆分的車(chē)輛路徑問(wèn)題及其研究進(jìn)展</p><p>　　摘要：車(chē)輛調(diào)度是運(yùn)輸環(huán)節(jié)優(yōu)化的關(guān)鍵所在，可拆分車(chē)輛路徑問(wèn)題作為車(chē)輛路徑問(wèn)題的一個(gè)重要分支，具有更切合車(chē)輛配送的實(shí)際情況，更能滿足企業(yè)經(jīng)營(yíng)管理的實(shí)際需求。本文首先對(duì)需求可拆分的車(chē)輛路徑問(wèn)題進(jìn)行了簡(jiǎn)要介紹，然后對(duì)其國(guó)內(nèi)外研究進(jìn)展進(jìn)行了詳細(xì)分析。 </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、車(chē)輛路徑問(wèn)題；研究進(jìn)展 </p><p>　　Key words： split demand；vehicle routing problem；research progress </p><p>　　中圖分類(lèi)號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-4311（2016）34-0097-03 </p><p><b>　　0 引言 </b

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、b>　　參考文獻(xiàn)： </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]李三彬，柴玉梅，王黎明.需求可拆分的開(kāi)放式車(chē)輛路徑問(wèn)題研究[J].計(jì)算機(jī)工程，2011，37（6）：168-171. </p><p>　　[7]劉旺盛，黃娟.需求可拆分的車(chē)輛路徑問(wèn)題的分段求解[J].集美

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

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

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