黃 震，羅中良，黃時慰

(惠州學院 計算機科學系，廣東惠州，516007)

?

一種帶時間窗車輛路徑問題的混合蟻群算法*

黃 震，羅中良，黃時慰

(惠州學院 計算機科學系，廣東惠州，516007)

針對帶時間窗車輛路徑問題求解時蟻群算法存在容易陷入局部最優(yōu)，而遺傳算法初始種群的優(yōu)劣對算法有效性存在直接影響，提出一種混合蟻群優(yōu)化算法。算法首先在蟻群算法的節(jié)點選擇概率公式中引入時間窗因素，以得到初始種群，然后通過遺傳算法的交叉算子和變異算子對初始種群中的較優(yōu)路徑進行交叉和變異操作，從而得到更優(yōu)的路徑。通過Matlab環(huán)境下對文中混合算法進行仿真實驗，在車輛利用率和路徑規(guī)劃上效果明顯，表明了算法的高效性，同時混合算法可以避免陷入局部最優(yōu)。

蟻群算法；遺傳算法；車輛路徑問題；時間窗

車輛路徑問題(Vehicle Routing Problem,VRP)是一類經典的組合優(yōu)化問題。一般指對一系列的客戶點組織適當的行車路線，使車輛有序地通過它們，在滿足一定的約束條件(如貨物需求量、車輛容量限制等)下，達到一定的目標(如距離最短、費用最少等)，帶時間窗車輛路徑問題(Vehicle Routing Problem with Time Windows,VRPTW)是在VRP的基礎上要求在配送過程中按照客戶要求在一定的時間窗內到達客戶點，即在不違背車輛容量限制、時間限制等約束條件的前提下，合理制定運輸時的車輛配送路徑方案，以盡可能小的成本滿足處在不同地理位置的客戶對貨物運送和服務時間的要求[1]。由于VRPTW帶有服務時間的訪問限制，VRPTW比VRP更貼近實際應用，廣泛地應用于交通和物流領域，由于VRPTW是NP難問題，主要都是使用啟發(fā)式算法[2-3]來求解，已有不少學者對該問題進行了相關的研究[4-11]。其中，李全亮[4]提出利用螞蟻算法求解VRPTW，從數值計算上探索了螞蟻算法的優(yōu)化能力，獲得了滿意的效果；李琳等[5]將蟻群系統(tǒng)與最大最小螞蟻系統(tǒng)相結合，并在狀態(tài)轉移規(guī)則中引入時間窗跨度與服務等待時間因素；何小鋒等[6]提出一種量子蟻群算法，增加量子比特啟發(fā)因子、利用量子旋轉門實現信息素更新，實驗表明該算法求解VRPTW比蟻群算法效率更高；吳天羿等[7]在初始種群的產生、交叉、變異等方面對遺傳算法進行改進，在求解VRPTW中比遺傳算法更有效。

本文首先使用蟻群算法求解VRPTW，實驗結果發(fā)現蟻群算法存在容易陷入局部最優(yōu)的缺點，于是將蟻群算法和遺傳算法相結合，通過蟻群算法產生初始種群，然后進行交叉和變異操作，實驗結果表明混合算法不僅可以避免陷入局部最優(yōu)，而且具有比較快的收斂速度和良好的全局尋優(yōu)能力，能夠有效的求解VRPTW。

1 VRPTW的數學模型

VRPTW描述為[12]：某倉庫有k輛車，每輛車的最大載重量為w，需要為n個客戶配送貨物， 其中倉庫編號為0，客戶編號為1至n，每輛車從倉庫出發(fā)為客戶送貨，最終回到倉庫，qi(i=1,2…,n)為各客戶的貨物需求量，ati表示車輛到達客戶i的時間，wti表示車輛在客戶i的等待時間，sti表示車輛在客戶i的服務時間，tij表示車輛從客戶i到客戶j的行駛時間，[ei,li]是客戶i的時間窗，即客戶i的最早開始服務時間為左時間窗ei，最遲開始服務時間為右時間窗l(fā)i，Cij為車輛從客戶i到客戶j的配送成本。

