基于遺傳算法的多目標(biāo)路徑優(yōu)化算法的研究

金仙力，李金剛

(南京郵電大學(xué) 計算機學(xué)院 軟件學(xué)院，江蘇 南京 210003)

1 概 述

車輛路由問題(VRP)可以描述為從一個或多個倉庫中心到許多的地理位置分散的客戶的行進路線的問題，此問題受制于許多方面的約束。VRP的目標(biāo)是提供一套以最低成本的車輛路線完成客戶交付的方案。

VRP問題在物流領(lǐng)域起著核心的作用。自從Dantzig和Ramser將VRP問題描述為旅行銷售人員問題(TSP)以來，國內(nèi)外的研究人員已經(jīng)對VRP問題進行了大量的研究。例如簡單的車輛路由問題(CVRP)，在此類問題中，任意一個客戶對所需的商品都有要求，而且車輛的負載也有一定的限制；帶時間限制的車輛路由問題(VRPTW)，在此類問題中，必須在一個特定的時間約束范圍內(nèi)訪問每個客戶；與裝載和交付相關(guān)的車輛路由問題(VRPPD)，在此類問題中，必須以某個特定的數(shù)量裝載和交付商品。

在靜態(tài)VRP中，所有的客戶在規(guī)劃之前就已確定且不再更改。然而，常見的情況是，一旦服務(wù)已經(jīng)開始，客戶、服務(wù)時間或路由成本都可能會時時變化。由于定位系統(tǒng)和通信技術(shù)的最新發(fā)展，目前已經(jīng)可以解決動態(tài)車輛路由問題(DVRP)了。

國內(nèi)外的一些研究人員對DVRP進行了大量研究。比如，Montemanni等[1]對具有容量和持續(xù)時間約束的DVRP做了細化。這些研究人員不僅提出了DVRP的一些基準(zhǔn)實例，而且進行了一個關(guān)于活動度如何影響最終成本的研究。此外，Montemanni等通過將DVRP分解為靜態(tài)VRP序列，然后使用蟻群系統(tǒng)(ACS)算法求解問題，可以將DVRP視為標(biāo)準(zhǔn)VRP的擴展。Branchini等[2]提出了自適應(yīng)粒度局部搜索啟發(fā)式算法。Creput等[3]研究了將自組織圖(SOM)神經(jīng)網(wǎng)絡(luò)操作為基于群體的進化算法的混合方法。Khouadjia等[4]研究了粒子群優(yōu)化(PSO)和可變鄰域搜索(VNS)。Elhassania等[5]將蟻群優(yōu)化(ACO)算法和大鄰域搜索(LNS)算法進行了新的混合。

基于靜態(tài)VRP，可以研究許多不同版本的DVRP。例如，動態(tài)VRPTW被認為是一個標(biāo)準(zhǔn)問題，能很好地適用于允許對一組公共基準(zhǔn)的啟發(fā)式和元啟發(fā)式的比較評估。為了解決這個問題，Housroum等[6]提出了一種進化方法；Hong[7]提出了一個改進的大型鄰域搜索算法。此外還有其他各種DVRP的研究。Attanasio等[8]為動態(tài)多車輛撥號問題提供了一個平行的禁忌搜索啟發(fā)式方法。Gendreau等[9]提出了鄰居搜索啟發(fā)式方法，以拾取和遞送位置的實時新請求為基礎(chǔ)優(yōu)化車輛的計劃路線。張迅等[10]研究了快遞的同時送取貨車輛路徑問題(VRPSDP)，設(shè)計了一種優(yōu)化算法，算法通過基于適應(yīng)度排名和最優(yōu)個體保留的選擇策略和自適應(yīng)交叉概率參數(shù)控制遺傳算法，以保證所求結(jié)果的優(yōu)良性。文獻[11-16]中則是成功將遺傳算法應(yīng)用于解決各類VRP問題，為其他研究提供了有效的參考價值。薛明等[17]基于Small-World模型構(gòu)建了云網(wǎng)格路網(wǎng)模型，實現(xiàn)了車輛的集成調(diào)度,提高了車輛運輸效率。侯占亭[18]則是針對多個優(yōu)化目標(biāo)進行了研究，通過改進基于分解的多目標(biāo)進化算法，實現(xiàn)了路徑優(yōu)化。于銳等[19]考慮了多種約束條件，比如時間約束、車載約束等，通過改進節(jié)約算法解決了開放式VRP。

綜上。關(guān)于VRP問題的研究眾多，但它們都有一個共同的問題，即服務(wù)點都是無序的。然而有些情況下，一些服務(wù)點是有順序要求的，即必須按一定順序為這些點提供服務(wù)。而在這方面的研究相對較少，因此文中的重點就是研究服務(wù)點有序的VRP問題。

