基于密度聚類構建物流配送問題的毀滅移除算法

陽 旺，何國超，吳 雁

(中南大學 信息科學與工程學院，長沙 410083)

(*通信作者電子郵箱yangwang@csu.edu.cn)

基于密度聚類構建物流配送問題的毀滅移除算法

陽 旺*，何國超，吳 雁

(中南大學 信息科學與工程學院，長沙 410083)

(*通信作者電子郵箱yangwang@csu.edu.cn)

研究多車型大規模物流配送問題，針對企業配送門店規模大且聚集的特點，在自適應大規模鄰域搜索(ALNS)框架下提出一種新的鄰域映射方式：基于密度聚類的毀滅移除算法。ALNS包含毀滅與重建兩個階段，通過不斷對當前解進行破壞和重建得到更好解。在毀滅階段，隨機選擇一條路線進行密度聚類得到簇集合，然后按簇對路線上的門店進行移除；重建階段隨機選擇貪婪插入法或Regret-2插入法將移除的門店插入到合適的路線上得到新配送方案。通過國際基準測試案例驗證了所提算法的有效性，與已有算法對比，基于密度聚類的毀滅移除算法的ALNS算法求解結果比案例已知最優解平均誤差更低，求解質量更優；應用于實際場景中，該算法能在有限時間內求得較好的配送方案。

新零售；車輛路徑問題；固定車輛數的多車型車輛路徑問題；毀滅與重建；密度聚類；自適應大規模鄰域搜索

0 引言

隨著電子商務的發展，未來將進入“新零售”時代，線上線下和物流結合在一起，產生新的零售方式[1]。在“新零售”方式下，物品由企業統一配送到各個門店(便利店、超市等)，客戶的需求由離客戶最近的門店進行服務，以實現“當日達”，甚至“小時達”，能極大地提高客戶的物流體驗。對企業而言，門店數量將增加，門店每天需求量將急速增加，如何使用一組車輛對大規模門店進行貨物配送，如圖1所示，是亟待解決的問題。

大規模門店物流配送本質上是解決一個車輛路徑問題(Vehicle Routing Problem, VRP)，最早由學者Dantzig等于1959年提出[2]，指一組車輛從物流總倉出發對一系列在地理上無規律分布的客戶進行服務，要求每個客戶的需求必須被滿足且只能由一輛車提供服務，每輛車的路線開始于物流總倉，并且最終結束于物流總倉。VRP已被證明是NP-hard問題，使用動態規劃法、分支界限法等精確算法只適用解決100個客戶規模以內的VRP[3]，不適用于大規模物流配送問題。根據約束條件不同，如車輛最大容量約束、門店服務時間窗約束等，可將VRP分為不同類型的擴展問題[3]。

圖1 物流配送問題Fig. 1 Logistics distribution problem

在本文研究的企業案例中，企業擁有8 000多家門店，配送車隊擁有多達37種車型。目前企業仍處于人工調度派車階段，線上和線下的訂單分開處理，存在車輛空載率高、配送成本偏高、客戶物流體驗差等問題，制約了企業的進一步發展。企業急需進行配送調度自動化，配送算法要能在限定時間內計算可行的配送方案，同時充分利用企業自身的配送資源。因此，本文考慮以下VRP要素：多種車型，每種車型車輛數量有限，不同車型固定費用、可變費用和最大裝載容量不同，每個門店的訂貨需求必須被滿足且只能由一輛車服務。根據要素確定本文研究的問題是一個具有固定車輛數的多車型車輛路徑問題(Heterogeneous Fixed Fleet Vehicle Routing Problem, HFFVRP)[3]。同時，本文提出的算法需在限定的時間內得到較好的解。

1 相關研究

大規模物流配送問題具有網絡拓撲結構復雜、數據處理規模大等[4]特點，難以直接解決。現實中企業一般將門店按行政區域進行劃分，從而將大規模VRP轉化為多個小規模VRP進行解決。但按行政區域進行劃分并不是最合理的劃分方式，有學者提出改進的基于基地啟發式算法(Location Based Algorithm)解決門店分區問題[4]。近年來，隨著大數據處理技術的成熟，聚類分析被廣泛應用到各個領域，不少學者將聚類分析應用于VRP中。Ewbank等[5]使用無監督模糊聚類技術對客戶點進行聚類分組，然后構建分組的旅行商問題(Travelling Salesman Problem, TSP)路線；Shin等[6]提出一種基于幾何中心(centroid-based)聚類的三階段算法，先圍繞g個種子客戶點進行聚類，然后根據類的幾何中心和車輛容量約束對客戶進行聚類再分配，最后構建每個類內部的TSP路線。但是，上述算法需指定聚類個數，而在實際應用中，聚類個數往往難以確定。本文擬采用DBSCAN(Density-Based Spatial Clustering of Applications with Noise)密度聚類算法，該算法根據用戶輸入的密度參數定義稀疏數據和稠密數據,只將稠密數據集作為聚類[7]。該算法可以克服其他基于距離的聚類只能發現類圓形類簇的缺點，并且無需指定聚類個數，適合用于對配送路線進行聚類分析。