引入決策變量Xijk，其取值如下：

(1)

VRPTW的目標函數表示為：

(2)

一般情況下VRPTW的目標有2個，第一目標是配送的車輛數K最少，第二目標是總配送距離最短，所以需要在式(2)中將p1和p2的值設置為p1?p2。

VRPTW的約束條件如下：

?j∈{1,2,...,n}

(3)

(4)

(5)

(6)

(7)

ati≤li,?i∈{1,2,...,n}

(8)

ei≤ati+wti≤li,?i∈{1,2,...,n}

(9)

ati+wti+sti+tij+(1-xijk)p3≤atj

?i,j∈{1,2,...,n},?k∈{1,2,...,K}

(10)

wti=max{0,ei-ati},?i∈{1,2,...,n}

(11)

ati≥0,?i∈{1,2,...,n}

(12)

wti≥0,?i∈{1,2,...,n}

(13)

sti≥0,?i∈{1,2,...,n}

(14)

其中式(3)、(4)約束每個客戶只由唯一車輛服務；式(5)是對倉庫約束，即由倉庫出發(fā)和回到倉庫的車輛都是K輛；式(6)車輛的載重約束；式(7)為次回路消除條件，式(8)至式(14)是時間窗約束。

2 混合蟻群算法求解VRPTW

2.1 求解VRPTW的編碼方式

本文在求解VRPTW時采用整數編碼方式[13]，需要編碼的包括初始種群的染色體個體和每個染色體對應的解路徑，本文采用0表示倉庫(有K輛車)，1至n表示客戶編號，具體編碼方式如下：

1)每個染色體個體采用一個n維整型向量[r1,r2,...,rn]表示，ri∈{1,2,…,n}，每個ri對應一個客戶。

2)解路徑采用一個n+K+1維的整型向量[t1,t2,...,t(n+K+1)]表示，tj∈{0,1,…,n}，每個tj對應倉庫或客戶。

每個染色體個體對應一個解路徑，由染色體個體求解路徑的基本原理是求出K條子路徑，每條子路徑對應一輛車的行駛回路，具體求解方法如下：

1)將解路徑向量的第一維分量t1賦值為0，表示車輛由倉庫出發(fā)；

2)定義變量Q(初始值為0)，將染色體個體中的客戶r1的貨物需求量加到Q中，如果Q不超過車輛的最大載重量則計算atr1(即從倉庫到達客戶r1的時間)，如果atr1沒有超過客戶r1的時間窗則將r1加入到解向量中(即將r1賦值給解路徑向量的第二維t2)；

3)按步驟2類似的方法繼續(xù)計算染色體個體向量中r1后面的每一個客戶ri，如果滿足重量約束和時間窗約束則將ri加入到解向量中，如果Q超重或者atr1超過時間窗則不把ri加入到解路徑向量中，而是將倉庫編號0加入到解路徑向量中(表示車輛回到倉庫)，這樣在解路徑向量中就構成了子路徑1；

4)按照步驟2、3的方法遍歷染色體個體向量中剩下的客戶編號，可以求出所有子路徑。

2.2 求解VRPTW的混合蟻群算法

算法的流程如圖1所示。

圖1 混合蟻群算法流程圖Fig.1 Flow diagram of hybrid ant colony algorithm

2.2.1 蟻群算法產生新種群 首先采用的蟻群算法求解VRPTW的新種群，具體步驟如下。

1)設置螞蟻數量(一般與客戶數相同)，每只螞蟻的節(jié)點選擇概率如式(15)所示

(15)

其中τik是指邊(i，k)上的信息素，ηik是指與邊(i，k)相關的啟發(fā)信息函數，一般取1/d(i,k)，d(i,k)為節(jié)點i與k之間的距離；α和β分別為信息素因子和啟發(fā)因子，分別影響信息素和啟發(fā)信息函數的重要程度。

Tik是時間窗信息函數，γ是時間窗信息因子，Tik計算方法如式(16)

(16)

