集送貨可拆分車輛路徑問題的兩階段構造啟發式方法1

金成成，閔嘉寧

（無錫太湖學院，無錫 214064）

0 引言

我國是一個能源消耗和碳排放大國，物流運輸是碳排放的大戶之一。在“雙碳目標”下，車輛路徑問題 (vehicle routing problem，VRP) 在現代物流運輸中起著更為重要的作用。車輛路徑優化對提高車輛負載率、削減運輸車輛的使用數量、降低運輸距離、減少碳排放以及相應的環境破壞具有相當大的影響[1]。

集送貨一體的VRP (VRP with simultaneous delivery and pickup，VRPSDP) 可以在送貨的同時完成集貨 (回收)，減少由于車輛回程放空引起的燃油消耗，從而降低運輸成本，增加企業收益，因此，近年來VRPSDP已成為VRP中的研究熱點。隨著經典VRPSDP中每個客戶可以被訪問一次且僅一次的約束放寬，每個客戶可以被多次訪問，客戶的配送和集貨需求可以被拆分，從而提高了車輛的負載率、減少使用的車輛數并節省行駛路徑[2]。因此，求解需求可拆分VRP受到越來越多的關注。有兩種拆分需求：一是拆分配送需求，相應的問題稱為配送可拆分VRP (Split Delivery VRP，SDVRP)，二是拆分集貨和送貨雙需求，相應的問題稱為集送貨可拆分VRP (split VRP with deliveries and pickups，VRPSPDP)。

SDVRP最早是由Dror和Trudeau[3]于1989年提出的，在SDVRP中，一個點的送貨需求可以由任意數量的車輛完成。學者們開發了許多算法來求解SDVRP，研究主要集中在通過采用啟發式和精確求解方法來解決這個問題[4～12]。

VRPSPDP則由Mitra[13]于2005年提出，采用一種混合整數線性規劃模型來描述該問題，并提出一種低成本的插入準則、使用車輛最少的構造啟發式路徑方法進行求解；2008年[14]其又提出了更優的并行聚類技術和新的路徑構造啟發式算法。王科峰[15]為無車輛數限制的VRPSPDP設計了兩個構造啟發式算法（最遠節點需求拆分算法和競爭決策算法），以及具有車輛數量限制的VRPSPDP的兩個構造啟發式算法 (最遠節點全拆分算法和最近節點全拆分算法)。Yin等人[16]提出了一個具有兩個特殊前提條件的VRPSPDP數學模型，這兩個條件分別是：最大行程距離約束以及每個客戶的需求只能拆分一次的限制。Wang等人[17]開發了一種兩階段啟發式方法，將初始啟發式算法和混合啟發式算法相結合，求解VRPSPDP問題。Qiu等人[18]設計了一個基于弧的混合整數模型，并采用分支-切割算法進行求解。

迄今為止，研究人員主要關注SDVRP，有較多的研究成果；而對VRPSPDP的研究較少，解決方案不夠全面，或附加了一些限制條件，或計算所需時間較長。因此，在VRPSPDP的優化效果方面仍存在相當大的提升空間。鑒于此，本文提出了一種基于“先聚類后路徑”策略的兩階段方法：第一階段采用一種擴展的多重啟動迭代掃描算法和微調系數對客戶進行聚類，確定拆分點和拆分值，將問題域分成若干個子域；第二階段采用改進的節約算法，最小化各子域的的運輸距離和使用車輛。使用重構的Solomon基準數據集來評估所提出算法的可行性和有效性，并與VRPSDP的計算結果進行比較，說明VRPSPDP的優越性。

本文的其余部分安排如下。第2節描述了VRPSPDP。第3節詳細描述了兩階段啟發式方法。第4節介紹并討論了使用基準數據集獲得的計算結果。最后，第5節對研究作了總結并指出進一步研究的方向。

1 問題描述