基于鄰域搜索的算法解決CVRP(Capacitated VRP)取得了較好的效果，一方面在多個國際基準測試案例上求得已知最優解，另一方面可擴展多種約束條件解決復雜的現實問題。但是，隨著問題規模的增大，已有算法容易陷入局部最優。鄰域搜索求解質量取決于鄰域映射的方式。傳統的鄰域映射方式主要分為路徑間交換或路徑內交換，如Shift(1,0)[8]、Swap(1,1)[8]、2-opt[8]等，算法每次迭代時對配送方案中1個或者2個節點進行操作，鄰域搜索范圍較小，當問題的解空間較大時，求解結果容易陷入局部最優。自適應大規模鄰域搜索(Adaptive Large Neighborhood Search, ALNS)[9]擴展了傳統鄰域搜索的鄰域概念，設計的鄰域結構對多個節點進行操作，從而擴大了鄰域搜索的范圍，更有可能求得全局最優的解。目前，國內外學者基于自適應大規模鄰域搜索解決HFFVRP的研究很少，并且在問題規模較大、車型種類較多、算法求解時間有限的情況下，現有自適應大規模鄰域搜索算法不能有效解決實際問題。

目前，ALNS中的毀滅移除算法分為workday、route和customer[11]三個層次，workday按工作日對配送方案進行移除，route對配送方案中的配送路線進行移除，customer對配送路線上的門店進行移除。本文研究和實現customer層的毀滅移除算法。Random Removal[9]是最簡單的毀滅移除算法，可在解空間中產生任意的鄰域集合；該算法易于實現但隨機性較大，不能保證ALNS求解質量。Shaw Removal[9]定義了相關度函數，鄰域映射方式由相關度函數決定；由于相關度函數計算復雜，導致該移除算法執行時間較長，容易造成ALNS算法整體執行時間過長的問題。Worst Removal[12]定義了一個門店從當前配送方案移除的開銷函數，開銷值越大，門店越需被移除，毀滅時移除開銷值最大的q個門店；該算法移除效果好，但時間復雜度高。在門店規模大且聚集的應用場景下，對配送方案進行門店移除時，已有毀滅移除算法每次移除一個門店，門店可能來自不同的聚集域，這造成移除的節點插入原聚集域代價最低，在重建階段該移除門店將被重新插入原聚集域。由于執行一輪毀滅和重建操作后，配送方案沒有發生變化，ALNS算法需執行多輪毀滅和重建操作才能移除整個聚集域，從而增加了ALNS算法的迭代次數和執行時間，面對大規模門店配送時，ALNS算法無法在有限時間內求得較優解。

因此，本文在ALNS算法中設計了一種基于密度聚類的毀滅移除算法。在毀滅階段使用密度聚類算法對配送路線進行聚類分簇，移除時以簇為單位，能在一次迭代中達到其他移除算法多次迭代的效果，而且密度聚類算法實現簡單，時間開銷較少，在執行一輪毀滅與重建操作上該算法時間開銷比其他移除算法少。在國際基準測試案例上進行實驗，結果表明采用密度聚類的毀滅移除算法執行相同的迭代次數只需更短時間，而且能得到更優的解，驗證了基于密度聚類的毀滅移除算法的有效性。應用于本文研究的企業案例中，與人工調度派車相比，本文設計的ALNS算法減少了1/3的車輛使用，總開銷不到其1/3，極大地降低了企業的配送成本。

2 問題描述及定義

在企業實際物流配送的車隊中，費用計算復雜，包括司機津貼、車輛加油費、過路過橋費、車輛維修費、停車費等，為方便研究，擬將車輛費用分為可變費用和固定費用，可變費用由每公里油耗與行駛里程數決定，固定費用是除可變費用外的其他一切費用。本文考慮多種因素形式化為HFFVRP數學模型，該模型目標是確定一組車輛對門店進行配送服務，包括每輛車的車型，每輛車應服務的門店、訪問門店的順序和路線。模型目標函數由兩部分費用組成：固定成本和可變成本。固定成本為所有車輛的固定費用累加和，可變成本為所有車輛可變費用累加和。目標函數約束條件為本文考慮的現實因素，配送方案優劣通過目標函數值大小進行判定。

HFFVRP定義如下：設無向圖G=(V,E),V={0,1,…,n}代表圖中所有的節點，其中物流總倉編號為0，所有車輛必須從0節點出發最終回到0節點；其余編號為各個門店，每個門店對貨物的需求量為di。E={(i,j)|i,j∈V,i≠j}是任意兩個節點的邊，權值為實際門店之間的距離dij。假設企業擁有的m種車型M={1,2,…,m}，第k種車型擁有的車輛集合為φk，固定費用為fk，每公里油耗費用為vk，該車型最大裝載量為Qk。規定每個門店的需求必須被滿足且只能由一輛車進行服務，問題的目標是：確定一組車輛對n個門店進行配送服務，使得總開銷最小。