waitj是車輛在節(jié)點j的等待時間，當車輛到達節(jié)點j的時間atj早于節(jié)點的左時間窗ej時，等待時間取值為ej-atj，若車輛到達時間晚于左時間窗ej且早于右時間窗l(fā)j則將等待時間設置為較小的數；lj-ej為節(jié)點j的時間窗跨度，在等待時間相同的情況下時間窗跨度越小的節(jié)點應該優(yōu)先選擇，由公式(16)可知，等待時間越短、時間窗跨度越小的節(jié)點選擇概率越大，使得車輛配送的效率越高。

2)當螞蟻從節(jié)點i選中節(jié)點j后，應該減少邊(i,j)的信息素，這樣可以增加螞蟻選擇其他節(jié)點的概率，本文按照式(17)更新邊(i,j)上的信息素

τij=(1-ρ)τij+ρΔτij

Δτij=Q/lk

(17)

其中ρ∈[0,1]為信息素揮發(fā)系數，Q是信息素大小(通常取常數)，lk是指本次迭代中第k只螞蟻已經走過的路徑長度。

3)每只螞蟻按照步驟1選擇完所有節(jié)點后即產生一個染色體個體，所有螞蟻產生的染色體個體構成初始群體。

2.2.2 計算適應值 產生了新種群后，需要計算各染色體個體對應的適應值，具體步驟如下。

1)各染色體個體按照2.1的方法求解對應的解路徑；

2)解路徑的子路徑數量即配送需求的車輛數K，將各子路徑的配送成本全部加起來求出總配送成本后，根據公式(2)計算出染色體個體的適應值；

3)比較各染色體對應的適應值，更新當代局部最小值lbest和全局最小值gbest。

2.2.3 交叉和變異操作 遺傳算法的交叉操作可以提高算法的全局搜索能力，本文在蟻群算法產生的新種群中選取兩個染色體個體作為父代進行交叉操作，進行交叉的父代個體選擇方法如下。

1)選取當代局部最小值lbest作為第一個父代個體；

2)為了更有利于后代的進化效果，第二個父代需要選擇與lbest有一定差異的個體[14]，具體做法是先隨機選擇一個染色體個體作為父代2，然后計算兩個父代的適應值F1和F2以及當前迭代適應值的最大值Fmax和最小值Fmin，接著計算(F1-F2)/(Fmax-Fmin)的絕對值，如果結果大于給定的閾值則開始交叉操作，否則重新選擇第二個父代。

按照上述方法選擇了兩個父代個體后，開始交叉操作，本文算法采用了部分匹配交叉算子，交叉操作具體步驟如下。

1)隨機產生兩個交叉位作為交叉區(qū)域；

2)將兩個父代的交叉區(qū)域分別加入對方的末尾；

3)分別刪除兩個父代中與交叉區(qū)域相同的客戶點即產生兩個新的個體；

4)計算新個體的適應值，如果新個體更優(yōu)則更新局部最小值lbest和全局最小值gbest。

例如，父代個體1為X=[3 1 8 4 2 6 7 5]，父代個體2為Y=[2 8 5 7 3 4 6 1]，隨機產生兩個交叉位分別為3和6，取出X的第3至第6位[8 4 2 6]作為交叉區(qū)域，Y的第3至第6位[5 7 3 4]作為交叉區(qū)域，將交叉區(qū)域加入到對方末尾后兩個個體分別成為[3 1 8 4 2 6 7 5 5 7 3 4]和[2 8 5 7 3 4 6 1 8 4 2 6]，分別刪除相同客戶點后產生兩個新個體為[1 8 2 6 5 7 3 4]和[5 7 3 1 8 4 2 6]。

變異操作相對交叉操作更簡單，一般只需要將染色體個體中的某一位與另一位交換即可，通過變異可以提高算法的局部搜索能力，本文算法的變異操作的步驟如下。

1)選取當代局部最小值lbest作為變異的個體；

2)在lbest的兩條不同子路徑上分別產生1個變異位，計算兩個變異位交換后的個體適應值，如果適應值更優(yōu)則保留變異后的個體。