2 DVRP問題的描述與建模

2.1 問題描述

以餐飲配送環(huán)境下的研究為目標(biāo)，DVRP可以描述為：送餐人員從配送點出發(fā)到多個商家和客戶進行取餐或送餐(對于同一訂單，必須先取餐再送餐)，選擇合適的送餐人員并合理組織其送餐路徑，使送餐人員從配送點出發(fā)，能夠合理地經(jīng)過每個商家和客戶點，并在滿足每個商家和客戶取餐量和送餐量的需求、送餐人員的承載限制以及商家和客戶的時間限制需求等約束條件下，以最低的總成本為每個商家和客戶提供服務(wù)。文中研究的問題屬于DVRP，結(jié)合餐飲配送的特點，可以對問題做一些相應(yīng)的假設(shè)，如下所示：

(1)只考慮單送餐人員，且具有載重量約束條件；

(2)送餐人員從配送中心出發(fā)，且送餐人員配送途中不接單，在服務(wù)點的取餐和送餐不消耗時間；

(3)每個服務(wù)點都會被訪問，且只訪問一次；

(4)商家服務(wù)點和客戶服務(wù)點均有時間約束，超過這個時間就會產(chǎn)生懲罰；

(5)路徑優(yōu)化的目標(biāo)：行駛成本最低，懲罰成本最低，總成本最低。

2.2 建立模型

(1)總成本最低化模型。

配送總成本包含三個部分，即不變成本、行駛成本與懲罰成本。其中不變成本包含車輛維護、送餐人員工資等，此成本是固定不變的；行駛成本則包含油耗等，此成本和行駛時間相關(guān)；懲罰成本是指因未在客戶要求的時間內(nèi)提供服務(wù)而產(chǎn)生的成本。

(2)行駛成本最低化模型。

行駛成本和行駛的距離相關(guān)。假設(shè)送餐人員行駛速度固定，則行駛距離和行駛時間線性相關(guān)，所以行駛成本也就和行駛時間相關(guān)。用n表示客戶數(shù)量，tij表示送餐人員從客戶i到客戶j之間的行駛時間?？山⒆畹突旭偝杀镜臄?shù)學(xué)模型如下：

(1)

決策變量：

(2)

(3)

其中，Xij為0表示送餐人員沒有從服務(wù)點i到服務(wù)點j提供服務(wù)，Xij為1表示送餐人員從服務(wù)點i到服務(wù)點j提供服務(wù)；Yi為0表示送餐人員沒有給服務(wù)點i提供服務(wù)，Yi為1表示送餐人員給服務(wù)點i提供服務(wù)。

約束條件為：

(4)

Yi=1

(5)

(6)

(7)

(8)

式(4)中，Pi表示服務(wù)點i的需求量，此式的含義是送餐人員的實際載重量小于或等于額定載重量Q；式(5)的含義是指每個服務(wù)點只能由一個送餐人員提供服務(wù)；式(6)、(7)表示送餐人員只能從一個服務(wù)點出發(fā)，并最終到另一個服務(wù)點去；式(8)的含義是必須要為每個服務(wù)點提供服務(wù)。

(3)懲罰成本最低化模型。

每個商家和客戶都有時間約束要求，送餐人員必須在規(guī)定時間內(nèi)提供服務(wù)，否則會產(chǎn)生時間懲罰。根據(jù)外賣配送特點，假定服務(wù)點i的時間約束要求為[0,Ei]，送餐人員到達服務(wù)點i的時間點為Ti，則可建立最低化懲罰成本的數(shù)學(xué)模型如下：

(9)

(4)綜合總成本模型。

因固定成本不變，所以要使配送總成本最低化，只需考慮行駛成本與懲罰成本即可。可建立最低化總成本的數(shù)學(xué)模型如下：

Z=w1Z1+w2Z2=

(10)

其中，Z表示總成本；Z1表示行駛成本；Z2表示懲罰成本；w1、w2表示兩種成本的權(quán)重值。

3 基于遺傳算法的路徑優(yōu)化

3.1 遺傳算法

遺傳算法(genetic algorithm)是一種基于適者生存思想的算法。由于遺傳算法采用隨機化搜索，所以由遺傳算法得出的結(jié)果存在一定的不確定性，即無法保證得到的結(jié)果是最好的結(jié)果。不過，通過一些改進方法，可以有效改善遺傳算法的局限性，可以在可接受的代價下得到所需的結(jié)果。

3.2 遺傳算法的設(shè)計

(1)染色體編碼。

文中采用自然數(shù)編碼，用1,2,…,n表示n個服務(wù)點。編碼時，將兩個“0”(代表配送中心)分別作為染色體的頭部和尾部，如“0,1,2,3,0”，次染色體表示送餐人員從配送中心出發(fā)，依次經(jīng)過服務(wù)點1、服務(wù)點2、服務(wù)點3，最終回到配送中心。

