閔嘉寧，金 成,2，陸麗君,3

MIN Jia-ning1 , JIN Cheng1,2 , LU Li-jun1,3

（1.無(wú)錫太湖學(xué)院，無(wú)錫 214064；2.南京航空航天大學(xué) 管理學(xué)院，南京 210000；3.南京大學(xué) 管理學(xué)院，南京 210000）

0 引言

需求可拆分車(chē)輛路徑問(wèn)題（Split Delivery Vehicle Route Problem，SDVRP）是由Dror和Trudeau[1]于1989年首先提出了。在SDVRP中，到需求點(diǎn)的交貨可以進(jìn)行拆分、由多輛車(chē)完成送貨[1,2]。因此，VRP可以根據(jù)使用的車(chē)輛數(shù)量和行駛距離進(jìn)行優(yōu)化，SDVRP迅速成為VRP的重要分支，受到越來(lái)越多的關(guān)注[3]。

學(xué)者們提出了啟發(fā)式、元啟發(fā)式和多階段/混合啟發(fā)式算法對(duì)SDVRP進(jìn)行求解[3]。Dror和Trudeau[1,2]在假設(shè)每個(gè)i的di≤Q的情況下提出了局部搜索算法，引入了兩階段操作：第一階段，k-split，把對(duì)客戶的訪問(wèn)分至不同的路徑，每條路徑具有足夠的剩余容量，以滿足拆分客戶的需求。第二階段，路徑添加，考慮一個(gè)拆分客戶，將其從訪問(wèn)它的所有路線中刪除并創(chuàng)建一條僅含該客戶的新路徑。通過(guò)大量數(shù)值實(shí)驗(yàn)驗(yàn)證了：當(dāng)任務(wù)點(diǎn)需求量較大時(shí)，SDVRP的結(jié)果明顯優(yōu)于VRP。Archetti等人[4]提出了第一個(gè)禁忌搜索算法（Tabu Search algorithm，TSA），稱(chēng)為SPLITABU。實(shí)驗(yàn)表明，SPLITABU比Dror和Trudeau[1,2]算法更有效。Jin等人[5]提出了一種具有有效不等式的兩階段算法（Two-Stage with Valid Inequality，TSVI）：第一階段，客戶被劃分為集群。第二階段，在每一個(gè)集群中求解旅行商問(wèn)題（Traveling Salesman Problem，TSP），確定最小旅行距離。所有集群的最小旅行距離之和用于迭代更新目標(biāo)函數(shù)。Aleman等人[6]中，提出了一種兩階段算法。首先通過(guò)構(gòu)造方法生成初始解，然后應(yīng)用可變鄰域下降（Variable neighborhood descent，VND）方案來(lái)改進(jìn)初始解。在文獻(xiàn)[4,5]和文獻(xiàn)[7,8]提出的實(shí)例上對(duì)該方法進(jìn)行了測(cè)試。Aleman和Hill（2010）[9]對(duì)[6]構(gòu)建的兩階段算法進(jìn)行改進(jìn)，提出了一種用詞匯構(gòu)建方法進(jìn)行禁忌搜索，隨著搜索的進(jìn)行，解決方案集在不斷變化—在刪除不良解決方案時(shí)，會(huì)向集合添加好的解決方案。該方法能夠顯著改善[6]的結(jié)果。Liu等人[10]提出了k-means聚類(lèi)算法，并設(shè)計(jì)了兩種不同的求解方法：一種是先分組后路徑；另一個(gè)是先路徑后分組。通過(guò)實(shí)驗(yàn)比較這兩種方法，表明：先分組后路徑的方法表現(xiàn)出更好的性能。Wilck和Cavalier[11]采用先聚類(lèi)后路徑的兩階段來(lái)解決SDVRP。為了實(shí)現(xiàn)比較合理的聚類(lèi)，采用了三步操作：首先，選取離車(chē)場(chǎng)最遠(yuǎn)點(diǎn)，與車(chē)場(chǎng)組成一條初始路徑；然后，將平均剩余容量舍入到最近的整數(shù)；最后，逐步向已構(gòu)成的初始路徑中加入最鄰近的節(jié)點(diǎn)。他們的計(jì)算結(jié)果表明，在行程距離和計(jì)算速度方面，它在相同數(shù)據(jù)集下的性能較優(yōu)。溫真真[12]提出了一種三階段局域搜索算法。首先，采用GENIUS求解全客戶域的TSP路徑，按照車(chē)輛的容量把路徑分成若干個(gè)組，每個(gè)組都滿足客戶的負(fù)載量；然后，對(duì)每個(gè)點(diǎn)從它當(dāng)前的路徑中刪除，采用點(diǎn)再插入貪婪算法，按照送貨量拆分策略插入到最優(yōu)位置，迭代直至無(wú)新的優(yōu)化解；最后，通過(guò)擾動(dòng)、重復(fù)上述“刪除-再插入”直至得到最優(yōu)解。實(shí)驗(yàn)表明該算法可以獲得較好的結(jié)果。向婷等人[13]提出了一種先分組后路徑的兩階段算法，首先基于“最近”原則，通過(guò)設(shè)置分割閾值來(lái)限制一定范圍內(nèi)的車(chē)輛負(fù)荷，然后采用蟻群算法對(duì)路徑進(jìn)行優(yōu)化。石建力等人[14]提出了一個(gè)隨機(jī)客戶的SDVRP模型。采用改進(jìn)的分割插入算子和自適應(yīng)大鄰域搜索啟發(fā)式算法。Shi等人[15]提出了一種基于局部搜索的粒子群方法。設(shè)計(jì)了編碼解碼方法和最佳位置向量，對(duì)SDVRP方案進(jìn)行了優(yōu)化。