本文定義HFFVRP模型使用的參數和決策變量如表1所示。建立具有固定車輛數的多車型車輛路徑問題數學模型如下所示:

(1)

(2)

(3)

(4)

(5)

(6)

其中:f(x)是目標函數;約束(2)表示各門店至少被一輛車服務一次;約束(3)確保一輛車對一個門店服務后，離開這個門店;約束(4)表示每個門店只能由一輛車提供服務;約束(5)表示被同一輛車服務的門店需要貨物總和不能超過該車型最大的裝載量;約束(6)表示門店j只能由一輛來自其他門店的車輛提供服務。

表1 HFFVRP數學模型的參數和決策變量Tab. 1 Parameters and decision variables of HFFVRR model

3 算法設計

設I為組合優化問題的實例，滿足I中所有約束條件的可行解為S(I)，衡量一個解好壞的開銷函數為式(1)，目標是求解式(1)中最小值。對任意一個解X上的映射：

N:X∈S(I)→N(X)?S(I)

(7)

稱為一個鄰域映射，又叫鄰域結構。其中:N(X)為解X的鄰域集合，稱X′∈N(X)為X的一個鄰居。在傳統的鄰域搜索中，鄰域集合的映射方式主要對當前解中一個或者兩個元素進行操作。ALNS是傳統鄰域搜索的一種擴展，通過對多個元素進行操作，從而擴展了鄰域的空間，在解空間中更大的范圍內搜索最好解[9]。ALNS算法求解的質量和速度主要受鄰域映射的方式影響，對不同的問題實例，最優的鄰域映射方式不同。對于同一個問題實例，設計不同的鄰域映射方式，算法求解質量也不相同。ALNS鄰域映射方式由毀滅階段算法決定，重建階段則在鄰域結構對應的鄰域解集合中搜索最佳可行解。ALNS在一次迭代中主要需要經歷毀滅與重建兩個階段:毀滅階段選擇一個簡單的移除算法，從當前配送路線中移除q個節點，將q個節點插入配送路線形成的所有可行解為鄰域集合;重建階段選擇一個構造算法從鄰域集合中搜索最好解形成新解，最后由接受準則決定是否采納新解。

設計一個ALNS算法需要注意以下三點：1)一組簡單有效的毀滅移除算法；2)一組能快速構造可行解的重建算法；3)決策層選擇合適的接受準則。

在毀滅階段本文根據實際情況提出并實現了基于密度聚類的毀滅移除算法(Cluster Removal, CR)，這是一種新的鄰域映射方式。同時還實現了Shaw Removal(SR)[9]、Worst Removal(WR)[12]和Random Removal(RR)[9]三種毀滅移除算法。在重建算法上本文實現了貪婪插入法[11]和Regret-2插入法[11]。本文借鑒模擬退火算法[13]設計和實現接受準則。

3.1 算法框架

算法1中ALNS框架基本流程包括：產生初始解，自適應選擇算法組合，毀滅當前解，重建可行解，根據接受準則判斷是否采納新的可行解。設毀滅與重建算法的全組合為L={a1,a2,…,an}，相對應的分數集合為P={π1,π2,…,πn}，每種組合ai包括一種毀滅算法和一種重建算法，對應分數為πi，πi將決定組合ai在輪盤賭選擇法被選中的概率。算法1中，第1)行構造初始方案時應選擇簡單的VRP構造算法，本文實現插入法[12]求得初始可行路線集合X，并設為當前能找到的最好解X*。第2)～12)行是主循環，算法執行指定的迭代次數。在循環內部，算法每執行R次迭代將對P進行更新，以保證對當前解改善較多的算法組合能被更大概率地選中。在每次迭代中(第4)～9)行)，毀滅算法根據移除規則破壞當前解X，使得q個門店未被服務，重建算法將q個門店重新插入到路線集合中得到可行的新路線集合X′，如果X′滿足接受準則，將成為當前能找到的最好路線組合。當執行次數達到最大迭代次數，輸出X*。

3.2 基于密度聚類的毀滅移除算法

在本文研究的企業案例中，每天需要處理來自各地300多家門店的訂單，問題規模較大。在地理分布上，同一個行政區域內門店分布相對密集，但企業物流總倉距離大部分門店較遠，基本在30 km以上，因此配送路線上的門店具有聚集的特點，適合應用聚類算法。