(2)產(chǎn)生初始種群。

最終解的優(yōu)劣和初始種群有很大關(guān)系，因此初始種群的質(zhì)量和規(guī)模要合理。為了得到一個比較合理并且能夠較快收斂的初始種群，采用隨機方法產(chǎn)生初始種群。即先得到[1,n]之間的所有整數(shù)，并打亂這些整數(shù)的排列，然后作為初始種群。

(3)計算適應(yīng)度。

適應(yīng)度是遺傳算法中一個非常重要的因素，它是遺傳算法進行遺傳操作時的重要依據(jù)。因此一個科學(xué)合理的適應(yīng)度計算方法能夠有效地改善遺傳算法，使之更加合理，更加高效。適應(yīng)度的計算所遵循的規(guī)則也比較簡單，即個體的結(jié)果越接近目標(biāo)值，個體的適應(yīng)度就越高。

(4)選擇算子。

選擇操作是從已知的種群中挑選出一個個體。因此，選擇操作的優(yōu)劣在一定程度上決定了遺傳算法的優(yōu)劣。選擇操作以適應(yīng)度為依據(jù)，因此適應(yīng)度的計算非常關(guān)鍵。選擇操作的結(jié)果往往是選擇出適應(yīng)度高的個體。

(5)交叉算子。

將選擇出的個體，采用隨機的方法進行匹配，產(chǎn)生一個完全不同的個體。具體操作方法為：隨機在上一代個體中選擇兩個個體，并產(chǎn)生兩個交叉段，將所選擇的交叉段插入到另一個個體前端，并逐一去掉個體中與交叉段重復(fù)的染色體，以此得到新一代的個體。

(6)變異算子。

為了使種群更加豐富多樣，可以執(zhí)行變異操作。變異操作就是改變個體兩個算子的位置。變異算法選擇算子位置的方法是隨機的，因此有一定的可能性會得到一個新的個體。

(7)調(diào)整算子。

結(jié)合餐飲配送的特點，即必須先到商家取貨后才能給客戶送貨，需要對新產(chǎn)生的種群進行調(diào)整。將不滿足條件的算子進行位置調(diào)整。

文中優(yōu)化算法流程如下：

Step1：對客戶點進行編碼，并獲得初始種群。

Step2：首尾插入0并標(biāo)記適應(yīng)度，獲得一個種群。

Step3：對種群進行選擇、交叉、變異、調(diào)整操作，獲得新的個體。

Step4：若滿足收斂條件，終止算法，否則進入Step2。

4 算法驗證與分析

為了驗證模型與算法的合理性與有效性，以南郵附近的外賣配送為例。假設(shè)配送員手中有5個訂單，訂單具體情況如表1所示。

如表1所示，每個訂單包含商家地址、客戶地址和時間窗信息。如1號訂單，送餐人員要先到小馬牛肉面取貨，然后才能到學(xué)6宿舍送貨，并且必須在15分鐘內(nèi)到達小馬牛肉面和學(xué)6宿舍，否則將會產(chǎn)生時間懲罰。

表1 訂單詳情

假定配送中心為南郵大廈，根據(jù)以上訂單信息，可整理出服務(wù)點的編號和地理位置、取貨量、送貨量和時間窗信息，如表2所示。

表2 服務(wù)節(jié)點的地理位置、取貨量、送貨量和時間窗信息

如表2所示，若服務(wù)點的取貨量不為0，且送貨量為0，則代表此服務(wù)點為商家；若服務(wù)點的取貨量為0，且送貨量不為0，則代表此服務(wù)點為下訂單的客戶。

為了計算總成本，需要知道每個服務(wù)點之間的行駛時間，從百度地圖應(yīng)用上可獲取各個服務(wù)點之間的行駛時間，結(jié)果如表3所示。

表3 各個服務(wù)點之間的行駛時間 min

在表3中，每個編號代表一個服務(wù)點，其對應(yīng)關(guān)系如表2所示。表3中的每個數(shù)據(jù)代表在兩個服務(wù)點之間行駛所需要的時間。如4(第3行第4列)代表從編號1服務(wù)點到編號2服務(wù)點所需行駛時間為4min，即從小馬牛肉面到亦明亮黃燜雞需要行駛4min。

假設(shè)行駛成本的權(quán)重w1和懲罰成本的權(quán)重w2分別取值1和5，此時在WAMP上運行6次，所得結(jié)果如表4所示。

表4 運行結(jié)果