在上述研究中采用的各類(lèi)啟發(fā)式方法通常很耗時(shí)，而大多數(shù)精確算法僅可在小范圍內(nèi)求解SDVRP。為了解決這些問(wèn)題，在本研究中，提出了一種基于多重啟動(dòng)迭代掃描算法（Multi-Restart Iterative Sweep Algorithm，MRISA）的兩階段方法，首先，將所有客戶點(diǎn)按照車(chē)輛的最大容量劃分成組，采用適當(dāng)?shù)呢?fù)載率（Load Factor，LF）和閾值系數(shù)（Threshold Coefficient，TC）對(duì)已獲得分組進(jìn)一步微調(diào)優(yōu)化；然后采用禁忌搜索算法TSA優(yōu)化每組的路線?；鶞?zhǔn)數(shù)據(jù)的計(jì)算實(shí)驗(yàn)表明，該算法可以在幾秒鐘內(nèi)獲得近優(yōu)解。

1 問(wèn)題描述

在SDVRP中，車(chē)輛從車(chē)場(chǎng)出發(fā)，為客戶提供送貨服務(wù)，最后返回車(chē)場(chǎng)。當(dāng)車(chē)輛為顧客服務(wù)時(shí)，訪問(wèn)次數(shù)沒(méi)有限制，也就是說(shuō)，每個(gè)顧客可以由同一車(chē)輛或不同車(chē)輛訪問(wèn)多次。求解一組車(chē)輛路徑，在車(chē)輛容量限制下使用的車(chē)輛數(shù)最小并且總行駛里程最小。

SDVRP是一個(gè)無(wú)向圖G=（V，E），其中V是頂點(diǎn)集，E是邊集。假設(shè)在所考慮的SDVRP中有n個(gè)客戶和m輛車(chē)。客戶為i=（1，2，…，n），i=0表示車(chē)場(chǎng)，車(chē)輛為v=（1，2，…，m），車(chē)隊(duì)中的車(chē)輛是同型號(hào)的，車(chē)輛最大負(fù)載量為Q。車(chē)輛從車(chē)場(chǎng)出發(fā)為客戶送貨，客戶i的送貨需求為di，客戶i到j(luò)之間的送貨量為dij≥0；客戶i和j之間的距離為cij（cii=0，cij=cji，非負(fù)并滿足三角不等式）；當(dāng)滿足所有客戶的需求后，車(chē)輛返回車(chē)場(chǎng)。所使用的最小車(chē)輛數(shù)是其中[x]表示不小于x的最小整數(shù)。目標(biāo)函數(shù)是求解合適的路徑使得車(chē)輛行駛距離最短。決策變量是：

目標(biāo)函數(shù)表述如下：

