張 雄,潘大志,2

(1.西華師范大學數(shù)學與信息學院,四川 南充 637009; 2.西華師范大學計算方法與應(yīng)用研究所,四川 南充 637009)

0 引 言

車輛路徑問題(Vehicle Routing Problem，VRP)，最早由Dantzig等人[1]于1959年提出，指的是多臺運輸車輛從配送中心出發(fā)向多個顧客運送貨物，最后返回配送中心。Solomon[2]于1987年將時間窗口引入到車輛路徑問題中，提出了帶時間窗口的車輛路徑問題(Vehicle Routing Problem with Time Windows,VRPTW)，配送中心有一個時間窗口，所有車輛對顧客的送貨服務(wù)必須在這個時間段內(nèi)，每個顧客也設(shè)有時間窗口，車輛必須在時間窗口內(nèi)才能對顧客開始服務(wù)。若車輛到達顧客的時間早于顧客最早開始服務(wù)時間，那么車輛必須等到顧客的最早開始服務(wù)時間才能服務(wù)；若車輛到達的顧客時間晚于顧客最晚開始服務(wù)時間，那么此顧客不能被這輛車服務(wù)，這種窗口稱為硬時間窗口(Hard Time Window)。

對于求解VRPTW，通常采用啟發(fā)式算法進行求解，因為當數(shù)據(jù)規(guī)模比較大時，精確算法需要較長的時間，對計算機的內(nèi)存要求也更高。啟發(fā)式算法不僅能對小規(guī)模VRPTW進行有效求解，也能對大規(guī)模問題進行有效求解，因此國內(nèi)外學者對啟發(fā)式算法求解VRPTW問題的研究較多如遺傳算法[3-5]、蟻群算法[6]、模擬退火算法[7,8]、粒子群算法[9]、狼群算法[10]、蝙蝠算法[11]等。

Cordeau等人[12]將禁忌搜索算法用于求解VRPTW問題以及帶時間窗口多車場車輛路徑問題(Multi Depot Vehicle Routing Problem with Time Windows, MDVRPTW)，該算法運行速度較快，能夠適應(yīng)多種VRP問題；儀孝展[13]將遺傳算法與模擬退火算法相結(jié)合，以防止陷入局部最優(yōu)解，提高了算法的運算效率；黃務(wù)蘭等人[14]提出了遺傳算法與大規(guī)模鄰域搜索算法的混合算法，相比傳統(tǒng)遺傳算法能夠有效避免早熟，但算法運行速度較慢；Harzi等人[15]提出了一種變鄰域搜索算法用于求解VRPTW問題；Paraskevopoulos等人[16]將禁忌搜索算法與變鄰域搜索算法相結(jié)合求解VRPTW問題；Dong等人[17]提出了一種基于MOEA的三細胞組織P系統(tǒng)(PDVA)來解決多目標VRPTW問題；Alzaqebah等人[18]將蜂群算法用于求解VRPTW問題。

蟻群算法(Ant Colony Optimization, ACO)由Dorigo等人[19]于1996年提出，許多國內(nèi)外學者將蟻群算法用于求解VRPTW問題，徐廷學等人[20]將量子計算融入蟻群算法；鄧麗娟等人[21]將精英螞蟻算法與變領(lǐng)域搜索算法融合用于求解多目標VRPTW；李奕穎等人[22]提出了基于Spark平臺的改進蟻群算法求解VRPTW,該算法求解大規(guī)模問題的精度與速度有明顯提升；Júnior等人[23]為提高蟻群算法的搜索性能結(jié)合變鄰下降算法進行局部搜索；金淳等人[24]提出了一種改進的分布式多agent蟻群算法，該算法在精度、速度、可靠性以及求解大規(guī)模問題方面具有明顯優(yōu)勢。

本文針對VRPTW提出一種改進的蟻群算法，在狀態(tài)轉(zhuǎn)移規(guī)則中引入等待時間這一因素，并且對目前最優(yōu)個體進行鄰域搜索，最后通過對Solomon標準測試集進行測試，驗證了算法的有效性。

1 帶時間窗口的車輛路徑問題

VRPTW問題描述：配送中心有一定數(shù)量車型相同的運輸車，在滿足約束條件的情況下，安排合理的路徑向顧客提供服務(wù)，使成本最低，成本包括車輛雇傭成本、運輸燃油消耗成本。

1.1 基本假設(shè)

1)只有一個配送中心，車輛從配送中心出發(fā)，對顧客進行服務(wù)，最后返回配送中心。

2)已知配送中心、顧客位置、配送中心和顧客時間窗口、顧客貨物需求量以及車輛最大裝載量、行駛速度。

3)所有客戶僅能被一輛運輸車提供服務(wù)。

