基于多重啟動迭代掃描的需求可拆分車輛路徑問題

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

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

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

0 引言

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

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

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

1 問題描述

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

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

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

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

2 提出的兩階段算法

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

2.1 預處理

兩階段算法開始之前，首先對客戶點di>Q的情況進行預處理：重量Q可以由一輛車運輸，該點剩余重量di=（di-Q）參與以下程序處理的。

2.2 MRISA

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

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

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

2）將車場設置為極坐標系的原點。

3）將連接原點和一個客戶點的線定義為角度0。

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

5）按升序?qū)蛻酎c的所有角度進行排序。

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

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

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

1）將角度0的點設置為第一個起始點。

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

3）從點lp2（需求dlp2）開始下一組掃描。

4）重復(b)和(c)直到掃過最后一個點。

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

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

步驟2.3：重新啟動迭代

步驟2.3.1：順時針掃描

1）按順時針方向順序設置每個點作為起始點。

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

3）將當前總行程距離與storagePool中的值進行比較。如果storagePool中的值較高，則將其替換為當前值。

4）按客戶點升序執(zhí)行步驟2.3.1，直到到達最后一個點。

步驟2.3.2：逆時針掃描

1）以逆時針方向順序設置每個點作為起始點。

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

3）按客戶點降序執(zhí)行步驟2.3.2，直到到達最后一個點。

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

1）通過微調(diào)負載率LF來調(diào)整集群分區(qū)，LF將Q更改為LF×Q。

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

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

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

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

2）輸出每個聚類中的點。

3）輸出每個聚類中的拆分點和相應的拆分值。

2.3 路徑優(yōu)化

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

步驟1：初始化

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

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

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

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

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

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

表1 CV的控制分支

步驟6：如果tempDist[0]

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

2）將bestQueue，currentBestQueue和tabu替換為tempDist[0]的相應對象。

3）返回步驟3。

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

步驟7：分析 tempDist[rr]對應對象的Tabu屬性

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

2）將currentBestQueue替換為tempDist[i].的相應對象。

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

3 案例分析

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

3.1 案例研究1

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

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

表2 11個實例MRISA的實驗結(jié)果

3.2 案例研究2

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

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

表3 案例2的實驗結(jié)果

圖1 客戶點圍繞車場分散分布

圖2 客戶點圍繞車場集群分布

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

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

算法“Max-min dis”+MRISA+TSA在實例“v11-120-7”上的執(zhí)行結(jié)果見“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所選算法。

為了進一步驗證三階段算法在具有與實例“v11-120-7”類似地理分布特征的實例上的執(zhí)行效果，本文采用“Max-min dis”+MRISA+TSA算法在實例“v12-100-10”（如圖2(b)所示，紅色為車場）上執(zhí)行（SPLITABU[3]無執(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%。

實驗結(jié)果表明三階段算法“Max-min dis”+MRISA+TSA對于客戶點圍繞車場集群分布的實例比兩階段的算法MRISA+TSA有效的多。

4 結(jié)論

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

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

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