基于精英保留策略的改進(jìn)蝙蝠算法及其在車輛路徑問題中的應(yīng)用

(武漢理工大學(xué)自動(dòng)化學(xué)院 湖北 武漢 430000)

一、引言

經(jīng)典的車輛路徑問題(Vehicle Routing Problem，VRP)最先由G.Dantzig和J.Ramser[1]在1959發(fā)表的《The Truck Dispatching Problem》一文中提出。VRP問題為NP難問題，其一經(jīng)提出，便引起了眾多學(xué)者的研究，VRP問題被分成了許多類型的問題。比如作為VRP問題經(jīng)典分類的帶時(shí)間窗的車輛路徑問題(Vehicle Routing Problem with Time-Window，VRPTW)，其由Solomon[2]在1979年首次提出，隨后便受到廣大學(xué)者的關(guān)注，顧名思義，其在原有的基礎(chǔ)上多了一個(gè)時(shí)間窗的要求。其根據(jù)對時(shí)間窗要求的嚴(yán)格與否又被分為硬時(shí)間窗和軟時(shí)間窗，本文僅考慮硬時(shí)間窗的情況，即嚴(yán)格遵守時(shí)間窗，車輛要在各客戶點(diǎn)的最晚受理服務(wù)時(shí)間前到達(dá)。

二、問題的模型

VRPTW問題一般被描述為：假設(shè)配送中心(此處用0表示)最多可以以K輛車對L個(gè)客戶進(jìn)行配送運(yùn)輸服務(wù)，配送運(yùn)輸車輛的載重量上限分別為qk(k=1,2,…,K)，每個(gè)客戶的貨物需求量分別為gi(i=1,2,…,L)，cij為客戶點(diǎn)i和客戶點(diǎn)j之間的距離(i、j=1,2，…，L，且i≠j)，同時(shí)，記車輛到達(dá)客戶點(diǎn)i的時(shí)間為RTi，車輛在客戶點(diǎn)i處理服務(wù)(卸貨)的時(shí)間為UTi，tij為車輛從客戶點(diǎn)i到客戶點(diǎn)j所需時(shí)間，客戶點(diǎn)i要求的時(shí)間窗為[ETi,LTi]。要求配送中心計(jì)劃用最短的總行駛距離或運(yùn)輸費(fèi)用完成對所有客戶的配送任務(wù)。

首先定義客戶點(diǎn)的編號集合H={1,2,…,L}、配送路線的編號集合C={0,1,…,L}和配送車輛的編號集合V={1,2,…,K}，其中L為總客戶數(shù)，K為配送中心的最大可用車輛數(shù)。則VRPTW問題的模型[5]如下：

(1)

(2)

(3)

(4)

(5)

(6)

ETi≤RTi≤LTi,i∈H

(7)

xijk∈{0,1},?i、j∈H,?k∈V

(8)

yik∈{0,1},?i∈H,?k∈V

(9)

其中，設(shè)定僅當(dāng)客戶i由車輛k配送時(shí)，yik=1，否則yik=0，僅當(dāng)車輛k從客戶i到客戶j時(shí)，xijk=1，否則xijk=0。

在該模型中，式(1)為目標(biāo)函數(shù)，為單目標(biāo)問題，僅要求Z(車輛的總行駛距離)最小，式(2)限制了車輛的承載能力(車輛單次運(yùn)輸?shù)呢浳锊荒艹^其承載能力)，式(3)限制了每個(gè)客戶點(diǎn)僅能到達(dá)一次，式(4)限制了每個(gè)客戶點(diǎn)都必需要到達(dá)，式(5)限制了要從每個(gè)客戶點(diǎn)駛離(不能停留在客戶點(diǎn))，式(6)限制了車輛線路從配送中心出發(fā)，最后要回到配送中心。式(7)限制了車輛到達(dá)客戶點(diǎn)的時(shí)間范圍。式(8)和式(9)限制了描述時(shí)間的變量xijk和yik的取值只能為0或1，以表示車輛k是否從客戶點(diǎn)i到客戶點(diǎn)j和車輛k是否經(jīng)過客戶點(diǎn)i的客觀事實(shí)。

