陽 旺，何國(guó)超，吳 雁

(中南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410083)

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

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

陽 旺*，何國(guó)超，吳 雁

(中南大學(xué) 信息科學(xué)與工程學(xué)院，長(zhǎng)沙 410083)

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

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

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

0 引言

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

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

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

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

1 相關(guān)研究

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

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

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

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

2 問題描述及定義

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

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

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

(1)

(2)

(3)

(4)

(5)

(6)

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

表1 HFFVRP數(shù)學(xué)模型的參數(shù)和決策變量Tab. 1 Parameters and decision variables of HFFVRR model

3 算法設(shè)計(jì)

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

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

(7)

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

設(shè)計(jì)一個(gè)ALNS算法需要注意以下三點(diǎn)：1)一組簡(jiǎn)單有效的毀滅移除算法；2)一組能快速構(gòu)造可行解的重建算法；3)決策層選擇合適的接受準(zhǔn)則。

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

3.1 算法框架

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

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

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

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

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

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

EpsDistance=(davg-dmin)*ξ

(8)

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

算法2 Cluster Removal。

輸入 門店集合S，移除門店個(gè)數(shù)q；

輸出v; 移除門店集RemovalShops。

過程:

1) whileq> 0 do

2) iftargetRoute==NULL then

3) 從S中隨機(jī)選擇一個(gè)門店si

4)targetRoute=ShopInRoute[si]

5) else

6) 從LastRemoval中隨機(jī)選擇一個(gè)門店si

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

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

9)targetRoute=ShopInRoute[sij]

10) 清空LastRemoval={}

11) end if

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

13 隨機(jī)從C中選擇一個(gè)簇ci

14) for 每個(gè)sil∈ci，其中l(wèi)從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

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

3.3 重建算法

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

3.3.1 貪婪插入法

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

(9)

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

(10)

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

3.3.2 Regret-2插入法

(11)

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

3.4 決策層

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

3.4.1 接受準(zhǔn)則

模擬退火算法應(yīng)用在車輛路徑問題上取得了很不錯(cuò)的效果[13]，本文借鑒模擬退火算法實(shí)現(xiàn)接受準(zhǔn)則，算法接受比當(dāng)前解更好的新解，也以一定概率接受比當(dāng)前解更差的新解。

3.4.2 自適應(yīng)選擇算法

(12)

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

4 實(shí)驗(yàn)與分析

本文算法在eclipse平臺(tái)下采用Java語言編程實(shí)現(xiàn)，測(cè)試環(huán)境為PC，配置為Intel Core i5-3470 @ 3.2 GHz，8.00 GB內(nèi)存，32位Windows 7操作系統(tǒng)。為方便描述，毀滅階段使用Cluster Removal機(jī)制的ALNS算法簡(jiǎn)稱C_ALNS，未使用該機(jī)制的算法簡(jiǎn)稱ALNS。仿真實(shí)驗(yàn)使用的國(guó)際標(biāo)準(zhǔn)測(cè)試案例可以從網(wǎng)站http://neo.lcc.uma.es/vrp/vrp-instances/[14]下載。

4.1 基準(zhǔn)測(cè)試案例驗(yàn)證有效性

本文提出的C_ALNS適用于具有大規(guī)?？蛻簦铱蛻粼诘乩砦恢蒙暇哂芯奂攸c(diǎn)的場(chǎng)景。在網(wǎng)絡(luò)上公開的HFFVRP數(shù)據(jù)集中客戶點(diǎn)并沒有聚集特點(diǎn)，不符合本文需要研究的場(chǎng)景。因此，本文采用符合場(chǎng)景應(yīng)用的CVRP(國(guó)際基準(zhǔn)測(cè)試案例進(jìn)行測(cè)試，CVRP可看成只有一種車型的HFFVRP。該測(cè)試案例為Augerat等提供的B類型的數(shù)據(jù)集[14]，客戶點(diǎn)具有聚集的特點(diǎn)，規(guī)模從31到78不等。

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

Augerat數(shù)據(jù)集的客戶規(guī)模較小，能在較短時(shí)間內(nèi)得到穩(wěn)定解，對(duì)每個(gè)測(cè)試案例均進(jìn)行5次實(shí)驗(yàn)，分別記錄C_ALNS算法和ALNS算法取得的解及花費(fèi)的時(shí)間，記錄各移除算法產(chǎn)生的滿足接受準(zhǔn)則解的次數(shù)，結(jié)果如表2所示。在表2中：第一列為測(cè)試案例編號(hào)；第二列為該案例目前已知的最優(yōu)解；cost列為相應(yīng)算法取得的解；time列為相應(yīng)算法的執(zhí)行時(shí)間(單位為s)；gap/%列表示相應(yīng)算法取得的解與公認(rèn)最優(yōu)解之間的誤差，計(jì)算公式為:

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

(13)

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

表2 Augerat數(shù)據(jù)集測(cè)試結(jié)果Tab. 2 Experimental results of Augerat data set

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

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

4.2 企業(yè)實(shí)際案例

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

4.2.1 數(shù)據(jù)提取

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

4.2.2 參數(shù)設(shè)置

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

表3 算法結(jié)果對(duì)比Tab. 3 Comparison of the results of C_ALNS and other algorithms

4.2.3 結(jié)果對(duì)比與分析

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

圖3 迭代次數(shù)與總開銷關(guān)系Fig. 3 Relationship between iterations and total cost

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

圖4 迭代次數(shù)與時(shí)間開銷關(guān)系Fig. 4 Relationship between iterations and time

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

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

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

算法車型數(shù)車輛數(shù)車輛平均裝載率/%總開銷人工調(diào)度63070.3618312ANLS102391.375910C_ALNS102191.545881

5 結(jié)語

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

References)

[1] 郝建彬.“新零售”的曙光[J]. 互聯(lián)網(wǎng)經(jīng)濟(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] 曹二寶,賴明勇,聶凱,等.大規(guī)模物流配送車輛調(diào)度問題研究[J].湖南大學(xué)學(xué)報(bào)(自然科學(xué)版),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] 譚穎,胡瑞飛,殷國(guó)富.多密度閾值的DBSCAN改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用,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。

國(guó)家科技支撐計(jì)劃項(xiàng)目(2015BAH05F02)。

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

1001- 9081(2017)08- 2387- 08

10.11772/j.issn.1001- 9081.2017.08.2387