在圖2中，假設毀滅階段選擇路線2進行移除。對于路線2中距離較近的門店j、k、l和m，使用其他毀滅算法進行移除時，算法隨機移除其中一個門店，例如門店k。然后在重建階段將k重新插入到配送路線中，由于在門店j和門店l之間插入代價最低，k將被重新插入到路線2中。算法執行一輪毀滅與重建操作后，路線1和路線2并未發生任何變化，從圖2左邊的配送方案變換為右邊的配送方案，算法將需要執行多次迭代。若使用聚類技術，將對路線2通過聚類得到(g,h,i,n)和(j,k,l,m)兩個門店簇，每個簇被移除概率為0.5。被移除的門店簇在重建階段被重新插入配送路線時可得到圖2右邊的配送方案，這是一個比圖2左邊更優的配送方案，并且只執行一輪毀滅與重建操作，因此，使用聚類技術的鄰域映射方式更適合應用于門店規模大且聚集的場景，能減少ALNS算法執行的迭代次數，降低ALNS算法執行的時間，提高ALNS求解質量。

圖2 基于密度聚類的毀滅移除例子Fig. 2 Example of density clustering based removal heuristic

毀滅階段需要設計一個簡單的移除算法從當前配送方案中移除q個門店，若移除算法過于復雜將影響ALNS算法整體性能。在customer層實現基于聚類的移除算法時，聚類對象為每輛車的配送路線。文獻[5]使用的模糊聚類技術和文獻[6]使用的基于幾何中心的聚類技術需事先指定聚類的個數g，g由車輛最大裝載量和客戶需求量總和決定，最終配送方案將派g輛車進行配送，應用于單條配送路線聚類時，k將難以確定。由于DBSCAN聚類算法具有實現簡單、無需指定聚類個數、發現任意形狀的空間聚類等特點，因此，適合應用于配送路線聚類。在eclipse平臺下實現該算法時可使用開源數學包org.apache.commons.math3.ml.clustering，需指定鄰域半徑參數EpsDistance和核心對象個數參數MinPts。本文在文獻[7]的基礎上實現參數的設置方式，EpsDistance由式(8)決定，其中davg為隨機選取的10個門店之間的平均距離，dmin為10個門店之間的最短距離，控制因子ξ在本文使用的測試案例中均取值0.8，MinPts每次隨機取值{2,3,4}。由于本文研究的企業案例只提供門店的經緯度信息，門店之間的距離計算需要借助高德地圖開發者平臺進行查詢，因此需要自定義門店間的距離計算方式，并把實現類作為參數傳入開源數學包的DBSCANClusterer函數中。

EpsDistance=(davg-dmin)*ξ

(8)

基于密度聚類的毀滅移除算法基本思想是隨機從當前配送路線集合中選擇一條路線，對該路線進行密度聚類得到簇集合，然后隨機選擇一個簇集合進行移除，直到移除了q個門店。設門店集合S={s1,s2,…,sn}，對一條配送路線使用DBSCAN聚類后得到簇集合C={c1,c2,…,cp}，每個簇集合擁有的門店ci={si1,si2,…,sik}，其中i取值范圍從1到p，查詢一個門店si所在路線使用操作ShopInRoute[si]，偽代碼如算法2所示。

算法2 Cluster Removal。

輸入 門店集合S，移除門店個數q；

輸出v; 移除門店集RemovalShops。

過程:

1) whileq> 0 do

2) iftargetRoute==NULL then

3) 從S中隨機選擇一個門店si

4)targetRoute=ShopInRoute[si]

5) else

6) 從LastRemoval中隨機選擇一個門店si

7) 其他門店到si距離從小到大排序

8) 選擇離si最近的門店sij且該門店所屬路線未執移除操作

9)targetRoute=ShopInRoute[sij]

10) 清空LastRemoval={}

11) end if

12) C=DBSCANClusterer(targetRoute,MinPts,EpsDistance)

13 隨機從C中選擇一個簇ci

14) for 每個sil∈ci，其中l從1到kdo

15) 若q為0，跳到21)

16) 把sil加入LastRemoval中

17) 把sil加入RemovalShops中,q自減1

18) end for

19) 把Ci加入RemovalRoutes中

20) end while

21) 輸出RemovalShops

算法分兩種情況選擇聚類的目標路線targetRoute，通過變量LastRemoval記錄最近被移除的門店。剛開始targetRoute為空時，隨機選擇第一條路線進行聚類移除操作，時間復雜度是O(1)。當targetRoute不為空且已移除門店數量不足q個門店時，在第5)～10)行，將從最近移除的門店集合中隨機選擇一個門店sj，假設其他門店到sj按距離從小到大排序后為集合N={sj1,sj2,…,sjn-1}，從中選擇一個未被移除的門店且該門店所屬路線未曾執行移除操作，將targetRoute設置為該門店所屬的路線。在具體實現時，由于其他模塊也需要N集合，在Cluster Removal算法中無需重新計算N，并且選擇門店時最多遍歷N中q個門店，所以第5)～10)的時間復雜度與常量q相關，為O(q)。在算法第12)行對targetRoute路線進行密度聚類，DBSCAN聚類算法在最優的情況下時間復雜度為O(nlogn)，在最壞情況下時間復雜度為O(n2)。因此，Cluster Removal算法時間復雜度取決于DBSCAN聚類算法，在最優情況下時間復雜度為O(q·nlogn)，在最壞情況下時間復雜度為O(q·n2)。