式(1)表示每個(gè)客戶點(diǎn)必須至少訪問(wèn)一次。式(2)給出了流量守恒約束。式(3)給出了子路徑消除約束。式(4)表示只有當(dāng)車(chē)輛v訪問(wèn)客戶點(diǎn)i時(shí)，客戶點(diǎn)i才由車(chē)輛v提供服務(wù)。式(5)確保滿足所有客戶的需求。等式(6)確保每輛車(chē)不超過(guò)其最大負(fù)載能力。

2 提出的兩階段算法

該算法是一種基于先聚類(lèi)后路徑優(yōu)化策略的兩階段算法。在第一階段，使用MRISA將客戶劃分為集群，并確定每個(gè)分區(qū)中的分裂點(diǎn)。第二階段采用TSA進(jìn)行每個(gè)群集路線優(yōu)化。下面對(duì)提出的MRISA+TSA算法作詳細(xì)描述。

2.1 預(yù)處理

兩階段算法開(kāi)始之前，首先對(duì)客戶點(diǎn)di>Q的情況進(jìn)行預(yù)處理：重量Q可以由一輛車(chē)運(yùn)輸，該點(diǎn)剩余重量di=（di-Q）參與以下程序處理的。

2.2 MRISA

掃描算法是Gillett和Miller[16]在20世紀(jì)70年代提出的一種構(gòu)造式的啟發(fā)式算法。它本質(zhì)上將最近的客戶劃分為一個(gè)集群。為了滿足SDVRP的要求，本文修改了經(jīng)典掃描算法。采用確定分組的數(shù)量。使用多重啟動(dòng)迭代確定每個(gè)組的最后一個(gè)點(diǎn)和分割點(diǎn)。LF和TC用于微調(diào)優(yōu)化組分區(qū)。MRISA的過(guò)程詳細(xì)解釋如下。

步驟1：轉(zhuǎn)換坐標(biāo)系

1）創(chuàng)建極坐標(biāo)系。

2）將車(chē)場(chǎng)設(shè)置為極坐標(biāo)系的原點(diǎn)。

3）將連接原點(diǎn)和一個(gè)客戶點(diǎn)的線定義為角度0。

4）將所有客戶點(diǎn)轉(zhuǎn)換為該極坐標(biāo)系。

5）按升序?qū)蛻酎c(diǎn)的所有角度進(jìn)行排序。

步驟2：對(duì)客戶域進(jìn)行分區(qū)

步驟2.1：創(chuàng)建變量initialValue和storagePool。前者用于存儲(chǔ)初始值，后者用于存儲(chǔ)最佳值。

步驟2.2：第一次循環(huán)

1）將角度0的點(diǎn)設(shè)置為第一個(gè)起始點(diǎn)。

2）按順時(shí)針（或逆時(shí)針）方向逐漸掃描將掃到的點(diǎn)放入該組，直到的累積值（Cumulative Value，CV）超過(guò)Q。將最后一客戶點(diǎn)分成lp1和lp2；dlp1使當(dāng)前組的總負(fù)載等于Q。該組以lp1結(jié)尾。

3）從點(diǎn)lp2（需求dlp2）開(kāi)始下一組掃描。

4）重復(fù)(b)和(c)直到掃過(guò)最后一個(gè)點(diǎn)。

5）根據(jù)每個(gè)集群中點(diǎn)的空間分布計(jì)算總行程距離。

6）將總行程距離存入initialValue和storagePool.

步驟2.3：重新啟動(dòng)迭代

步驟2.3.1：順時(shí)針掃描

1）按順時(shí)針?lè)较蝽樞蛟O(shè)置每個(gè)點(diǎn)作為起始點(diǎn)。

2）執(zhí)行步驟2.2（b-e）。

3）將當(dāng)前總行程距離與storagePool中的值進(jìn)行比較。如果storagePool中的值較高，則將其替換為當(dāng)前值。

4）按客戶點(diǎn)升序執(zhí)行步驟2.3.1，直到到達(dá)最后一個(gè)點(diǎn)。

步驟2.3.2：逆時(shí)針掃描

1）以逆時(shí)針?lè)较蝽樞蛟O(shè)置每個(gè)點(diǎn)作為起始點(diǎn)。