三、基本蝙蝠算法

Yang[8]受到蝙蝠在高維空間定位、捕獵方式的啟發(fā)，于2010年提出了蝙蝠算法(Bat Algorithm，BA)，其可以應(yīng)用于各種實(shí)際問題的求解。

蝙蝠算法基于以下原則[8]：

(1)每只蝙蝠在捕食過程中，都是使用回聲定位的方法來判斷自己和獵物或障礙物之間的距離(而不是使用視覺或嗅覺)。

(2)每只蝙蝠在位置xi處，以速度vi按任意方向飛行，并發(fā)出不同頻率fi和響度Ai的超聲波來搜索獵物。蝙蝠會(huì)根據(jù)它們離獵物的距離來調(diào)整超聲波的響度Ai和脈沖發(fā)射頻率ri。

蝙蝠算法的實(shí)現(xiàn)步驟如下：

Step2：根據(jù)每只蝙蝠的初始位置xi和適應(yīng)度函數(shù)f(x)，得到每只蝙蝠的初始目標(biāo)值，通過比對，得到當(dāng)前全局最優(yōu)解x*。

Step3：根據(jù)式(10)、(11)、(12)進(jìn)行迭代，更新下一代各蝙蝠的位置、飛行速度和超聲波頻率。其中β為[0,1]上的隨機(jī)數(shù)。

fi=fmin+(fmax-fmin)β

(10)

(11)

(12)

(13)

(14)

(15)

Step6：計(jì)算出當(dāng)前所有蝙蝠的適應(yīng)度值，并篩選出當(dāng)前的全局最優(yōu)解。

Step7：重復(fù)執(zhí)行Step3-Step6，直到滿足精度要求或達(dá)到設(shè)定的迭代次數(shù)。

Step8：輸出全局最優(yōu)解。

基本蝙蝠算法由于其模型簡單，在應(yīng)用的過程中，容易陷入局部極值，無法得到全局最優(yōu)解；其又容易在后期出現(xiàn)收斂速度慢等問題，對其應(yīng)用帶來了極大的不便。因此，對蝙蝠算法的改進(jìn)也從未停止過，如文獻(xiàn)[5]中，馬祥麗將蝙蝠的位置x對應(yīng)了兩個(gè)向量：xa和xb，其中一個(gè)表示車輛的編號，一個(gè)表示配送的順序，其相當(dāng)于省去了兩個(gè)限制條件(3)、(4)式(每個(gè)客戶點(diǎn)只能到達(dá)一次，每個(gè)客戶點(diǎn)都要送到)，其增加了維數(shù)，但卻也減少了計(jì)算過程，最后的仿真結(jié)果也驗(yàn)證了其有效性。文獻(xiàn)[6]中，戚遠(yuǎn)航在蝙蝠算法中引入了隨機(jī)插入策略、普通插入搜索、交換搜索等，提高了搜索空間，加強(qiáng)了蝙蝠算法的收斂效率。

四、改進(jìn)蝙蝠算法解決VRPTW問題

因?yàn)榛掘鹚惴ㄊ潜辉O(shè)計(jì)用來解決連續(xù)函數(shù)的優(yōu)化問題的，而VRP的解是離散化的(若干個(gè)客戶點(diǎn)的有序序列)，所以要想用蝙蝠算法來解決VRP問題，首先要將VRP問題中的各變量進(jìn)行編碼，然后再制定BA算法在VRP問題中的相關(guān)運(yùn)算規(guī)則及相關(guān)操作算子。

(一)編碼和解碼