3.3 重建算法

重建算法將毀滅階段移除的q個門店重新插入到配送路線中，使每個門店的需求都被滿足，且不違反各車型車輛數量有限的約束與車輛最大裝載容量的約束，形成可行的配送方案。本文根據HFFVRP的特點設計了插入代價的計算方式，實現貪婪插入和Regret-2插入兩種常用的構造算法。

3.3.1 貪婪插入法

算法基本思想是在每次迭代中為一個移除門店尋找插入代價[12]最低的路線進行插入。根據車型可變成本，本文設計了如式(9)所示的插入代價函數：

(9)

式(9)表示對k車型配送路線上的門店a和門店b之間插入i。Δfi,k的值由兩部分代價組成，分別是i插入a與b之間的開銷和新增一輛車服務i的開銷。通過控制因子γ可以在插入當前路線或新增一輛車上取得平衡。當門店距離倉庫較近且插入當前路線代價較高時，應新增一輛車對門店進行服務；當門店距離倉庫較遠時，應避免新增一輛車。控制因子γ在迭代中每次隨機取值{0.00,0.05,0.10,…,1.50}。當出現違反車輛容量約束而無法將門店i插入路線k的情況時，先判斷該車型是否還有可用車輛，若存在可用車輛，則Δfi,k為新增一輛車服務該門店的代價，否則Δfi,k=∞。算法每次迭代尋找式(10)中門店與路線的組合：

(10)

然后，將門店i插入k路線中，更新車輛的可用容量。迭代一直進行，直到q個門店全部被插入配送路線中。該算法實現簡單，計算Δfi,k操作最多需要進行n次，因此算法的時間復雜度為O(q·n)。但是，對于插入開銷最大的門店，算法在最后一次迭代進行處理，此時每條路線對應的車輛可用容量低，插入任何路線都容易違反車輛的最大裝載容量約束，唯有新增一輛車對該門店進行服務，從而增加了車輛數，總開銷變大。

3.3.2 Regret-2插入法

(11)

式(11)保證了門店i插入到最合適的路線上，算法迭代后期處理的是最優路線與次優路線之間差值不大的門店，能有效避免貪婪插入法在迭代后期容易出現違反車輛容量約束的問題。

3.4 決策層

經過毀滅與重建兩個階段，算法產生一個新的配送方案，決策層需決定是否接受新的方案。在本文實現的ALNS算法中，決策層做了兩件事情：1)采用模擬退火接受準則決定是否接受新的配送方案；2)自適應選擇下一次迭代的算法組合。

3.4.1 接受準則

模擬退火算法應用在車輛路徑問題上取得了很不錯的效果[13]，本文借鑒模擬退火算法實現接受準則，算法接受比當前解更好的新解，也以一定概率接受比當前解更差的新解。

3.4.2 自適應選擇算法

(12)

其中：r為選擇因子，取值0

4 實驗與分析

本文算法在eclipse平臺下采用Java語言編程實現，測試環境為PC，配置為Intel Core i5-3470 @ 3.2 GHz，8.00 GB內存，32位Windows 7操作系統。為方便描述，毀滅階段使用Cluster Removal機制的ALNS算法簡稱C_ALNS，未使用該機制的算法簡稱ALNS。仿真實驗使用的國際標準測試案例可以從網站http://neo.lcc.uma.es/vrp/vrp-instances/[14]下載。

4.1 基準測試案例驗證有效性