本文所說的VRPSPDP是指：問題域中有n個客戶和 m輛車，所有車輛都是同一型號。每輛車k|k=（1，2，...，m）裝載了車輛行駛中容量Q所限的配送貨物∑ni=1di≤Q離開車場，沿途為客戶i，j|i，j=（0，1，2，...，n）（0是車場）送貨di并同時集貨（回收）pi，最后攜帶容量所限的集貨返回車場。客戶i和j之間的距離為cij，客戶自身不存在環路cii=0，且路徑無向cij=cji?？蛻鬷和j之間的送貨量0≤dij≤Q，客戶i和j之間的集貨量0≤pij≤Q。使用的最小車輛數是[max(Σni=1di，Σni=1pi)/Q]，其中[x]表示等于或大于x的最小整數[18，19]。每位客戶可能同時具有集/送貨需求，其中任何一個都可能超過車輛容量。每位客戶的配送和集貨都可以進行拆分；也就是說，每個客戶可能被多個車輛訪問或者被同一車輛訪問多次。車輛k從客戶i行駛到j，則xijk=1；否則xijk=0?？蛻鬷由車輛k服務，則yik=1；否則yik=0。為簡單起見，本文假設沒有時間窗口限制，也沒有最大行駛時間和距離的限制。求解的目標是最小化總行駛距離[13，14]。

其中：

式(1)是目標函數，表示最小化總行駛距離。

式(2)和式(3)是客戶需求約束：確保通過多次訪問滿足客戶j的配送/收集需求。

式(4)和式(5)是車輛裝載約束：確保一次行駛中的車輛的配送/收集量不超過車輛容量。

式(6)是車輛裝載實時約束：由于在各客戶節點處可能有卸貨和裝貨，車載量是動態、上下波動的，因此，為確保一次行駛中在任何節點處的配送/收集的總裝載不超過車輛容量，必須隨時檢測車載約束?？蛻艄濣cθq（含節點θ）之前的集貨數量和客戶節點θ之后的配送數量（從節點θ+1開始）沿車輛k的路線的總和不能超過車輛容量。

式(7)和式(8)是車場貨物類型約束：確保沒有送貨進入車場，并且沒有集貨來自車場。

式(9)是車輛出入守恒約束：確保到達客戶位置j的車輛也離開該位置。

式(10)是車場出入約束：表明每個車輛每次行駛僅駛入/駛出車場一次。

2 兩階段方法

本文基于“先聚類后路徑”策略提出了一種兩階段方法來求解VRPSPDP問題。第一階段，采用擴展的多重啟動迭代掃描算法（Multi-Restart Iterative Sweep Algorithm，MRISA）對客戶進行聚類，確定拆分點和拆分的值；第二階段，采用經過改進、符合VRPSDP要求的節約算法（Clarke-Wright，C-W），優化行駛距離。

2.1 第一階段

掃描算法是Gillett和Miller[19]提出的一種構造啟發式算法，本質上是在滿足一定前提條件下將距離最近的客戶集群到一個分區中。通過多重迭代執行，可以找到最優的分區。

掃描算法是在極坐標下執行的，所以首先對直角坐標系下的空間域以車場為原點轉換成極坐標系，然后按升序對客戶點的所有角度進行排序，并設置變量組optimal存儲各分區的客戶點 (集送貨值)、拆分點 (拆分值) 以及最佳距離[20]。

2.1.1集送貨掃描算法

集送貨掃描算法 (Sweep Algorithm for Delivery and Pickup，SA-DP) 是對基本的Gillett和Miller掃描算法的改進，使之應用于客戶具有集送貨都不可拆分的情況下。在執行SA-DP之前，需要檢查每個點的送貨需求di和集貨需求pi。如果di，pi≥Q，則單獨派送數量Q，剩余部分參與SA-DP執行，對客戶域進行分區。

步驟1：選擇角度0°作為起始點。

步驟2：按順時針將點掃描進入初始分區，直到（max(Σlpi=1di，Σlpi=1pi)）≥Q：

1）如果Σii=1di=QandΣii=1pi=Q，i就作為當前M分區的最后一個點（Last Point，lp），當前分區的最大累積值 (Maximum Cumulative Value，MCV) MCVlpd=Σii=1di=Q，MCVlpp=Σii=1pi=Q。