3)如果變異后的個體更優(yōu)則更新局部最小值lbest和全局最小值gbest。

2.2.4 全局更新信息素 當一次迭代結束后，需要更新每條邊的信息素，信息素按照式(18)的方法更新

(18)

(19)

其中信息素大小Q為常數，Lk為第k只螞蟻在本次迭代的路徑總長度。

3 仿真實驗

3.1 實驗的參數設置

本文使用Matlab對算法進行仿真實驗，其中蟻群算法的各參數設置為：α=1，β=5，γ=2，ρ=0.1，q0=0.7，Q=100；遺傳算法的交叉概率設置為0.9，閾值設置為0.2，變異概率設置為0.2，求解目標函數時p1設置為10 000，p2設置為1。

3.2 實驗及結果分析

3.2.1 實驗1 實驗1采用VRPTWBENCHMARKPROBLEMS測試集的數據，該測試集的數據分為C類(客戶的地理位置集中分布)、R類(客戶的地理位置隨機分布)和RC類(客戶的地理位置集中和隨機相混合)3種數據集，本實驗選取3類數據中有25個客戶的C101-25、R101-25、RC101-25和有100個客戶的C101-100、R101-100、RC101-100共6組數據，6組數據的理想解如表1所示。

表1 測試集的理想解Table 1 Optimal Solutions of the test problems

本文分別使用蟻群算法和本文算法進行10次仿真實驗，25個客戶的數據迭代次數為400次，100個客戶的數據迭代次數為800次，蟻群算法和本文算法求出的最好解的結果如表2所示。

表2 實驗1的仿真結果Table 2 Simulation results of the first experiment

由表2可知，本文算法在6組數據中無論在車輛數還是在配送的路徑長度都明顯優(yōu)于蟻群算法的結果。在6組數據中，本文算法的都得到了理想解的車輛數，誤差率均為0，而路徑長度的誤差率分別是0、0.1%、0.19%、0.43%、2.23%和4.61%，結果都非常接近理想解，其中C101-25得到了理想解，C101-25的配送路線如圖2所示，圖2中的X坐標和Y坐標是倉庫和客戶位置的坐標，路線圖由3輛車配送，路徑長度為191.813 6，由3條子路徑構成，分別是0-5-3-7-8-10-11-9-6-4-2-1-0、0-20-24-25-23-22-21-0、0-13-17-18-19-15-16-14-12-0，其中0表示倉庫號，1至25表示客戶號。

圖2 C101-25的車輛配送路線圖Fig.2 Vehicle distribution routing for C101-25

3.2.2 實驗2 為了更好的說明本文算法求解VRPTW的有效性，實驗2采用文獻[5]中的數據，實驗數據包括1個倉庫和20個客戶，分布在邊長為200km的正方形區(qū)域，倉庫的坐標為145km,130km，每輛車的載重量為8t，車輛的行駛速度為60km/h，忽略車輛在客戶點的服務時間，20個客戶的具體數據如表3所示。

表3 客戶的具體數據Table 3 Data of customers

文獻[5]得到的最好解是3輛車進行配送，車輛利用率分別是96.25%、100%和100%，配送路徑總長度為1 266.01km，本實驗對上述數據進行仿真實驗10次，實驗的迭代次數400次，實驗結果如表4所示。

表4 實驗2的仿真結果Table 4 Simulation results of the second experiment

由表4可知，本文算法得到的最差解都比文獻[5]的最好解的路徑總長度更短，最好解的路徑總長度為1 249.27km，對應的3條子路徑分別是：0-7-8-15-16-13-20-0、0-5-14-4-3-17-11-0、0-18-1-10-2-12-9-19-6-0，車輛利用率分別是98.75%、97.5%和100%，實驗表明本文算法的結果在同樣使用3輛車配送的基礎上，車輛的使用率更加平均，路徑的總長度則更短。

4 結 論