本文提出的C_ALNS適用于具有大規模客戶，且客戶在地理位置上具有聚集特點的場景。在網絡上公開的HFFVRP數據集中客戶點并沒有聚集特點，不符合本文需要研究的場景。因此，本文采用符合場景應用的CVRP(國際基準測試案例進行測試，CVRP可看成只有一種車型的HFFVRP。該測試案例為Augerat等提供的B類型的數據集[14]，客戶點具有聚集的特點，規模從31到78不等。

算法參數設置如下:在C_ALNS和ALNS中，每種毀滅與重建算法組合初始分數πi都設為0.5，以保證每種組合被選中的概率相同；分數更新選擇因子r設為0.2。根據文獻[12]給出的建議：在小規模問題中，將毀滅階段需要移除的客戶數量q設置為min{0.1n,30}，其中n代表客戶總數；大規模問題則設置為min{0.4n,60}。迭代次數IterMax設為2 000。

Augerat數據集的客戶規模較小，能在較短時間內得到穩定解，對每個測試案例均進行5次實驗，分別記錄C_ALNS算法和ALNS算法取得的解及花費的時間，記錄各移除算法產生的滿足接受準則解的次數，結果如表2所示。在表2中：第一列為測試案例編號；第二列為該案例目前已知的最優解；cost列為相應算法取得的解；time列為相應算法的執行時間(單位為s)；gap/%列表示相應算法取得的解與公認最優解之間的誤差，計算公式為:

gap=(ZC_ALNS/ALNS-Zbest)/Zbest*100%

(13)

其中：ZC_ALNS/ALNS代表C_ALNS算法或者ALNS算法取得的解，Zbest代表該案例已知最優解。SR、RR、WR、CR列為本文實現的移除算法的貢獻率，各移除算法貢獻率計算方式為：ALNS執行2 000次迭代，由該移除算法產生滿足接受準則的解的次數除以所有滿足接受準則的解的總次數。測試案例移除算法貢獻率越高，對應的鄰域映射方式越適合應用于解決該問題實例。從表2中可知，兩種算法取得的最好解與案例已知最優解之間誤差均在1%以內，誤差較小。在23個測試案例上，C_ANS算法需要更短的時間，所需時間加黑表示該案例下C_ALNS算法求解質量比ALNS算法更優，占19個案例，說明在相同迭代次數下，C_ALNS算法能在更短的時間內求得更優的解，比ALNS更高效。在4個例外的案例中，結合各毀滅移除算法貢獻率可知，SR或者WR毀滅移除算法更適合應用于這些案例，但C_ALNS產生的解與ALNS產生的解相差不超過1%，C_ALNS需要時間更短。在C_ALNS表現更好的19個案例中，CR算法貢獻率最高，ALNS則是SR或者WR算法貢獻率高，這說明CR是比SR或WR時間復雜度更低的毀滅移除算法，定義的鄰域映射方式更適合應用于客戶具有聚集特點的VRP場景下，驗證了基于密度聚類的毀滅移除算法的有效性。

表2 Augerat數據集測試結果Tab. 2 Experimental results of Augerat data set

表3給出C_ALNS算法與Hassani等的混合蟻群算法H_ACS[15]、Tasan等的遺傳算法(Genetic Algorithm, GA)[16]、文獻[17]公布的粒子群優化(Particle Swarm Optimization, PSO)算法、Ewbank等的無監督模糊聚類算法[5]、Shin等的Centroid-based 3-phase算法[6]的結果比較，Average行表示每種算法求解結果與案例已知最優解之間的平均誤差,符號“—”表示該算法沒有提供對應測試案例求解結果。

從表3中可知，C_ALNS求解23個測試案例得到的最好解比兩種使用了聚類技術的算法[5-6]求解的結果更優，說明DBSCAN聚類算法適合應用于配送路線聚類。與案例已知最優解相比，C_ALNS算法平均誤差為0.77%，H_ACS算法平均誤差為1.66%，GA的平均誤差為25.03%，PSO算法平均誤差為0.30%，Centroid-based 3-phase算法平均誤差為6.28%，Ewbank等的無監督模糊聚類算法平均誤差為4.58%。GA的平均誤差較大的原因是算法求解質量取決于測試案例的上界和下界，下界為案例已知最優解，但由于GA使用CPLEX在Augerat數據集上求解的上界較大，故求解結果較差。對比結果表明C_ALNS算法求解質量優于H_ACS算法、GA，Centroid-based 3-phase算法和Ewbank等的無監督模糊聚類算法，稍遜于PSO算法，但C_ALNS算法在給定迭代次數下求得最好解，以滿足時間限制要求，PSO算法以最優解為目標，并未限定時間約束，因此，本文設計的C_ALNS算法能有效解決車輛路徑問題。

4.2 企業實際案例

本文研究的企業案例每天凌晨前匯總當天所有門店的訂單，并在凌晨后處理部分訂單，在白天處理大部分訂單。企業需要算法在有限時間內求得較好的配送方案，指導貨物裝車，并使車輛按指定路線進行配送。

4.2.1 數據提取

企業業務部門提供以下數據：每個門店詳細地址信息，包括每個門店的經緯度；37種車型詳細數據信息，包括車輛最大裝載量、車輛固定開銷費用、車輛每公里油耗；一個月的訂單歷史數據和人工派車調度處理的結果數據。本文對訂單歷史數據按日進行處理，每天有350個左右的門店下單。利用門店的經緯度信息，通過高德開放平臺可查詢2個門店之間的最短距離或用時最少距離，從而得到每2個門店之間的距離。

4.2.2 參數設置

本文隨機選取一天訂單進行處理，涉及345個門店，規模較大，因此毀滅階段需移除門店個數q設為60。對C_ALNS和ALNS中每種算法組合初始分數設為0.5，保證每種組合選擇概率相同，分數更新選擇因子r設為0.2。算法分別進行1 000、2 000、4 000、8 000、16 000次迭代，以說明算法求得的最好解、迭代次數和時間開銷三者之間的關系。同時選取5、10、15、20、25、30、35輛車進行一組實驗，迭代次數為5 000，以說明車輛規模與時間開銷的關系。最后選取C_ALNS和ALNS迭代5 000次的配送方案與企業人工調度配送方案進行對比。

表3 算法結果對比Tab. 3 Comparison of the results of C_ALNS and other algorithms

4.2.3 結果對比與分析

圖3對比了C_ALNS與ALNS算法配送方案總開銷，總開銷為式(1)定義的目標函數。從迭代次數與總開銷關系中可知，算法在執行相同次數情況下，C_ALNS算法求解效果更優，說明CR算法適用于門店規模大且聚集特點的應用場景，能提高C_ALNS求解質量。兩條曲線下降的趨勢表明兩種算法隨著迭代次數增加，求解質量更優，并最終達到穩定值，因此，在有限時間內，對大規模問題應盡量增加算法執行次數以取得較優的配送方案。

圖3 迭代次數與總開銷關系Fig. 3 Relationship between iterations and total cost

圖4對比了兩種算法的執行時間。在執行相同迭代次數下，C_ALNS算法需要更少時間，說明CR是一個簡單算法，相比其他算法組合，使用CR算法的組合只需花費更短時間執行一輪毀滅與重建的操作，從而縮短了C_ALNS算法整體執行時間。兩種算法執行時間曲線走勢說明迭代次數與花費時間呈正相關關系，若企業需要在1個小時內得到較好的配送方案，在門店規模為345、車型數目為37種的情況下，執行5 000次迭代是較好的選擇。

圖4 迭代次數與時間開銷關系Fig. 4 Relationship between iterations and time

圖5說明車輛規模與算法時間開銷的關系。圖中曲線走勢表明在給定迭代次數下，車輛規模越大，算法執行時間越長。在實際應用中，應根據需要選擇合適車型，以減少車隊規模。例如，對生鮮商品進行配送，只需考慮具有冷藏功能的車型，從而減少配送車輛規模，降低算法執行時間，在有限時間內增加算法執行次數，以求得更優的配送方案。

表4對比企業人工調度、ALNS算法和C_ALNS算法計算的配送方案。車型數為每種配送方案使用車型的種數，車輛數為每種配送方案使用的車輛總數，車輛平均裝載率為所使用的車輛裝載率之和除以使用車輛總數。相比人工調度計算的配送方案，C_ALNS算法與ALNS算法使用了更多的車型，C_ALNS算法減少接近1/3的車輛使用，平均車輛裝載率提高了20%，總開銷不到其1/3，有效地降低了企業配送成本。因此，C_ALNS算法能在有限時間內求得較優配送方案，適合應用在多車型大規模企業物流配送問題中。

圖5 車輛規模與時間開銷關系Fig. 5 Relationship between vehicle scale and time表4 幾種算法配送方案對比Tab. 4 Comparison of delivery solutions calculated by different algorithms

算法車型數車輛數車輛平均裝載率/%總開銷人工調度63070.3618312ANLS102391.375910C_ALNS102191.545881

5 結語

為解決多車型大規模物流配送問題，本文在ALNS算法框架下設計和實現了一種基于密度聚類的毀滅移除算法。使用國際標準測試案例進行仿真實驗，通過C_ALNS與ALNS算法求解結果對比可知，基于密度聚類的毀滅移除算法定義的鄰域映射方式更適合門店規模大且聚集的場景，能有效降低ALNS算法整體執行時間，提高ALNS求解質量，從而驗證所提移除算法的有效性。與Ewbank等的無監督聚類算法[5]、Shin等的Centriod-based 3-phase算法[6]、H_ACS算法[15]、GA[16]、PSO算法[17]相比，C_ALNS求解質量優于H_ACS算法、GA、Ewbank和Shin的算法，稍遜于PSO算法，但C_ALNS算法在限定時間內求解，PSO算法以最優解為目標，并未限定時間約束，因此，C_ALNS算法能有效解決物流配送問題。應用于企業實際數據集的結果表明，C_ALNS算法能在有限時間內得到較優的配送方案，極大地降低了企業的物流配送成本。在新零售模式下，本文提出的算法能有效解決企業對大規模數量的門店進行貨物配送的問題，下一步將研究門店到各顧客之間的物流配送問題。

References)