4)運輸車輛對顧客提供服務(wù)必須在顧客規(guī)定的時間窗口內(nèi)，可以早于最早規(guī)定服務(wù)時間，但不能晚于最晚規(guī)定服務(wù)時間。

5)每輛車所服務(wù)客戶的總需求量不能超過車輛的最大裝載量，并且車輛在提供服務(wù)時必須在配送中心的工作時間窗口之內(nèi)。

1.2 數(shù)學模型

VRPTW有2個目標：使用車輛總數(shù)盡可能少和總的運輸距離盡可能的短。在日常物流運輸中雇傭運輸司機的成本遠遠大于車輛行駛途中燃油消耗以及車輛磨損所帶來的成本，因此將車輛使用總數(shù)為第一優(yōu)化目標，總的運輸距離為第二優(yōu)化目標，通過加權(quán)將多目標問題轉(zhuǎn)化為單目標問題。

目標函數(shù)為：

(1)

約束條件為：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

其中，公式(1)通過加權(quán)的方式將所用車輛數(shù)量和總的行駛距離這一多目標問題轉(zhuǎn)化為單目標問題，并且以前者為第一優(yōu)化目標。公式(2)和公式(3)表示一個顧客只能被一輛車服務(wù)。公式(4)和公式(5)表示配送中心的車輛不必全部參與運輸。公式(6)表示一輛車的路徑不會出現(xiàn)子回路。公式(7)表示離開節(jié)點的時間約束。公式(8)和公式(9)為車輛的時間窗口約束，公式(10)為車輛的裝載量約束。

2 改進的蟻群算法

2.1 編碼

本文采用整數(shù)編碼，配送中心編碼為1，顧客節(jié)點編碼為2,3,4,…,N+1。假設(shè)有10個顧客需要服務(wù)，一條可行解編碼為[1,3,4,8,1,7,5,2,1,6,9,11,1]，這條編碼表示有3條子路徑，分別為1→3→4→8→1、1→7→5→2→1、1→6→9→11→1。

2.2 候選集的構(gòu)造

因為車輛有裝載量的限制，顧客有時間窗限制，則候選集中的節(jié)點必須滿足以下約束：

li+tij≤LTj

(11)

li+tij+wj+sj+tj1≤LT1

(12)

loadi+qj≤Q

(13)

其中，loadi為車輛在節(jié)點i當前的裝載量；公式(11)為顧客的時間窗口約束；公式(12)為車輛服務(wù)時間的限制，必須在服務(wù)下一節(jié)點后能夠返回配送中心；公式(13)為車輛裝載量限制。

2.3 狀態(tài)轉(zhuǎn)移規(guī)則設(shè)計

由于時間窗口的約束，車輛在對客戶i服務(wù)時會有等待時間wi(wi≥0),為使每輛車服務(wù)的客戶節(jié)點盡可能多，引入等待時間，構(gòu)建新的狀態(tài)轉(zhuǎn)移規(guī)則，如公式(14):

農(nóng)村配電網(wǎng)線路中存在同桿并架線路時，當某回線路上發(fā)生短路故障后，繼電保護將故障線路跳開，但同桿并架的另一回線路仍然處于正常運行狀態(tài)。此時，由于非故障線路與故障線路間的電容和互感，導致故障點電弧電流無法降低至0，增加電弧滅弧難度。在此狀態(tài)下，故障點電弧中流過的電流稱為潛供電流。由于潛供電流增加了故障點滅弧的難度，延長了故障點滅弧時間，可能導致自動重合閘后故障點絕緣未成功恢復，引發(fā)重合閘失敗。

(14)

(15)

2.4 蟻群算法信息素更新

(16)

(17)

(18)

其中，Q為信息素總量,ρ為信息素揮發(fā)率。

2.5 可行路徑鄰域搜索

由于蟻群算法易過早收斂，因此本文加入鄰域搜索操作。文獻[25]提出了節(jié)點移除——插入鄰域搜索算子，本文在文獻[25]的基礎(chǔ)上結(jié)合VRPTW問題特征設(shè)計多種搜索算子，搜索算子包含顧客節(jié)點移除和重新插入操作，搜索算子的區(qū)別主要在于顧客節(jié)點的移除操作。

1)隨機節(jié)點移除操作move_rand。

從100個客戶節(jié)點中隨機選擇q個節(jié)點，本文設(shè)q=10，即總顧客數(shù)的10%。將選擇的q個節(jié)點從路徑中移除，并保存移除后的路徑。

2)最長距離節(jié)點移除操作move_arc。

記Disti=distr,i+disti,j,r為節(jié)點i的前驅(qū)節(jié)點，j為節(jié)點i的后繼節(jié)點，disti,j為i和j節(jié)點的距離，移除Dist最大的節(jié)點。移除操作如圖1所示，從可行路徑中移除6號節(jié)點，此操作是為了減少路徑的總長度。