2）如果Σii=1di=QandΣii=1pi=Q，i就作為當前分區的最后一個點lp，當前分區的MCVlpd=Σii=1di=Q，MCVlpp=Σii=1pi。

3）如果Σii=1pi=QandΣii=1di＜Q，i就作為當前分區的最后一個點lp，當前分區的MCVlpd=Σii=1pi=Q，MCVlpd=Σii=1di。

4）如果Σii=1di＞QandΣii=1pi＜Q，i的前一個點（i-1）就作為當前分區最后一個點lp，當前分區的MCVlpd=Σii=1di，MCVlpp=Σi-1i=1pi。

5）如果Σii=1pi＞QandΣii=1di＜Q，（i-1）就作為當前分區最后一個點lp，于是當前分區的最大累積值MCVlpp=Σi-1i=1pi，MCVlpd=Σi-1i=1di。

6）如果Σii=1di＞QandΣii=1pi＞Q，（i-1）就作為當前分區的最后一個點lp，當前分區的MCVlpd=Σi-1i=1di，MCVlpp=Σi-1i=1pi。

終止當前分區。

步驟3：從lp的下一個點出發開始下一個分區的掃描，重復步驟2。

步驟4：重復步驟2～3，直至最后一個客戶點。

步驟5：終止本次掃描，將各分區的客戶點 (集送貨值)、拆分點 (拆分值) 以及最佳距離存入變量組optimal。

2.1.2 集送貨可拆分掃描算法

針對集送貨需求都可拆分，我們對SA-DP進行了改進，形成了集送貨可拆分的掃描算法 (Sweep Algorithm for Delivery and pickup split，SA-DP-Split)。在這種情況下，每位客戶可能同時具有集送貨需求，其中任何一個都可能超過車輛容量。

步驟1：選擇角度0°作為起始點。

步驟2：按順時針將點掃描進入初始分區，直到（max(Σlpi=1di，Σlpi=1pi））≥Q：

1）如果Σii=1di=QandΣii=1pi=Q，i就作為當前分區的最后一個點lp，當前分區的MCVlpd=Σii=1di=Q，MCVlpp=Σii=1pi=Q，i+1是下一個分區的起始點。

2）如果Σii=1di=QandΣii=1pi＜Q，i就作為當前分區的最后一個點lp，當前分區的MCVlpd=Σii=1di=Q，MCVlpp=Σii=1pi；i+1是下一個分區的起始點。

3）如果Σii=1pi=QandΣii=1di＜Q，i就作為當前分區的最后一個點lp，當前分區的MCVlpd=Σii=1pi=Q，MCVlpd=Σii=1di；i+1是下一個分區的起始點。

4）如果Σii=1di＞QandΣii=1pi＜Q，i就作為當前分區最后一個點lp，分裂lp為lp1和lp2，最大累積值MCVlp1d=Q，CVlp2d=Σii=1di-Q，MCVlp1p=Σii=1pi，MCVlp2p=0；lp2是下一個分區的起始點。

5）如果Σii=1pi＞QandΣii=1di＜Q，i就作為當前分區最后一個點lp，分裂lp為lp1和lp2，最大累積值MCVlp1p=Q，MCVlp2p=Σii=1pi-Q，MCVlp1d=Σii=1di，MCVlp2d=0；lp2是下一個分區的起始點。

6）如果Σii=1di＞QandΣii=1pi＜Q，i就作為當前分區的最后一個點lp，分裂lp為lp1和lp2，最大累積值MCVlp1d=Q，MCVlp1p=Q，MCVlp2d=Σii=1di-Q，MCVlp2p=Σii=1pi-Q；lp2是下一個分區的起始點。

終止當前分區。

步驟3：從下一個分區的起始點出發開始下一個分區的掃描，重復步驟2。

步驟4：重復步驟2～3，直至最后一個客戶點。

步驟5：終止本次掃描，將各分區的客戶點 (集送貨值)、拆分點 (拆分值) 以及最佳距離存入變量組optimal。

2.1.3 微調系數

SA-DP-Split中，當（Σii=1di＞QandΣii=1pi＜Q) 或者（Σii=1di＜QandΣii=1pi＞Q) 時，i+1就是下一個分區的起始點，而無論Σii=1pi或Σii=1di與Q相差多少。這樣可能會影響車輛的負載率，造成使用的車輛數增加。為此，我們引入了系數coef對‘差多少’進行控制，形成增強的SA-DP-Split (SA-Enhanced-DP-Split，SA-E-DPSplit)：如果Σii=1xi＜coef·Q，(此處的x表示d或p)，則x 不在該點終止分區、繼續掃描；如果Σii=1xi≥coef·Q，則x在該點終止分區、停止掃描。這就意味著d和p可以有各自獨立的分區終止點。以步驟2的2）為例：

