楊亞璪 靳文舟 郝小妮 田晟

(1.華南理工大學(xué)工商管理學(xué)院,廣東廣州 510640;2.華南理工大學(xué)土木與交通學(xué)院,廣東廣州 510640)

傳統(tǒng)的車輛路徑問(wèn)題(VRP)是Dantzig和Ramser在研究亞特蘭大煉油廠向各加油站投送汽油的運(yùn)輸路徑優(yōu)化問(wèn)題時(shí)提出的,主要用于解決物流網(wǎng)絡(luò)中任務(wù)點(diǎn)需求多樣性的滿足和服務(wù)車輛路徑的安排,通常以車輛容量、行駛距離、服務(wù)時(shí)間窗等為約束條件,以運(yùn)輸成本(可包括時(shí)間、距離和費(fèi)用成本等)最小為優(yōu)化目標(biāo).在現(xiàn)實(shí)問(wèn)題中,很多情況下存在著逆向物流的需求,一部分任務(wù)點(diǎn)需要送貨,另一部分任務(wù)點(diǎn)需要集貨,于是產(chǎn)生了帶集貨的車輛路徑問(wèn)題(VRPB)、裝卸混合車輛路徑問(wèn)題(MVRPB)、同時(shí)送貨和集貨的車輛路徑問(wèn)題(VRPSDP),如果考慮時(shí)間窗、物流中心個(gè)數(shù)、隨機(jī)需求等情況,問(wèn)題的類型就會(huì)更加多樣化[1-2].

上述問(wèn)題有一個(gè)共同點(diǎn),就是所有任務(wù)點(diǎn)只能接受一次服務(wù),車輛大多數(shù)情況下處于非滿載狀態(tài),任務(wù)點(diǎn)的集送貨需求不可拆分,但物流服務(wù)中部分或全部任務(wù)點(diǎn)集送貨需求量可能很大,車輛容量卻很小,在一次訪問(wèn)中車輛無(wú)法完成任務(wù),因此如何解決這類問(wèn)題值得研究.

1989年Dror和Trudeau[3]提出了需求可拆分的車輛路徑問(wèn)題(SDVRP),為上述問(wèn)題提供了解決思路,并指出允許需求拆分不僅可以節(jié)省服務(wù)距離,而且可以節(jié)省服務(wù)車輛數(shù)目,隨后便有更多的學(xué)者投入到這方面的研究[4-8].對(duì)SDVRP進(jìn)行再擴(kuò)展就可以得到集送貨可拆分的車輛路徑問(wèn)題(VRPSPDP),顯然,VRPSPDP更具一般性,但目前只有Mitra[9-10]對(duì)VRPSPDP進(jìn)行過(guò)探討,構(gòu)建了問(wèn)題的混合整數(shù)線性規(guī)劃模型,并先后給出了兩種啟發(fā)式算法.

文中將對(duì)VRPSPDP繼續(xù)進(jìn)行研究,借鑒Mitra給出的研究成果得到另一種啟發(fā)式算法,最后通過(guò)算例對(duì)比3種算法的求解效果.

1 VRPSPDP數(shù)學(xué)模型

1.1 問(wèn)題描述

VRPSPDP可以描述為:物流中心需要為多個(gè)任務(wù)點(diǎn)提供服務(wù),不涉及物流服務(wù)的外包,各個(gè)任務(wù)點(diǎn)位置已知,同時(shí)具有送貨和集貨需求,且需求量可以超過(guò)車輛容量,車輛從物流中心出發(fā),載運(yùn)一定的貨物到達(dá)任務(wù)點(diǎn),采用先卸后裝的方式完成任務(wù),車內(nèi)貨物可以根據(jù)裝卸貨物的實(shí)際情況進(jìn)行很好的位置調(diào)整,或者能夠滿足裝卸貨物的要求,任務(wù)點(diǎn)的集送貨需求量可以拆分,由不同車輛或同一車輛多次完成,所有車輛保證途中不得超載,合理安排車輛的行駛路線,使得所有車輛的行駛距離之和最小.