設(shè)有L個(gè)客戶點(diǎn)，K輛車，蝙蝠種群規(guī)模為s，維數(shù)d=L+K-1，記蝙蝠種群集合S={1,2，…，s}，編碼長度集合D={1,2，…，d}。將蝙蝠位置xi(i∈S)取為(1,2，…，d)的一個(gè)全排列。解碼時(shí)，首先在xi的首末位置各插入一個(gè)0，以表示車輛從配送中心出發(fā)，最后回到配送中心，再將xi中大于L的分量換為0，以代表配送中心，于是xi就變?yōu)榱烁鱾€(gè)車輛的配送路線了。例如L=10，K=3，假設(shè)最優(yōu)解x*為(1,4,6,8,11,2,3,5,12,7,9,10)，解碼時(shí)，x*變?yōu)?0,1,4,6,8,0,2,3,5,0,7,9,10,0)，于是三輛車的線路就為0-1-4-6-8-0,、0-2-3-5-0和0-7-9-10-0了。

(二)操作算子

因?yàn)樵隍鸬奈恢谩w行速度和超聲波頻率的更新公式中，存在位置、速度和頻率的加法、減法或乘積運(yùn)算，所以需要定義其相關(guān)的操作算子，定義如下所示：

x+v為x先按CN1交換，其結(jié)果再按CN2交換，一直到按CNd交換之后的結(jié)果。

v1+v2，表示每一次有兩個(gè)交換數(shù)，同時(shí)交換兩次。但是由式(2)可以看出v2f可能不是整數(shù)或超出了配送點(diǎn)的編號范圍，需要進(jìn)行修正操作，采用向上取整，數(shù)值超過范圍的取臨界值或取一個(gè)在范圍內(nèi)的隨機(jī)值或取當(dāng)前全局最優(yōu)解在此處的分量。本文f取在[0,1]上，然后采取向上取整。

(三)精英保留策略

在局部搜索中，如果找到了比全局最優(yōu)解更優(yōu)的解，更新當(dāng)前全局最優(yōu)解，同時(shí)群體中適應(yīng)度最差的個(gè)體替換成之前的全局最優(yōu)解，以提高收斂效率、避免丟失潛在的良好精英片段。

圖1 算法流程圖

五、仿真實(shí)驗(yàn)

本文算法的相關(guān)實(shí)驗(yàn)均在同一實(shí)驗(yàn)環(huán)境中進(jìn)行，其中CPU主頻為2.50GHz，內(nèi)存為12GB，操作系統(tǒng)為64位windows 10，編程語言為C++。

表1 本文的蝙蝠算法與多目標(biāo)算法的比較結(jié)果

本文得到的最優(yōu)的一次路徑為：

C101中車輛1線路0-57-55-54-53-56-58-60-59-0，車輛2線路0-98-96-95-94-92-93-97-100-99-0，車輛3線路0-81-78-76-71-70-73-77-79-80-0，車輛4線路0-67-65-63-62-74-72-61-64-68-66-69-0，車輛5線路0-20-24-25-27-29-30-28-26-23-22-21-0，車輛6線路0-43-42-41-40-44-46-45-48-51-50-52-49-47-0，車輛7線路0-90-87-86-83-82-84-85-88-89-91-0，車輛8線路0-5-3-7-8-10-11-9-6-4-2-1-75-0，車輛9線路0-32-33-31-35-37-38-39-36-34-0，車輛10線路0-13-17-18-19-15-16-14-12-0，總距離為828.936768。

從結(jié)果來看，雖然差不多，但是遺傳算法的迭代次數(shù)、群數(shù)數(shù)更多，也就意味著計(jì)算更復(fù)雜，耗時(shí)更多。

六、結(jié)論

本文提出了一種改進(jìn)的蝙蝠算法求解VRPTW問題。實(shí)驗(yàn)結(jié)果表明蝙蝠算法具有較強(qiáng)的尋優(yōu)能力、較高的魯棒性、較少的時(shí)間耗費(fèi)；但蝙蝠算法的改進(jìn)工作仍有不少的前進(jìn)空間，還需要更多的研究與改進(jìn)。