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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、b>　　3 總結(jié) </b></p><p>　　車輛調(diào)度是運(yùn)輸環(huán)節(jié)優(yōu)化的關(guān)鍵所在，可拆分車輛路徑問題作為車輛路徑問題的一個(gè)重要分支，具有更切合車輛配送的實(shí)際情況，更能滿足企業(yè)經(jīng)營管理的實(shí)際需求，本文首先對需求可拆分的車輛路徑問題進(jìn)行了簡要介紹，然后對其國內(nèi)外研究進(jìn)展進(jìn)行了詳細(xì)分析。希望本文能對企業(yè)的經(jī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]李三彬，柴玉梅，王黎明.需求可拆分的開放式車輛路徑問題研究[J].計(jì)算機(jī)工程，2011，37（6）：168-171. </p><p>　　[7]劉旺盛，黃娟.需求可拆分的車輛路徑問題的分段求解[J].集美

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

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

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