基本假設(shè):(1)物流中心只有一個(gè),所有車輛從物流中心出發(fā)并最終回到物流中心;(2)配送車輛類型單一,數(shù)目事先確定,不再考慮因車輛數(shù)量變化而產(chǎn)生的總行駛距離減少;(3)任務(wù)點(diǎn)之間、任務(wù)點(diǎn)和物流中心之間均存在可連通的道路,點(diǎn)間距離已知,并且不存在方向性差異;(4)配送車輛沒(méi)有時(shí)間窗和最大行駛距離等限制條件.

1.2 數(shù)學(xué)模型

設(shè)配送中心編號(hào)為 0,任務(wù)點(diǎn)編號(hào)為 1,2,…,n,車輛數(shù)為m;車輛容量為v;Dj、Rj分別為任務(wù)點(diǎn)j的送貨需求量和集貨需求量;D、R分別為任務(wù)點(diǎn)總的送貨需求量和集貨需求量;cij為任務(wù)點(diǎn)i和j之間的距離;xijk為車輛k從任務(wù)點(diǎn)i到j(luò)的次數(shù);yij為從任務(wù)點(diǎn)i到j(luò)時(shí)車輛即將卸載的貨物量(用于滿足任務(wù)點(diǎn)的送貨需求);zij為從任務(wù)點(diǎn)i到j(luò)時(shí)車輛已經(jīng)裝載的貨物量(已經(jīng)滿足的任務(wù)點(diǎn)的集貨需求).

完成任務(wù)所需要的車輛數(shù)為

式(2)為目標(biāo)函數(shù),即所有車輛行駛距離之和最小;式(3)和(4)確保每個(gè)任務(wù)點(diǎn)的送貨和集貨需求得到滿足;式(5)和(6)保證擬送出的貨物不再運(yùn)回物流中心,已收集的貨物也不再?gòu)奈锪髦行倪\(yùn)出;式(7)表明車輛進(jìn)出各個(gè)任務(wù)點(diǎn)的次數(shù)是平衡的;式(8)表示每輛車只從物流中心出來(lái)一次;式(9)保證車輛在執(zhí)行任務(wù)的途中不超載;式(10)和(11)分別是對(duì)決策變量的非負(fù)約束和整數(shù)約束.

2 啟發(fā)式算法

采用Mitra[9-10]解決VRPSPDP的思想,在已有算法的基礎(chǔ)上進(jìn)行改進(jìn).現(xiàn)以 FG表示車輛當(dāng)前承載的擬送出的貨物量,以RG表示車輛當(dāng)前承載的已收集的貨物量,以TC表示當(dāng)前所有車輛的行駛距離之和.問(wèn)題的求解可分為3個(gè)階段:第 1階段采用足夠的車輛 m1完成各個(gè)任務(wù)點(diǎn)需要滿載送貨和滿載集貨的任務(wù)量(如圖1(a)所示);第2階段采用剩余車輛 m2完成剩余的任務(wù)量,可對(duì)各個(gè)任務(wù)點(diǎn)的集送貨需求進(jìn)行拆分(如圖1(b)所示);第3階段求出任務(wù)點(diǎn)之間、任務(wù)點(diǎn)與物流中心之間的最短距離,并用其替代現(xiàn)有線路上兩點(diǎn)間的距離(如圖1(c)所示).在各階段運(yùn)算過(guò)程中,需不斷更新FG、RG和TC的值.

圖1 啟發(fā)式算法 3階段示意圖Fig.1 Scheme of three phases in heuristic algorithm實(shí)線箭頭表示車輛的行駛路線,虛線箭頭表示部分線路替換后車輛的行駛路線.

2.1 第1階段算法

第1階段派出m1輛車,其算法步驟如下:

(1)令i=1,m1=0,TC=0;

(2)考察任務(wù)點(diǎn)i,若Di≥v且Ri≥v,則派出一輛車滿載貨物訪問(wèn)該任務(wù)點(diǎn),卸下貨物并收集貨物,滿載返回物流中心,記錄車輛行駛路線,更新 Di、Ri、D、R、TC,i=i+1,m1=m1+1,否則,i=i+1;

(3)若i≤n,轉(zhuǎn)第(2)步;若i=n+1,考察所有任務(wù)點(diǎn),若存在任務(wù)點(diǎn)j滿足Dj≥v且Rj≥v,則令i=1,轉(zhuǎn)第(2)步,否則,進(jìn)入第2階段.