[1] 郝建彬.“新零售”的曙光[J]. 互聯網經濟,2016(11)：12-15. (HAO J B. The dawn of “new retail” [J]. The Internet Economy, 2016(11): 12-15.)

[2] DANTZIG G B, RAMSER J H. The truck dispatching problem [J]. Management Science, 1959, 6(1): 80-91.

[3] KUMAR S N, PANNEERSELVAM R. A survey on the vehicle routing problem and its variants [J]. Intelligent Information Management, 2012, 4(3): 66-74.

[4] 曹二寶,賴明勇,聶凱,等.大規模物流配送車輛調度問題研究[J].湖南大學學報(自然科學版),2007,34(12):89-92. (CAO E B, LAI M Y, NIE K, et al. Research on large-scale vehicle routing problem of logistics-distribution[J]. Journal of Hunan University (Natural Sciences), 2007, 34(12): 89-92.)

[5] EWBANK H, WANKE P, HADI-VENCHEH A. An unsupervised fuzzy clustering approach to the capacitated vehicle routing problem [J]. Neural Computing and Applications, 2016, 27(4): 857-867.

[6] SHIN K, HAN S. A centroid-based heuristic algorithm for the capacitated vehicle routing problem [J]. Computing & Informatics, 2011, 30(4): 721-732.

