基于混合遺傳算法的車輛路徑優(yōu)化問題研究?

胡乃平 于豐平

1 引言

近些年來，隨著大眾時間意識的提高，對時間精度的要求也隨之提高?？爝f作為服務(wù)行業(yè)，時間是影響行業(yè)內(nèi)競爭的重要指標(biāo)之一［1］。在客戶要求的時間窗內(nèi)將快遞送達到客戶手中，將是硬時間窗問題的追求目標(biāo)，這一追求依賴于合理的車輛路徑調(diào)度方案。

車輛路徑問題（Vehicle Routing Problem）是調(diào)度系統(tǒng)中的關(guān)鍵環(huán)節(jié)，該問題由Dantzig和Ramser于1959年首次提出，自此，國內(nèi)外學(xué)者對求解此問題進行了諸多研究。其經(jīng)典算法之一是可得到更好解的順序插入啟發(fā)式算法和基于預(yù)見性貪婪規(guī)則的插入啟發(fā)式算法［2］。其二是結(jié)合量子計算提出了量子蟻群算法。通過定義人工螞蟻的轉(zhuǎn)移概率，增加量子比特啟發(fā)式因子，從而提高算法的全局搜索能力。但是求解問題規(guī)模較小，難以應(yīng)用目前的大規(guī)模數(shù)據(jù)［3］。其三在靜態(tài)VRP模型基礎(chǔ)之上，提出動態(tài)VRP模型。初始階段采用改進的遺傳算法，實時優(yōu)化階段采用適用于對已有路徑進行改造的模擬退火法。但是該模型考慮因素不周全，只考慮了時間窗限制，沒有考慮到最大行駛距離、行駛道路情況、交通擁堵等突發(fā)現(xiàn)象［4］。其四是將最小化車輛數(shù)和總行駛距離為目標(biāo)函數(shù)，應(yīng)用混合種群增量算法求解［5］。其五提出了基于改進遺傳算法的車輛路徑調(diào)度算法，但是建立數(shù)學(xué)模型時，沒有考慮時間窗限制，沒有強調(diào)時間思想［6］。本文將針對交通擁堵的現(xiàn)狀，在傳統(tǒng)硬時間窗物流配送車輛調(diào)度問題模型之上，以時間作為影響車輛路徑選擇的首要因素，建立數(shù)學(xué)模型，將分解協(xié)調(diào)算法與遺傳算法混合，求解最優(yōu)解。

2 車輛調(diào)度模型