本文將蟻群算法和遺傳算法相結合來求解VRPTW，介紹了求解VRPTW的編碼和解碼方法、產生新種群的方法、交叉和變異以及全局更新信息素的方法。進行了兩個仿真實驗，實驗1驗證了本文算法在求解VRPTW時比基本蟻群算法更加有效，實驗2表明本文算法比文獻[5]的結果更優(yōu)，說明本文算法是求解VPRTW的有效算法。

[1] 蔣波．基于遺傳算法的帶時間窗車輛路徑優(yōu)化問題研究[D]．北京：北京交通大學，2010．

[2] 羅中良,易明珠.最優(yōu)化問題的蟻群混合差分進化算法研究[J].中山大學學報：自然科學版，2008，47(3)：37-41

[3] 羅中良,易明珠,唐華,等.開Y-開Δ變壓器相序調整的蟻群優(yōu)化方法及收斂性研究[J]．中山大學學報：自然科學版，2007，46(2)：29-32

[4] 李全亮．螞蟻算法在帶時間窗車輛路徑問題中的應用研究[J]．數學的實踐與認識，2006，36(10)：173-178．

[5] 李琳,劉士新,唐加福．改進的蟻群算法求解帶時間窗的車輛路徑問題[J]．控制與決策，2010，25(9)：1378-1382．

[6] 何小鋒,馬良．帶時間窗車輛路徑問題的量子蟻群算法[J]．系統(tǒng)工程理論與實踐，2013，33(5)：1255-1261．

[7] 吳天羿，許繼恒，劉建永，等．求解有硬時間窗車輛路徑問題的改進遺傳算法[J]．系統(tǒng)工程與電子技術，2014，36(4)：708-712．

[8] 袁建清.求解動態(tài)車輛調度問題的混合禁忌搜索算法[J].計算機應用與軟件，2012，29(4)：148-150．

[9] 李進,傅培華．基于能耗的帶時間窗車輛路徑問題建模與仿真[J]．系統(tǒng)仿真學報，2013，25(6)：1147-1154．

[10] 王飛．帶時間窗車輛調度問題的改進粒子群算法[J]．計算機工程與應用，2014，50(6)：226-229．

[11] 戚銘堯，張金金，任麗．基于時空聚類的帶時間窗車輛路徑規(guī)劃算法[J]．計算機科學，2014，41(6)：218-221．

[12] 潘立軍．帶時間窗車輛路徑問題及其算法研究[D]．長沙：中南大學，2012．

[13] 黃震．混合量子粒子群算法求解車輛路徑問題[J]．計算機工程與應用，2013，49(24)：219-223．

[14] 周艷聰，孫曉晨，余偉翔．基于改進遺傳算法的物流配送路徑優(yōu)化研究[J]．計算機工程與科學，2012，34(10)：118-122．

Application Research of Hybrid ant Colony Algorithm in Vehicle Routing Problem with Time Windows

HUANGZhen,LUOZhongliang,HUANGShiwei

(Department of Computer Science, Huizhou University, Huizhou 516007, China)

A hybrid ant colony algorithm was proposed.Because, ant colony algorithm used to solve the vehicle routing problem with time windows (VRPTW) is easy to fall into local optimum, and the quality of initial population in genetic algorithm affects the effectiveness of the algorithm directly. Firstly, the algorithm introduces the factors of time windows into node selection probability formula of ant colony algorithm to get the initial population. Secondly， the crossover and the mutation were operated to get a better path for the initial population. Applying Matlab environment for hybrid algorithm simulation, the effects on the vehicle utilization and path planning is obvious. It shows the algorithm is efficient, and can avoid falling into local optimum.

ant colony algorithm；genetic algorithm；vehicle routing problem；time window

2014-06-22

廣東省科技計劃資助項目(2012B010100038);廣東省高等學校教學質量與改革工程本科類資助項目(粵高教函【2013】113號-113)、惠州市科技計劃資助項目(A512.0234)、全國大學生創(chuàng)新訓練資助項目(105771300)

黃震(1980年生 )，男；研究方向：智能算法、無線傳感器網絡;通訊作者:羅中良;E-mail:195146501@qq.com

10.1347/j.cnki.acta.snus.2015.01.009

TP301.6

A

0529-6579(2015)01-0041-06