[7] 譚穎,胡瑞飛,殷國富.多密度閾值的DBSCAN改進算法[J].計算機應用,2008,28(3):745-748. (TAN Y, HU R F, YIN G F. Adapted DBSCAN with multi-threshold[J]. Journal of Computer Applications, 2008, 28(3): 745-748.)

[8] VAZ PENNA P H, SUBRAMANIAN A, OCHI L S. An iterated local search heuristic for the heterogeneous fleet vehicle routing problem [J]. Journal of Heuristics, 2013, 19(2): 201-232.

[9] ROPKE S, PISINGER D. A unified heuristic for a large class of vehicle routing problems with backhauls [J]. European Journal of Operational Research, 2006, 171(3): 750-775.

[10] GRANGIER P, GENDREAU M, LEHUéDé F, et al. An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization [J]. European Journal of Operational Research, 2014, 254(1): 80-91.

[11] AZI N, GENDREAU M, POTVIN J-Y. An adaptive large neighborhood search for a vehicle routing problem with multiple routes [J]. Computers & Operations Research, 2014, 41(1): 167-173.

[12] GHILAS V, DEMIR E, VAN WOENSEL T. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows and scheduled lines [J]. Computers & Operations Research, 2016, 72: 12-30.

[13] YU V F, LIN S-Y. A simulated annealing heuristic for the open location-routing problem [J]. Computers & Operations Research, 2015, 62(C): 184-196.

[14] NEO. VRP Instances [EB/OL]. [2017- 02- 17]. http://neo.lcc.uma.es/vrp/vrp-instances/.

[15] HASSANI A H E, BOUHAFS L, KOUKAM A. A hybrid ant colony system approach for the capacitated vehicle routing problem and the capacitated vehicle routing problem with time windows[M]// Vehicle Routing Problem. [S.l.]: InTechOpen., 2008： 58-70.

[16] TASAN A S, GEN M. A genetic algorithm based approach to vehicle routing problem with simultaneous pick-up and deliveries [J]. Computers & Industrial Engineering, 2012, 62(3): 755-761.

[17] TEOH B E, PONNAMBALAM S G, KANAGARAJ G. Differential evolution algorithm with local search for capacitated vehicle routing problem [J]. International Journal of Bio-Inspired Computation, 2015, 7(5): 321-342.

This work is supported by the National Key Technology R&D Program (2015BAH05F02)

YANGWang, born in 1982, Ph. D., associate professor. His research interests include computer algorithm.

HEGuochao, born in 1991, M. S. candidate. His research interests include vehicle routing problem.

WUYan, born in 1992, M. S. candidate. Her research interests include vehicle routing problem.

Densityclusteringbasedremovalheuristicforvehicleroutingproblem

YANG Wang*, HE Guochao, WU Yan

(SchoolofInformationScienceandEngineering,CentralSouthUniversity,ChangshaHunan410083,China)

Focusing on large-scale vehicle routing problem with heterogeneous fleet, a new neighborhood mapping method, namely density clustering based removal heuristic algorithm, was proposed under the Adaptive Large Neighborhood Search (ALNS) frame work. ALNS includes two phases: destruction and reconstruction, which provides optimized solution by destroying and reconstructing current solution. In the destruction phase, a routine was randomly selected to get clusters by density clustering, and then the stores were removed from the routine according to the clusters. In reconstruction, Greedy or Regret-2 insert algorithm was randomly chosen to place those removed stores into proper routine. Test results on benchmark instances validate the effectiveness of the proposed method. Compared with other existing algorithms, the ALNS density clustering based removal heuristic algorithm has lower rate of error and better quality of solutions; in real situations, the proposed algorithm can provide optimized solution in limited time.

new retail; Vehicle Routing Problem (VRP); Heterogeneous Fixed Fleet Vehicle Routing Problem (HFFVRP); ruin and recreate; density clustering; adaptive large neighborhood search

TP399; TP301.6

A

2017- 02- 21;

2017- 04- 18。

國家科技支撐計劃項目(2015BAH05F02)。

陽旺(1982—)，男，湖南湘潭人，副教授，博士，CCF會員，主要研究方向：計算機算法； 何國超(1991—)，男，廣東湛江人，碩士研究生，主要研究方向：車輛路徑問題； 吳雁(1992—)，女，湖南漣源人，碩士研究生，主要研究方向：車輛路徑問題。

1001- 9081(2017)08- 2387- 08

10.11772/j.issn.1001- 9081.2017.08.2387