傳統(tǒng)帶時間窗的車輛調(diào)度問題分為軟硬時間窗兩類，其判斷依據(jù)是相較于客戶要求的時間窗，快遞提前或推后到達是否允許懲罰。硬時間窗問題要求快遞必須在用戶規(guī)定的時間窗內(nèi)對客戶進行驗證（每個客戶僅被服務(wù)一次）。如果不能在用戶規(guī)定的時間窗內(nèi)完成驗證，則要引入適當(dāng)?shù)难诱`懲罰［3，7］。為了反映懲罰約束關(guān)系，同時本文以時間為主線，所以懲罰換算成相應(yīng)的時間，即若未能滿足客戶時間窗要求，則懲罰快遞人員的時間成本，所以建立如圖1所示的懲罰函數(shù)（其中M表示無窮大）。

圖1 懲罰函數(shù)定義圖

上圖中，Etime表示懲罰時間，t為快遞車輛到達客戶點的時間。[g,h]為客戶所要求的最佳服務(wù)時間范圍。g為最佳最早服務(wù)時間，h為最佳最晚服務(wù)時間，在此時間段內(nèi)，不會造成任何提前或推遲成本；[e,g]和[h,l]為客戶可接受的時間段，但會造成一定的提前或推遲成本；l之后，客戶將沒法或拒接簽收快遞，此時將造成無窮大的推遲時間成本，用一個無窮大的懲罰成本M來表示，即：

快遞到達服務(wù)地點途中，不同時間，不同地點，會造成不同程度的擁堵，即

上式中，Tc表示擁堵程度，i表示地點，ts，te分別表示擁堵的開始時間和結(jié)束時間，Rlo，Rme，Rhi分別表示輕度擁堵、中度擁堵和高度擁堵的地點。不同程度的擁堵，會造成不同程度的等待時間，如圖2所示。

圖2 交通擁堵等待時間圖

上圖中，Tc表示擁堵情況，Wtime表示等待時間：Tc-lo表示輕度擁堵，等待時間為w1，Tc-me表示中度擁堵，等待時間為w2，Tc-hi表示重度擁堵，等待時間為w3。為了計算方便，相同程度的擁擠假設(shè)等待時間相同，即

除此之外，還應(yīng)包括以下約束和假設(shè)：

1）所有客戶只能被一輛配送車輛僅且訪問一次，一輛配送車輛可訪問多個客戶；

2）所有配送車輛，從配送中心出發(fā)開始上班狀態(tài)，回到配送中心為下班狀態(tài)；

3）所有車輛必須嚴格遵守容量、載重量等規(guī)則條件；

4）同一配送中心的快遞車輛車型相同，容量相同；

5）配送中心唯一；

6）所有車輛及工作人員在法定工作時間內(nèi)工作，沒有加班時間。

本文求解問題描述如下：某一區(qū)域內(nèi)有且僅有一個快遞配送中心，z個客戶。該配送中心有m輛載重量為q的汽車，每個客戶的快遞的重量分別為 gi(i=1,2,…,L)，為方便，規(guī)定q＞gi。車輛到達客戶i的時間點為ti，在客戶i的服務(wù)時間為Δti，ti須在客戶i要求的服務(wù)時間窗[gi,hi]范圍內(nèi)。為方便建模，配送中心編號為0，客戶分別編號為1，2，3，…，l，配送車輛從客戶i到客戶 j的時間運輸成本用Cij表示。

利用上述符號可建立調(diào)度優(yōu)化問題的數(shù)學(xué)模型如下：

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

約束條件：

上述模型中，式（4）為模型的目標(biāo)函數(shù)，Etime為為滿足客戶要求時的懲罰時間成本。Q為運輸成本，包括兩部分，一是在每個客戶點需要的服務(wù)時間；二是到達目標(biāo)地點的路程消耗時間成本。函數(shù)要求在滿足客戶要求的服務(wù)時間窗范圍內(nèi)，方案所產(chǎn)生的時間運輸總成本最小；式（5）表示車輛k是否從點i行駛到點j；式（6）表示客戶i是否由車輛k來配送；式（7）表示從始至終有m輛配送車輛工作；式（8）表示每個客戶i有且僅有一輛配送車k對其配送；式（9）、（10）表示一輛快遞車只能服務(wù)一個服務(wù)；式（11）、（12）表示車輛 k載重量以及容積約束；式（13）表示快遞車輛及工作人員的工作時間約束。

3 VRP遺傳算法

3.1 編碼

針對物流配送車輛調(diào)度問題求解而言，遺傳算法主要針對快遞車輛所服務(wù)的客戶群問題，所以采用簡單直觀的序列編碼方法［8］。問題描述如下：某一城市區(qū)域內(nèi)有z（z＞0）個客戶，配送中心有m輛車，分別編號為1,2,…,m，任一客戶接受任一快遞車的服務(wù)概率是相等的，據(jù)此設(shè)計序列編碼，每一位為1,2,…,m中的某個自然數(shù)，長度為z位。每一種編碼對應(yīng)于一種客戶分群方案。

3.2 初始染色體種群的生成

群體規(guī)模 N，建議范圍是：N=20～100［9］。隨機產(chǎn)生符合所述編碼標(biāo)間的染色體，并考察約束文獻［9］和［10］，剔除不滿足約束條件的染色體，直到染色體種群的數(shù)目達到規(guī)模N，生成初始染色體種群。本文約定規(guī)模n=100，即產(chǎn)生100個初始種群。

3.3 適應(yīng)度函數(shù)

遺傳算法的根本原則是適者生存。根據(jù)適應(yīng)度函數(shù)衡量個體而分別得到的適應(yīng)值，就決定了個體是繼續(xù)留在此環(huán)境下還是被淘汰。本文中，時間作為影響快遞車輛路徑選擇的首要因素，因此時間也是適應(yīng)度函數(shù)中最為主要的衡量指標(biāo)。每個快遞車輛能否在上班時間內(nèi)，合理安排時間，從而送完全部的快遞服務(wù)，是首要考慮的因素。所以建立如下所示的適應(yīng)函數(shù) f(x)和目標(biāo)函數(shù)g(x)的映射關(guān)系：

適應(yīng)值函數(shù)：

上式中，g表示總時間成本，w1表示時間成本，未滿足客戶時間窗要求時懲罰造成；w2表示程消耗時間成本，即車輛到達目的地路程消耗；w3表示時間成本，即配送車輛在客戶點的時間消耗。Cmax表示一個可以輸入值或是理論上的最大值。

3.4 遺傳算子

復(fù)制、雜交和變異是遺傳算子的操作算子的三種基本形式，這三種形式構(gòu)成了遺傳算法強大搜索能力的核心，是模擬自然選擇以及遺傳過程中發(fā)生的繁殖、雜交和變異現(xiàn)象的主要載體［10］。

復(fù)制，采用放回的聯(lián)賽選擇，因其選擇的概率比較容易控制。其基本思想是從當(dāng)前群體中隨機選擇一定數(shù)量的個體，比較個體的適應(yīng)值，選擇較大適應(yīng)值的個體保存到下一代。反復(fù)執(zhí)行該選擇過程，直至其個體數(shù)量達到既定的群體規(guī)模。根據(jù)大量科研研究，聯(lián)賽規(guī)模q=2。

雜交，采用均勻雜交方法，即位于染色體位串上的每一位基因以相同概率進行隨機均勻雜交［11］。

變異，通過變異基因的二進制字符實現(xiàn)變異操作。在實際應(yīng)用中，因為變異概率比較小，可能部分個體從始至終都不會發(fā)生一次變異。在眾多實驗的基礎(chǔ)之上，變異概率一般取值為：Pm=0.005～0.01，本文 Pm=0.0095［12］。

3.5 算法停止選擇的標(biāo)準(zhǔn)

理論研究中，遺傳算法有多種算法可結(jié)束循環(huán)終止，但應(yīng)用中發(fā)現(xiàn)很多方法的實現(xiàn)相當(dāng)困難，因此在求解過程當(dāng)中，追求能夠快遞搜索到具有一定質(zhì)量的滿意解。本文采用設(shè)定達到最大遺傳迭代步數(shù)200步時，循環(huán)終止。該方法簡單易行，實用性較高。

3.6 算法流程

基于混合遺傳算法的VRP問題算法流程圖3所示。

Step 1：隨機產(chǎn)生100個可行編碼序列作為初始種群，另將控制變量k賦值為1，轉(zhuǎn)向Step2；

Step 2：利用評價函數(shù)評價第k代種群，得到截至目前為止的最優(yōu)解及其最優(yōu)解的適應(yīng)值，轉(zhuǎn)向Step3；

Step 3：判斷控制變量k是否不大于200，若是，轉(zhuǎn)向Step4，否則轉(zhuǎn)向Step6；

Step 4：依據(jù)本文的聯(lián)賽選擇，從父代中選擇獲取最優(yōu)種群，轉(zhuǎn)向Step5；

Step 5：對Step4選擇的種群進行算法當(dāng)中的關(guān)鍵步驟——交叉操作，轉(zhuǎn)向Step6；

Step 6：對Step5得到的種群進行變異操作，得到子代種群，轉(zhuǎn)向Step2；

Step 7：獲取最優(yōu)解方案，得到結(jié)果。

圖3 算法流程圖

4 應(yīng)用實例分析

4.1 問題描述

某區(qū)域的快遞配送中心有4輛相同型號相同容量的快遞配送車，每輛車的載重量為2噸?，F(xiàn)向某城市9個地區(qū)的60個客戶配送快遞物件，各個客戶的需求量、客戶要求的服務(wù)時間窗如表1所示，各個客戶點之間的距離如表2所示，這個地區(qū)的道路交通狀況如圖4所示。為了計算方便，統(tǒng)一設(shè)定在不同十字路口，堵車情況所造成的快遞車輛等待時間，如遭遇輕度堵車時，等待時間為10min；中度堵車時，等待時間為20min；重度堵車時，等待時間為30min?？爝f車輛的行駛速度為80km/h，快遞車輛在早上7：00統(tǒng)一從配送中心出發(fā)，下午18：00下班之前都要回到配送中心。在每個客戶地點，在客戶地點送達快件加上等待時候總共消耗10min。無論提前到達或者推后到達，造成多長的等待時間，成本都是20元。到達同一地區(qū)不同客戶點耗時10min。城市上午擁堵高峰期為7：00～9：00，下午為17：00～18：00。當(dāng)?shù)竭_一個客戶地點有多種選擇路徑時，選擇成本最低、時間最短的路徑。

表1 客戶需求情況表

續(xù)表1

圖4 某地區(qū)的道路交通狀況圖

4.2 調(diào)度方案

本文建立基于時間的硬時間窗物流調(diào)度模型，得到以下車輛調(diào)度路徑：

車輛1路徑：6：00從物流中心出發(fā)，19：45回到物流中心。

B-＞45-＞47-＞2-＞5-＞7-＞26-＞27-＞30-＞31-＞34-＞37-＞38-＞35-＞33-＞28-＞32-＞B

車輛2路徑：7：00從物流中心出發(fā)，16：25回到物流中心。

B-＞52-＞54-＞53-＞50-＞19-＞22-＞20-＞1-＞3-＞4-＞6-＞46-＞48-＞49-＞B

車輛3路徑：7：00從物流中心出發(fā)，18：30回到物流中心。

B-＞56-＞60-＞57-＞12-＞9-＞17-＞15-＞10-＞14-＞8-＞11-＞13-＞16-＞44-＞40-＞42-＞B

表2 各個地區(qū)之間的距離和道路情況表（單位：km）

車輛4路徑：5：00從物流中心出發(fā)，19：55回到物流中心。

B-＞25-＞29-＞36-＞39-＞41-＞43-＞51-＞55-＞59-＞58-＞18-＞21-＞23-＞24-＞B

4.3 結(jié)果分析

本文采用C語言實現(xiàn)編程。為了便于分析比較，模擬程序是在相同的硬件環(huán)境下進行。

表3 實例的混合遺傳算法計算結(jié)果

從表3可以看出，用混合遺傳算法對實例模型求解，10次都得到了較高質(zhì)量的解，其配送總時間的平均值為47.41h，平均計算時間為2.32s，求解效率較高。

為了便于比較，運用量子蟻群算法［3］、改進的遺傳算法［8］求解該模型算法，在迭代次數(shù)都是200次的情況下，計算結(jié)果如表4所示。

表4 實例的遺傳算法、混合遺傳算法計算結(jié)果的比較

從表4可以看出，混合遺傳算法的效率、尋優(yōu)結(jié)構(gòu)高于量子蟻群算法［3］、改進的遺傳算法［8］。

5 結(jié)語

本文優(yōu)化了帶時間窗的VSP模型，突出強調(diào)了時間概念。面對大規(guī)模數(shù)據(jù)，運用求解大系統(tǒng)優(yōu)化問題時采用的分解協(xié)調(diào)思想，將模型描述問題轉(zhuǎn)化成多個獨立的優(yōu)化問題，逐一解決。采用基于序列編碼的遺傳算法，構(gòu)造出混合遺傳算法求解模型問題，通過實驗數(shù)據(jù)的對比分析得知，該算法具有良好的性能，是求解帶時間窗VSP問題的一種可行算法，能夠快速得到具有參考價值的車輛路徑調(diào)度方案。下一步研究將優(yōu)化數(shù)學(xué)模型，綜合考慮建模時的非滿載、超載等各種約束條件。

［1］盧帥.聯(lián)邦快遞中國有限公司國內(nèi)業(yè)務(wù)發(fā)展戰(zhàn)略研究［D］.長沙：湖南大學(xué)，2014：12-16.

LU Shuai.FedEx（China）domestic business development strategy research［D］.Changsha：Hunan University，2014：12-16.

［2］Ioannou G，Prastacos G.A greedy look-ahead heuristic for the vehicle routing problem with time windows［J］.Journal of the Operational Research Society，2001，52（5）：523-537.

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

HE Xiaofeng，MA Liang.Quantum-inspired ant colony algorithm for vehicle routing problem with time windows［J］.Systems Engineering-Theory&Practice，2013，33（5）：1255-1261.

［4］郭建紅.帶時間窗的卷煙物流配送動態(tài)車輛路徑優(yōu)化方法研究［D］.北京：北京交通大學(xué)，2013.

GUOJianhong.Research on Dynamic Vehicle Routing Optimization of Cigarette Logistics based on Time-window［D］.Beijing：Beijing Jiaotong University，2013.

［5］孟祥虎，胡蓉，錢斌.求解帶時間窗車輛路徑問題的有效混合PBIL算法［J］.系統(tǒng)工程理論與實踐，2014，34（10）：2701-2709.

MENG Xianghu，HU Rong，QIAN Bin.Effective hybrid population-based incremental learning algorithm for vehicle routing problem with time windows［J］.System Engineering-Theory&Practice，2014，34（10）：2701-2709.

［6］曾羽琚，陳明輝.基于改進遺傳算法的車輛調(diào)度模型［J］.計算機工程與應(yīng)用，2015，51（6）：240-243.

ZENG Yuju，CHEN Minghui.Vehicle scheduling module based on improced Genetic Algorithm［J］.Computer Engineering and Applications，2015，51（6）：240-243.

［7］廖良才，王棟，周峰.基于混合遺傳算法的物流配送車輛調(diào)度優(yōu)化問題求解方法［J］.系統(tǒng)工程，2008，26（8）：27-31.

LIAO Liangcai，WANG Dong，ZHOU Feng.Solving Method of the Optimization Problem of Logistic Distribution Vehicle Scheduling Based on Hybrid Genetic Algorithm［J］.Systems Engineering，2008，26（8）：27-31.

［8］甘寶，薛玉璽，魏文萍.基于改進遺傳算法的車輛路徑問題［J］.交通運輸研究，2015，1（4）：88-94.GAN Bao，XUN Yuxi，WEI Wenping.An Improved Genetic Algorithm for Vehicle Routing Problem［J］.Transport Research，2015，1（4）：88-94.

［9］潘立軍.帶時間窗車輛路徑問題及其算法研究［D］.長沙：中南大學(xué)，2012.

PAN Lijun.Vehicle Routing Problem with Time Windows and Its Algorithms［D］.Changsha：Central South University，2012.

［10］孫秀娟.基于改進算子的遺傳算法［J］.電子制作，2014（2）：32-32.

SUN Xiujuan.Genetic Algorithm Based on Improved Operator［J］.Experimental Research，2014（2）：32-32.

［11］李冠楠，李家春.基于雜交遺傳算法的多處理器硬實時容錯調(diào)度算法［J］.計算機應(yīng)用研究，2016，33（9）：2606-2610.

LIGuannan，LIJiachun.Genetic algorithm based on multiprocessor hard real-time fault tolerant schedule［J］.Application Research of Computers，2016，33（9） ：2606-2610.

［12］沈暢，樂天.遺傳算法中的變異算子的述評［J］.科技視界，2012（23）：107-108.

SHEN Chang，LE Tian.A Review of Variation Operators in Genetic Algorithms［J］.Science&Technology Vision，2012（23）：107-108.