步驟2：按順時針將點掃描進入初始分區，直到（max(Σlpi=1di，Σlpi=1pi））≥Q：

1) 如果Σii=1di=QandΣii=1pi＜coef·Q，i就作為當前分區d的最后一個點lp，當前分區的最大累積值MCVlpd=Σii=1di=Q，MCVlp=Σii=1pi；i+1是下一個分區累計d的起始點，而p繼續掃描并累計MCVl+1p=Σi+1i=1pi。

2) 如果Σii=1di=QandΣii=1pi≥coef·Q，i就作為當前分區d和p的最后一個點lp，當前分區的最大累積值MCVlpd=Σii=1di=Q，MCVlpp=Σii=1pi；i+1是下一個分區的起始點。

2.1.4 多重迭代

多重迭代 (Multi Restart Iteritive，MRI) 地執行SA-DP/SA-DP-Split/SA-E-DP-Split，操作分別成為MRISA for DP/MRISA for DP-Split/MRISA for E-DP-Split：

步驟1：依次以0o～360o中各客戶點為起始點執行SADP/SA-DP-Split/E-SA-DP-Split，并與optimal中的最佳距離比較，存入最佳值。

步驟2：依次以360o～0o中各客戶點為起始點執行SADP/SA-DP-Split/E-SA-DP-Split，并與optimal中的最佳距離比較，存入最佳值。

步驟3：提取optimal中的最佳客戶點 (集送貨值)、拆分點 (拆分值) 以及最佳距離，并終止操作。

2.2 第二階段

執行第一階段的操作后，每個子分區中都只有一條路線，每個客戶點都有集送貨需求。因此，問題變成了VRPSDP。采用改進的C-W算法(Modified C-W，M-C-W)滿足VRPSDP要求，改進的C-W算法的過程如下。

步驟1：形成初始解集L={Li}，Ai∈{1，2，…，n}，其中Li表示直接集送貨點i。

步驟2：計算距離節省度Δcij=c0i+c0j-Δcij。對Δcij（i，j=1，2，...，n）進行降序排序，得到Dcij。

步驟3：構造新的路徑集L'0=φ，并設置初始送貨/集貨需求裝載量R'0=0。

步驟4：從頂部到底部掃描Dcij并終止在底部。

步驟5：在掃描中根據以下判別條件尋找每個點對（i，j）的合并可能性。

如果i是路徑的末端，則將點j合并在點i后面。

如果i是路線的開始，則在點i前合并點j。

如果j是路線的末端，則將點i合并在點j后面。

如果j是路線的開始，則在點j之前合并點i。

4) 車輛的總裝載隨著沿路徑的裝載增加或減少而波動，因此必須檢查每個點的裝載約束：如果當前路徑的裝載量滿足以下條件，則轉到下一個點對；否則，刪除步驟5中的所有操作并返回步驟4：

3 案例研究