2.2 第2階段算法

第2階段派出m2輛車,其算法步驟如下:

(1)令m2=m-m1,若D＜R,則否則,FG-max=v;

(2)若D≠0或R≠0,則轉(zhuǎn)第(3)步,否則,進(jìn)入第3階段;

(3)若D≥FG-max,則FG=FG-max,否則, FG=D;

(4)若D＜R,轉(zhuǎn)第(5)步,否則,轉(zhuǎn)第(7)步;

(5)車輛從物流中心出發(fā),找到最大 Ri對(duì)應(yīng)的任務(wù)點(diǎn)i作為車輛訪問(wèn)的下一個(gè)任務(wù)點(diǎn),即令next-dest=i,更新FG、RG、Di、Ri、D、R、TC,如果有多個(gè)任務(wù)點(diǎn)符合要求,則按任務(wù)點(diǎn)編號(hào)等待下一輛車訪問(wèn);

(6)若RG≠v且R≠0,或FG≠0,則由當(dāng)前任務(wù)點(diǎn)出發(fā)訪問(wèn)最近的任務(wù)點(diǎn)i(i必須存在集貨或者送貨需求),令next-dest=i,根據(jù)FG、RG、Di、Ri的關(guān)系,將點(diǎn) i的集送貨需求量進(jìn)行合理拆分,并由車輛完成部分或全部集送貨任務(wù),更新FG、RG、Di、Ri、D、R、TC,如果有多個(gè)任務(wù)點(diǎn)與當(dāng)前任務(wù)點(diǎn)距離相同,則按任務(wù)點(diǎn)編號(hào)優(yōu)先訪問(wèn)集送貨需求剛好滿足的任務(wù)點(diǎn),重復(fù),直至RG=v或R=0,并且FG=0,車輛返回物流中心,記錄其行駛路線,轉(zhuǎn)第(2)步;

(7)車輛從物流中心出發(fā),找到最大Di對(duì)應(yīng)的任務(wù)點(diǎn)i作為訪問(wèn)的下一個(gè)任務(wù)點(diǎn),即令next-dest=i,更新FG、RG、Di、Ri、D、R、TC,如果有多個(gè)任務(wù)點(diǎn)符合要求,則按任務(wù)點(diǎn)編號(hào)等待下一輛車訪問(wèn);

(8)若FG≠0,或FG=0且R≠0,則由當(dāng)前任務(wù)點(diǎn)出發(fā)訪問(wèn)最近的任務(wù)點(diǎn)i(i必須存在集貨或者送貨需求),令next-dest=i,根據(jù)FG、RG、Di、Ri的關(guān)系,將點(diǎn) i的集送貨需求量進(jìn)行合理拆分,并由車輛完成部分或全部集送貨任務(wù),更新FG、RG、Di、Ri、D、R、TC,如果有多個(gè)任務(wù)點(diǎn)與當(dāng)前任務(wù)點(diǎn)距離相同,則按任務(wù)點(diǎn)編號(hào)優(yōu)先訪問(wèn)集送貨需求剛好滿足的任務(wù)點(diǎn),重復(fù),直至FG=0或R=0,車輛返回物流中心,記錄其行駛路線,轉(zhuǎn)第(2)步;

2.3 第3階段算法

第3階段實(shí)施部分線路替換,其算法步驟如下:

(1)對(duì)于點(diǎn)間距離不符合三角形各邊大小關(guān)系的情況,利用最短路徑算法,求出兩兩任務(wù)點(diǎn)之間、任務(wù)點(diǎn)和物流中心之間的最短距離;

(2)根據(jù)第(1)步的計(jì)算結(jié)果更新車輛行駛路線,保證各線路距離最短,算法結(jié)束.

3 算例分析

采用文獻(xiàn)[9-10]中的算例,比較文中算法(這里稱之為YH)與Mitra提出的兩種算法(SM和NH)的優(yōu)化效果.有 1個(gè)物流中心,19個(gè)任務(wù)點(diǎn),車輛容量為 10個(gè)單位,各任務(wù)點(diǎn)集送貨需求量見(jiàn)表 1第2、3列,根據(jù)點(diǎn)間距離分為兩種情況.