2）執(zhí)行步驟2.3.1（b和c）。

3）按客戶點(diǎn)降序執(zhí)行步驟2.3.2，直到到達(dá)最后一個(gè)點(diǎn)。

步驟2.3.3：應(yīng)用負(fù)載率LF和閾值系數(shù)TC微調(diào)集群分區(qū)

1）通過(guò)微調(diào)負(fù)載率LF來(lái)調(diào)整集群分區(qū)，LF將Q更改為L(zhǎng)F×Q。

2）設(shè)置TC（例如，2或4），進(jìn)一步微調(diào)分區(qū)。

3）應(yīng)用LF×Q和TC以后，步驟2.2(b)將CV的計(jì)算細(xì)化為多個(gè)控制分支，如表1所示。

步驟3：輸出結(jié)果

1）輸出initialValue和storagePool中總行程距離。

2）輸出每個(gè)聚類(lèi)中的點(diǎn)。

3）輸出每個(gè)聚類(lèi)中的拆分點(diǎn)和相應(yīng)的拆分值。

2.3 路徑優(yōu)化

上述3.1和3.2執(zhí)行后，問(wèn)題域被分成幾個(gè)較小的組。每組中僅有一條路徑。采用TSA對(duì)每個(gè)組中的路徑優(yōu)化。TSA是Glover于1986年提出的元啟發(fā)式算法。TSA的過(guò)程描述如下。

步驟1：初始化

1）設(shè)置關(guān)鍵變量：禁忌長(zhǎng)度tabuLength，終止條件maxIter和禁忌表tabu[tabuLength]。

2）隨機(jī)生成初始路徑serialNum[customerNum]解決方案。

步驟2：計(jì)算serialNum的目標(biāo)函數(shù)值并將其賦值給變量bestValue。

步驟3：如果迭代次數(shù)等于maxIter，則終止程序并輸出最佳結(jié)果;否則，連續(xù)迭代，并執(zhí)行以下步驟。

步驟4：通過(guò)采用合適的選擇函數(shù)（例如，2-opts）生成當(dāng)前解決方案的rr鄰域。

步驟5：以非降序?qū)@些 rr鄰域進(jìn)行排序，并將該列表存儲(chǔ)在變量tempDist[rr]中作為候選隊(duì)列。

表1 CV的控制分支

步驟6：如果tempDist[0]

1）用tempDist[0]替換bestValue和currentBestValue。

2）將bestQueue，currentBestQueue和tabu替換為tempDist[0]的相應(yīng)對(duì)象。

3）返回步驟3。

否則，執(zhí)行步驟7。

步驟7：分析 tempDist[rr]對(duì)應(yīng)對(duì)象的Tabu屬性

1）用tempDist[i]的最佳值替換currentBestValu（假設(shè)第i個(gè)）。

2）將currentBestQueue替換為tempDist[i].的相應(yīng)對(duì)象。

步驟8：轉(zhuǎn)到步驟3。

3 案例分析

為驗(yàn)證所提算法的可行性和有效性，在基準(zhǔn)數(shù)據(jù)集上進(jìn)行了相關(guān)實(shí)驗(yàn)。案例來(lái)源于VRP Web中CVRPLIB[17]，案例研究1使用了Christofides和Eilon基準(zhǔn)數(shù)據(jù)集，案例研究2使用了Christofides，Mingozzi和Toth基準(zhǔn)數(shù)據(jù)集。實(shí)驗(yàn)采用C語(yǔ)言、在64位Intel?Core處理器、8GB內(nèi)存的Windows 7計(jì)算機(jī)上實(shí)現(xiàn)。

3.1 案例研究1

案例1數(shù)據(jù)集中有11個(gè)實(shí)例，如表1所示，實(shí)例名稱(chēng)“E-n21-k4”表示“Eil數(shù)據(jù)集，21點(diǎn)，4條路線”。對(duì)于每個(gè)實(shí)例，執(zhí)行兩個(gè)掃描操作：一個(gè)是順時(shí)針的，另一個(gè)是逆時(shí)針的。在每次操作中，記錄三個(gè)控制的結(jié)果，它們是：負(fù)載率LF控制，TC=2控制和TC=4控制。在每個(gè)控制分支列中，三個(gè)子列分別指示：負(fù)載率LF，初始循環(huán)中生成的初始值，以及MRISA的最佳值。表2列出了11個(gè)實(shí)例MRISA的實(shí)驗(yàn)結(jié)果。