在表4中，迭代次數(shù)表示算法運行次數(shù)，當(dāng)滿足迭代次數(shù)時，算法會終止。此時，會出一個解集。由于遺傳算法的特性，每次運行時，雖然迭代次數(shù)可能相同，但解集卻可能不同，最終導(dǎo)致得到的解也可能不同。不過隨著迭代次數(shù)的增加，得到的解會慢慢趨于一個穩(wěn)定值。穩(wěn)定后的解的總成本為30，其中行駛成本20，懲罰成本10。此時得到的路徑為0231657480，即送餐人員送餐的路徑為：南郵大廈-亦明亮黃燜雞-三子包子-小馬牛肉面-無線樓-學(xué)6宿舍-科技樓-徐州地鍋-學(xué)2宿舍-南郵大廈。經(jīng)驗證結(jié)果有效。

和傳統(tǒng)遺傳算法做比較，它們的收斂情況如圖1所示。

圖1 算法收斂曲線

從圖1中可以看出，文中算法的收斂速度明顯高于普通的遺傳算法，其收斂更快，效率更高，說明該算法有效、可行。

5 結(jié)束語

根據(jù)外賣配送的特點，提出了一種基于遺傳算法的改進算法?；谕赓u配送的實例進行了實驗驗證，表明該算法能夠更快收斂，可以很好地解決服務(wù)點有序的VRP問題。

[1] MONTEMANNI R,GAMBARDELLA L M,RIZZOLI A E,et al.Ant colony system for a dynamic vehicle routing problem[J].Journal of Combinatorial Optimization,2005,10(4):327-343.

[2] BRANCHINI R M,ARMENTANO V A,LOKKETANGEN A.Adaptive granular local search heuristic for a dynamic vehicle routing problem[J].Computers & Operations Research,2009,36(11):2955-2968.

[3] CREPUT J C,HAJJAM A,KOUKAM A,et al.Self-organizing maps in population based metaheuristic to the dynamic vehicle routing problem[J].Journal of Combinatorial Optimization,2012,24(4):437-458.

[4] KHOUADJIA M R,SARASOLA B,ALBA E,et al.A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests[J].Applied Soft Computing,2012,12(4):1426-1439.

[5] ELHASSANIA M,JAOUAD B,AHMED E A.A new hybrid algorithm to solve the vehicle routing problem in the dynamic environment[J].International Journal of Soft Computing,2013,8(5):327-334.

[6] HOUSROUM H,HSU T,DUPAS R,et al.A hybrid GA approach for solving the dynamic vehicle routing problem with time windows[C]//Information and communication technologies.[s.l.]:IEEE,2006:787-792.

[7] HONG L.An improved LNS algorithm for real-time vehicle routing problem with time windows[J].Computers & Operations Research,2012,39(2):151-163.

[8] ATTANASIO A,CORDEAU J F,GHIANI G,et al.Parallel Tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem[J].Parallel Computing,2004,30(3):377-387.

[9] GENDREAU M,GUERTIN F,POTVIN J Y,et al.Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries[J].Transportation Research Part C:Emerging Technologies,2006,14(3):157-174.

[10] 張 迅,劉海東,李 丹,等.基于遺傳算法的快遞配送車輛路徑問題研究[J].物流技術(shù),2013,32(3):263-267.

[11] 王振鋒,王 旭,葛顯龍.基于遺傳算法的不同約束條件車輛調(diào)度問題研究[J].計算機應(yīng)用研究,2010,27(10):3673-3675.

[12] 袁麟博,章衛(wèi)國,李廣文.一種基于遺傳算法-模式搜索法的無人機路徑規(guī)劃[J].彈箭與制導(dǎo)學(xué)報,2009,29(3):279-282.

[13] 鄺航宇,金 晶,蘇 勇.自適應(yīng)遺傳算法交叉變異算子的改進[J].計算機工程與應(yīng)用,2006,42(12):93-96.

[14] 盧月品,趙 陽,孟躍強,等.基于改進遺傳算法的狹窄空間路徑規(guī)劃[J].計算機應(yīng)用研究,2015,32(2):413-418.

[15] 雷偉軍,程筱勝,戴 寧,等.基于改進遺傳算法的多模型加工路徑規(guī)劃[J].機械工程學(xué)報,2014,50(11):153-161.

[16] 莊 健,楊清宇,杜海峰,等.一種高效的復(fù)雜系統(tǒng)遺傳算法[J].軟件學(xué)報,2010,21(11):2790-2801.

[17] 薛 明,許德剛.基于云網(wǎng)格集成調(diào)度的防擁堵車輛路徑規(guī)劃算法[J].計算機科學(xué),2015,42(7):295-299.

[18] 侯占亭.基于分解和決策空間相似性度量的進化多目標(biāo)車輛路徑規(guī)劃算法研究[D].西安:西安電子科技大學(xué),2014.

[19] 于 銳,曹介南,朱培棟.車輛運輸路徑規(guī)劃問題研究[J].計算機技術(shù)與發(fā)展,2011,21(1):5-8.