表1 3種啟發(fā)式算法及CPLEX計(jì)算結(jié)果Tab le 1 Results of three heuristic algorithms and CPLEX

續(xù)表1

續(xù)表1

情況1:所有任務(wù)點(diǎn)之間的距離相等,cij=10,?i,j(j＞i)并且cii=∞,?i;

情況2:所有任務(wù)點(diǎn)之間的距離不相等,cij=9+ j-i,?i,j(j＞i),并且cii=∞,?i.

在情況 1和情況 2下,由各個(gè)任務(wù)點(diǎn)的集送貨需求量變化和點(diǎn)間距的兩種情況搭配,可以分別形成 55個(gè)子問(wèn)題,共計(jì) 110個(gè)子問(wèn)題,將其分為 5個(gè)子問(wèn)題集合,采用 3種啟發(fā)式算法及優(yōu)化軟件包CPLEX(部分子問(wèn)題得到最優(yōu)值,部分子問(wèn)題運(yùn)行30min得到上界值)分別計(jì)算,其結(jié)果對(duì)比見(jiàn)表 1,其中最佳優(yōu)化結(jié)果用黑體字顯示.

由計(jì)算結(jié)果可以看出,文中提出的啟發(fā)式算法(YH)在大部分情況下優(yōu)于SM和NH,并且可以獲得最優(yōu)解,但對(duì)于第 3類子問(wèn)題集的優(yōu)化效果略差,在實(shí)際應(yīng)用中,可選擇NH作為檢驗(yàn)對(duì)比.

4 結(jié)語(yǔ)

以集送貨可拆分的車輛路徑問(wèn)題為研究對(duì)象,提出了一種新的啟發(fā)式算法.研究結(jié)果表明:新算法可以較好地求解VRPSPDP,尤其是在送貨需求總量大于集貨需求總量時(shí)其優(yōu)化效果很好.實(shí)際物流服務(wù)過(guò)程中,在車型選擇、貨物堆載位置等方面應(yīng)盡量考慮貨物裝卸混合帶來(lái)的問(wèn)題,以節(jié)約時(shí)間、提高服務(wù)效率.另外,文中研究尚未考慮車輛行駛線路長(zhǎng)度、任務(wù)點(diǎn)間距離的方向性差異、客戶對(duì)服務(wù)的時(shí)間窗、需求的隨機(jī)性等問(wèn)題,留待進(jìn)一步探討.

[1] Ropke S,Pisinger D.A unified heuristic for a large class of vehicle routing problemswith backhauls[J].European Journalof Operational Research,2006,171(3):750-775.

[2] Pisinger D,Ropke S.A general heuristic for vehicle routing problems[J].Computers＆Operations Research, 2007,34(8):2403-2435.

[3] Dror M,Trudeau P.Savings by split delivery routing[J]. Transportation Science,1989,23(2):141-145.

[4] Dror M,Laporte G,Trudeau P.Vehicle routing with split deliveries[J].Discrete Applied Mathematics,1994,50 (3):239-254.

[5] Mullaseril P A,Dror M,Leung J.Split-delivery routing heuristics in livestock feed distribution[J].The Journal of the Operational Research Society,1997,48(2):107-116.

[6] SiC,Bruce G,Edward W.The splitdelivery vehicle routing problem:app lications,algorithms,test problems,and computational results[J].Networks,2007,49(4):318-329.

[7] ArchettiC,Speranza M G,Hertz A.A tabu search algorithm for the split delivery vehicle routing prob lem[J]. Transportation Science,2006,40(1):64-73.

[8] Archetti C,Speranza M G,Savelsbergh M W P.An op tim ization-based heuristic for the split delivery vehicle routing problem[J].Transportation Science,2008,42(1):22-31.

[9] Mitra S.An algorithm for the generalized vehicle routing problem with backhauling[J].Asia-Pacific Journal of Operational Research,2005,22(2):153-169.

[10] Mitra S.A parallel clustering technique for the vehicle routing p rob lem with sp lit deliveries and pickups[J]. Journal of the Operational Research Society,2008,59 (11):1532-1546.