圖1 節(jié)點移除操作

3)車輛服務(wù)最少顧客節(jié)點移除操作move_nodes。

選出可行路徑中車輛服務(wù)顧客數(shù)最少的子路徑，將所在子路徑中的節(jié)點移除，此操作可減少運輸車輛的使用數(shù)量。

4)節(jié)點重新插入操作insert。

將移除操作得到的節(jié)點，依次插入路徑中，采用貪心的思想保存總成本最小的路徑作為最終路徑。由于時間窗口以及運輸車裝載量的約束，經(jīng)過移除-插入操作可能會產(chǎn)生不可行解，但只需對重新插入節(jié)點的子路徑進行檢測修復。

5)子路徑檢測修復操作。

即對插入節(jié)點的路徑，逐一計算每個節(jié)點的車輛開始服務(wù)時間以及車輛的當前裝載量，若有不滿足時間窗口或裝載量約束的節(jié)點j，便將原路徑從節(jié)點j截斷，節(jié)點j之前的路徑作為已檢測過的滿足約束的路徑，剩下路徑繼續(xù)從節(jié)點j開始檢驗，直到所有節(jié)點都檢測完成且滿足約束條件。鄰域搜索算法步驟為：

Step1初始化參數(shù)counter←0。

Step2對蟻群算法得到的當前種群最優(yōu)路徑隨機選取一種節(jié)點移除操作，記錄移除的節(jié)點nodes_r及路徑rout_r。

Step3將nodes_r，通過insert插入算子插入到路徑rout_r中，得到新路徑，對新路徑進行修復操作。

Step4counter←counter+1，若counter

2.6 算法步驟

Step1蟻群算法參數(shù)初始化,Iter←0。

Step2通過狀態(tài)轉(zhuǎn)移規(guī)則構(gòu)造pop_size(種群大小)個路徑。

Step3對當前蟻群算法得到的最優(yōu)路徑進行鄰域搜索操作產(chǎn)生新路徑。

Step4蟻群算法得到的種群與鄰域得到的新種群按適應(yīng)度從小到大排序，選取前pop_size個個體得到新種群。

Step6信息素更新，令I(lǐng)ter←Iter+1，更新全局最優(yōu)解以及畫出當前最優(yōu)路徑圖。

Step7若Iter

3 實驗分析

實驗所使用計算機配置為3.5 GHz CPU、8 GB RAM、64位操作系統(tǒng)；編程語言為MATLAB語言,版本為MATLAB r2018a;運行參數(shù)為popsize=30，α=2,β=1.5,γ=1，ρ=0.95,Q=10，以Solomon標準測試集C類為參考，測試集中客戶節(jié)點為100，包含大時間窗口與小時間窗口,車輛裝載量也有大小。每種算法運行10次,最大迭代次數(shù)為400。表1～表3分別為基本蟻群算法(ACS)、文獻[4]算法以及目前已知最優(yōu)解與本文算法(ACS-NS)的求解結(jié)果對比。圖2～圖4分別為C103、C106、C204、C207算例通過本文算法所得到路徑圖。

表1 基本蟻群算法與本文算法結(jié)果對比

表2 文獻[4]算法與本文算法結(jié)果對比

表3 已知最優(yōu)解與本文算法結(jié)果對比

圖2 C103路徑圖

圖3 C106路徑圖

圖4 C204路徑圖

圖5 C207路徑圖

由表1可以看出，無論是在車輛使用數(shù)量還是路徑總長度，ACS-NS算法均優(yōu)于ACS算法。表2為文獻[4]算法與ACS-NS算法的求解結(jié)果對比，雖然C105算例在路徑總長度上ACS-NS算法求解結(jié)果要差于文獻[4]算法,但誤差僅為1.8%,其余算例ACS-NS算法得到的結(jié)果均優(yōu)于文獻[4]算法。表3為ACS-NS算法求解結(jié)果與目前最優(yōu)解(http://w.cba.neu.edu/～msolomon/heuristi.htm)對比，除C105外其余算例均達到最優(yōu)解，C105算例中車輛行駛距離差異為3%。通過實驗分析可知改進后的蟻群算法對帶時間窗口車輛路徑問題有較好的適用性，能有效求解帶時間窗口車輛路徑問題。

4 結(jié)束語

針對帶時間窗口車輛路徑問題，本文提出的改進蟻群算法在狀態(tài)轉(zhuǎn)移規(guī)則中引入等待時間，通過構(gòu)造節(jié)點移除算子(move_rand、move_arc、move_nodes)以及節(jié)點插入算子insert對蟻群算法得到的路徑鄰域搜索。通過Solomon算例仿真運算，運算結(jié)果與最優(yōu)解對比表明改進算法能夠有效求解帶時間窗口車輛路徑問題。