表2的實(shí)驗(yàn)結(jié)果顯示，1）每個(gè)實(shí)例在逆時(shí)針操作或順時(shí)針操作的重啟迭代中，行程里程發(fā)生變化；2）在任何一種操作中最佳值始終低于初始值；3）最佳值既可以出現(xiàn)在逆時(shí)針操作中，也可以出現(xiàn)在順時(shí)針操作中；4）TC=4控制中的最佳值總是低于LF控制中相應(yīng)的最佳值；5）在少數(shù)情況下，TC=4控制中的最佳值略低于TC=2控制中的值；而大多數(shù)情況下，TC=4控制中的最佳值與TC=2控制中的最佳值相等。這表明MRISA是必要的，可行的和有效的。

表2 11個(gè)實(shí)例MRISA的實(shí)驗(yàn)結(jié)果

3.2 案例研究2

案例2數(shù)據(jù)集中有6個(gè)實(shí)例，實(shí)例名稱(chēng)“v1-50-5”表示“vrpnc1 dataset，50 points，5條路徑”。案例研究2比較了本文所提出的算法（MRISA+TSA）與基于正常掃描算法（Normal Sweep Algorithm，NSA）+禁忌算法的兩階段算法（NSA+TSA）以及SPLITABU[4]在案例2數(shù)據(jù)集上的執(zhí)行結(jié)果。各種算法中記錄了總行駛里程、計(jì)算所消耗的時(shí)間，以及行駛距離與MRISA+TSA算法的相對(duì)偏差率（Relative Deviation Percentage，RDP），表中簡(jiǎn)稱(chēng)為RDP(1)，如表3所示。其中，RDP(1)=（DisMRISA+TSA-Dis所選算法）/Dis所選算法。

表3的實(shí)驗(yàn)結(jié)果顯示：1）SPLITABU 和 ISA+TSA的行駛里程RDP除了實(shí)例“v11-120-7”外其余的都小于6%；這表明MRISA+TSA對(duì)除了實(shí)例“v11-120-7”外那些具有物理位置分散分布（如圖1所示，紅色為車(chē)場(chǎng)）的實(shí)例可以獲得近優(yōu)解；2）NSA+TSA和 MRISA+TSA的行駛里程RDP(1)均小于0，說(shuō)明MRISA+TSA的行駛里程小于NSA+TSA的行駛里程，MRISA是必要的，可行的和有效的；4）MRISA+TSA的計(jì)算時(shí)間比SPLITABU低的多，最大的計(jì)算時(shí)間小于15s。

表3 案例2的實(shí)驗(yàn)結(jié)果

圖1 客戶點(diǎn)圍繞車(chē)場(chǎng)分散分布

圖2 客戶點(diǎn)圍繞車(chē)場(chǎng)集群分布

但是，表3顯示SPLITABU在實(shí)例“v11-120-7”的行駛里程的RDP(1)很大，為20.9%。這說(shuō)明MRISA算法在這個(gè)實(shí)例上無(wú)效。實(shí)例“v11-120-7”的地理分布特征是所有的點(diǎn)都成集群形狀分布在車(chē)場(chǎng)周?chē)?，如圖2(a)所示“v11-120-7”。為了適應(yīng)這個(gè)特征，我們采用了“先聚群再掃描”的策略。首先，采用“Max-Min dis”[18]方法對(duì)客戶聚群；然后再對(duì)每個(gè)聚群采用MRISA +TSA，即三階段方法“Max-min dis”+MRISA+TSA。

