融合鄰域搜索策略蟻群算法求解帶時(shí)間窗口的車(chē)輛路徑問(wèn)題

張 雄,潘大志,2

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

0 引 言

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

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

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

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

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

1 帶時(shí)間窗口的車(chē)輛路徑問(wèn)題

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

1.1 基本假設(shè)

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

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

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

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

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

1.2 數(shù)學(xué)模型

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

目標(biāo)函數(shù)為：

(1)

約束條件為：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

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

2 改進(jìn)的蟻群算法

2.1 編碼

本文采用整數(shù)編碼，配送中心編碼為1，顧客節(jié)點(diǎn)編碼為2,3,4,…,N+1。假設(shè)有10個(gè)顧客需要服務(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)造

因?yàn)檐?chē)輛有裝載量的限制，顧客有時(shí)間窗限制，則候選集中的節(jié)點(diǎn)必須滿(mǎn)足以下約束：

li+tij≤LTj

(11)

li+tij+wj+sj+tj1≤LT1

(12)

loadi+qj≤Q

(13)

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

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

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

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

(14)

(15)

2.4 蟻群算法信息素更新

(16)

(17)

(18)

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

2.5 可行路徑鄰域搜索

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

1)隨機(jī)節(jié)點(diǎn)移除操作move_rand。

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

2)最長(zhǎng)距離節(jié)點(diǎn)移除操作move_arc。

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

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

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

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

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

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

5)子路徑檢測(cè)修復(fù)操作。

即對(duì)插入節(jié)點(diǎn)的路徑，逐一計(jì)算每個(gè)節(jié)點(diǎn)的車(chē)輛開(kāi)始服務(wù)時(shí)間以及車(chē)輛的當(dāng)前裝載量，若有不滿(mǎn)足時(shí)間窗口或裝載量約束的節(jié)點(diǎn)j，便將原路徑從節(jié)點(diǎn)j截?cái)?，?jié)點(diǎn)j之前的路徑作為已檢測(cè)過(guò)的滿(mǎn)足約束的路徑，剩下路徑繼續(xù)從節(jié)點(diǎn)j開(kāi)始檢驗(yàn)，直到所有節(jié)點(diǎn)都檢測(cè)完成且滿(mǎn)足約束條件。鄰域搜索算法步驟為：

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

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

Step3將nodes_r，通過(guò)insert插入算子插入到路徑rout_r中，得到新路徑，對(duì)新路徑進(jìn)行修復(fù)操作。

Step4counter←counter+1，若counter

2.6 算法步驟

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

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

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

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

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

Step7若Iter

3 實(shí)驗(yàn)分析

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

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

表2 文獻(xiàn)[4]算法與本文算法結(jié)果對(duì)比

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

圖2 C103路徑圖

圖3 C106路徑圖

圖4 C204路徑圖

圖5 C207路徑圖

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

4 結(jié)束語(yǔ)

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