為了驗證所提出的兩階段方法在減少行駛距離、降低運輸車輛數量和提高裝載率方面的可行性和有效性，我們選用了VRP Web Solomon數據集中25、50和100個客戶的數據[21]。但是，Solomon數據集不能直接用于VRPSPDP，因為它們不包括集貨需求數據。通過合并兩個數據集來構建完整的新數據集：一個作為送貨需求而另一個作為集貨需求。例如，新構建的原始數據集CR101中的送貨需求和集貨需求分別是由原始數據集C101中的送貨需求和原始數據集R101的送貨需求構成的。同時，進一步增大集送貨值占車輛容量的比例：保留數據集中各點的地理位置數據不變，對每個奇數點，給送貨值加0.75·Q并給集貨值加0.2·Q；對每個偶數點，給送貨值加0.2·Q并給集貨值加0.75·Q，使得新構建數據集的集送貨值占車輛容量在20.5%和95%之間。驗證是在64位Windows 7計算機上使用C實現的，該計算機具有Intel?Core處理器2.50 GHz和8GB內存。

在新構建的數據集上分別執行MRISA for DP/DPSplit/E-DP-Split+M-C-W（簡稱為DP、DP-Split和E-DP-Split），結果如表1所示。表中距離減少ΔDist.%計算如下。

表1 在新構建的數據集上執行的結果

結果表明，E-DP-Split相比其他兩個算法 (DP-Split和DP) 具有明顯的優勢：

E-DP-Split比DP算法的距離減少ΔDist.%在30.65% 和38.35%之間，平均值為33.91%。DP-Split比DP算法的距離減少ΔDist.%在11.66%和26.85%之間，平均為19.89%。E-DP-Split比DP-Split的距離減少ΔDist.%在12.50%和24.23%之間，平均為17.38%。行駛距離的減少將直接降低運輸成本。

DP情況下的路徑數等于點數，即一條路徑對應一個點。E-DP-Split情況下的路徑數比DP下降約41%、比DPSplit下降了約11%；DP-Split比DP下降約34%。路徑數的下降意味著車輛使用數量、車輛啟動費用和人力成本的下降，所有這些都將顯著降低運輸成本。(說明：由于空間限制，無法在表1中標明ΔRt.%；計算公式類似于式(11)、式(12)和式(13))。

三種算法的平均負載率Load Rate分別為0.96、0.89和0.57。E-DP-Split比DP上升約68.4%，比DP-Split上升約7.9%；DP-Split比DP上升約56.1%。(說明：由于空間限制，無法在表1中標明ΔLR.%；計算公式類似于式(11)、式(12)和式(13))。

車輛行駛產生的路線形狀像圍繞車場周圍的花瓣，客戶點的拆分通常發生在子域的開始或結束。

E-DP-split情況下，兩個相鄰路徑之間可能有兩個分裂點：一個點是送貨值拆分，另一個點是集貨值拆分。

4 結語

本文基于“先聚類后路徑”策略開發了求解VRPSPDP的數學模型的兩階段構造啟發式方法。第一階段，采用擴展的多重啟動迭代掃描式算法以及微調系數 coef將客戶域劃分為若干個子域，并確定拆分點和拆分值。第二階段，采用改進的C-W節約算法，按照路徑優化的原則，檢測每個客戶點動態車載量，確定行駛路徑。在Solomon原始數據集的基礎上，通過重構使之適合VRPSPDP的需求，驗證所提出方法的可行性和有效性，并與VRPSDP進行了分析比較。實驗結果表明：

1）提出的兩階段算法顯著減少了VRPSPDP的總行駛距離、車輛使用數量并提高了平均裝載率。

2）車輛行駛路徑圍繞著車場周圍形狀像花瓣，而且客戶拆分經常發生在子域的開始或結束處。

3）在重構的數據集上執行E-DP-Split+M-C-W比執行DP+M-C-W算法顯示出明顯的優勢：行駛距離平均減少33.91%，使用的車輛數量平均下降約41%，平均裝載率上升約68.4%。

4）在執行E-DP-Split+M-C-W時，兩條相鄰路徑之間可能有兩個分裂點：一個點是送貨值拆分，另一個點是集貨值拆分。

本文在集送貨可拆分的車輛路徑優化上作了初步探索嘗試，今后還將在優化的算法上進一步深入研究，以期獲得更優的結果；擴展本文的研究到可分割的 (divisble) 集送貨VRP[22，23]，研究多種拆分案例對優化結果的影響。