根據(jù)“Max-Min dis”方法的原則，首先，按照最遠(yuǎn)距離（Maximum distance）原則，選擇相距最遠(yuǎn)的點(diǎn)作為聚群中心，使得初始數(shù)據(jù)集的分割效率較高。然后，按照最近距離（Minimum distance）原則，將所有距離最近的點(diǎn)就近歸入聚群組[18]，如圖2(a)所示，紅色為車(chē)場(chǎng)，深紅色的點(diǎn)為各聚群中心；最左邊兩個(gè)聚群連在一起，為了區(qū)別、其中一個(gè)聚群用綠色點(diǎn)表示。如果每個(gè)聚群的總需求量≤α×Q（α>1正整數(shù)），MRISA +TSA可以在各聚類(lèi)中執(zhí)行；如果某聚類(lèi)的總需求量>α×Q（α>1正整數(shù)），通過(guò)“推出”、“拉入”操作調(diào)整各聚群的需求量，使各聚群的總需求量≤α×Q（α>1正整數(shù)），然后再在各聚類(lèi)中執(zhí)行MRISA +TSA。

算法“Max-min dis”+MRISA+TSA在實(shí)例“v11-120-7”上的執(zhí)行結(jié)果見(jiàn)“Max-min dis”+MRISA+TSA列的“v11-120-7”行（最右列黃色）。結(jié)果表明采用算法“Max-min dis”+MRISA+TSA后行駛里程下降了。行駛里程與SPLITABU和 NSA+TSA行駛里程相比的RDP；2）分別為6.9%和-17.6%，分別比RDP(1)下降了約14%and 10.8%；而采用“Max-min dis”+MRISA+TSA算法后的行駛里程比MRISA+TSA算法也下降了，RDP(2)為-11.6%。其中，RDP(2)=（Dis“Max-mindis”+MRISA+TSA-Dis所選算法）/Dis所選算法。

為了進(jìn)一步驗(yàn)證三階段算法在具有與實(shí)例“v11-120-7”類(lèi)似地理分布特征的實(shí)例上的執(zhí)行效果，本文采用“Max-min dis”+MRISA+TSA算法在實(shí)例“v12-100-10”（如圖2(b)所示，紅色為車(chē)場(chǎng)）上執(zhí)行（SPLITABU[3]無(wú)執(zhí)行結(jié)果）。執(zhí)行結(jié)果表明采用“Max-min dis”+MRISA+TSA算法后的行駛里程下降了，NSA+TSA與MRISA+TSA的RDP(2)分別為-20.1%和-10.1%，NSA+TSA的RDP(2)比RDP(1)下降了8.9%。

實(shí)驗(yàn)結(jié)果表明三階段算法“Max-min dis”+MRISA+TSA對(duì)于客戶點(diǎn)圍繞車(chē)場(chǎng)集群分布的實(shí)例比兩階段的算法MRISA+TSA有效的多。

4 結(jié)論

針對(duì)SDVRP，本文提出了一種基于構(gòu)造啟發(fā)式的兩階段算法。第一階段，采用多重啟動(dòng)迭代策略在逆時(shí)針和順時(shí)針?lè)较驈拿奎c(diǎn)開(kāi)始掃描客戶域。根據(jù)車(chē)輛容量將客戶域劃分為子域。負(fù)載率LF和TC用于微調(diào)分區(qū)、拆分點(diǎn)和拆分負(fù)載。第二階段，TSA用于優(yōu)化每個(gè)子域中的路徑，以實(shí)現(xiàn)最小的總運(yùn)輸距離。

數(shù)值實(shí)驗(yàn)是在CVRPLIB基準(zhǔn)數(shù)據(jù)集上進(jìn)行的。計(jì)算結(jié)果表明，MRISA多重啟動(dòng)迭代策略是必要的，并且該算法在大多數(shù)測(cè)試數(shù)據(jù)集實(shí)例中為SDVRP提供了可行有效的解決方案。所提出的算法在數(shù)據(jù)集1的11個(gè)實(shí)例中有7個(gè)獲得近似最優(yōu)解（RDP<5%），數(shù)據(jù)集2的6個(gè)實(shí)例中有5個(gè)獲得近似最優(yōu)解（RDP<6%）。另外，數(shù)據(jù)集1和2計(jì)算所耗的最大時(shí)間分別是3s和15s，他們大大的低于所評(píng)價(jià)的其他算法。

進(jìn)一步實(shí)驗(yàn)表明：兩階段MRISA+TSA方法對(duì)客戶地理位置分散分布的實(shí)例是有效的；而三階段的“Maxmin dis”+MRISA+TSA方法則對(duì)客戶地理位置集群分布的實(shí)例更加有效。