一種基于云計(jì)算環(huán)境的動態(tài)車輛路徑問題解決策略

寧 濤 陳 榮 郭 晨 馮瑞芳

1. 大連交通大學(xué)，軟件學(xué)院，大連 116045

2. 大連海事大學(xué)，信息科學(xué)技術(shù)學(xué)院，大連 116026

0 引 言

車輛路徑問題（Vehicle routing problem, VRP）[1]是運(yùn)籌學(xué)領(lǐng)域的經(jīng)典優(yōu)化組合問題，它由Dantzig和Ramser于1959年提出，其解決思路是通過構(gòu)造適當(dāng)?shù)能囕v行駛路線來實(shí)現(xiàn)運(yùn)輸成本的最小化。VRP的研究歷經(jīng)50多年已被證明是典型的NP-Hard問題，具有較強(qiáng)的實(shí)際應(yīng)用意義，并衍生出眾多路徑模型。動態(tài)車輛路徑問題（Dynamic vehicle routing problem,DVRP）[2]于1988年被Psaraftis首次提出，之后的學(xué)者在信息更新、需求迫切程度等方面對DVRP開展了研究。Pureza對有時間窗的DVRP進(jìn)行了研究，研究否定了按照新增加需求的順序?qū)囕v進(jìn)行調(diào)度，提出了基于適當(dāng)數(shù)量緩沖區(qū)的解決方案[3]。Mitrovic-Minic對快遞公司郵件車輛等待時間進(jìn)行了研究，并提出了基于實(shí)際數(shù)據(jù)的四種動態(tài)等待策略[4]。Haghani在分析了車輛配送過程需求動態(tài)變化的特點(diǎn)，提出了用遺傳算法求解DVRP，并得出了實(shí)時交通信息與 DVRP動態(tài)變化成正比的關(guān)系[5]。Lchoua則分析了DVRP過程中出現(xiàn)動態(tài)事件的概率，在此基礎(chǔ)上用模糊預(yù)定點(diǎn)生成動態(tài)調(diào)度方案[6]。Hanshar以報(bào)品配送為背景，用遺傳算法求解DVRP并指出采用2-Exchange改進(jìn)方法可以迅速求解問題[7]。Fattahi分析了選定的在線算法求解DVRP的競爭比率，提出了一種自適應(yīng)局部粒子搜索策略可以將企業(yè)利益最大化，同時提出了對潛在客戶的挖掘算法[8]。

基于上述研究方法，本文提出了基于云計(jì)算環(huán)境的改進(jìn)遺傳算法求解DVRP。文中首先建立面向不同約束條件的DVRP數(shù)學(xué)模型；針對動態(tài)調(diào)度的特點(diǎn)，提出雙鏈遺傳算法進(jìn)行車輛分配鏈和路徑優(yōu)化鏈的編碼方法；在云計(jì)算理論基礎(chǔ)上，設(shè)計(jì)云交叉算子和云變異算子來改進(jìn)遺傳算法的交叉和變異操作，進(jìn)而提出云計(jì)算環(huán)境下的自適應(yīng)遺傳算法（Cloud-based adaptive genetic algorithm, CAGA）求解DVRP調(diào)度問題，最后通過仿真實(shí)驗(yàn)和實(shí)例驗(yàn)證算法的有效性。

1 DVRP調(diào)度模型

1.1 問題描述

實(shí)際生活中，車輛路徑問題存在大量的不確定性，客戶需求、運(yùn)輸需求、路徑制定者的主觀認(rèn)識、交通路況及車況等變化都需要調(diào)度管理員借助調(diào)度系統(tǒng)在短時間內(nèi)對更新的信息作出快速正確的響應(yīng)，并修改生成新的路徑規(guī)劃。具有動態(tài)需求的 DVRP可描述如下：某運(yùn)輸網(wǎng)絡(luò)系統(tǒng)中存在 1個車場和 m個待服務(wù)的節(jié)點(diǎn)(客戶點(diǎn))，表示為0，1，2，…，m，車輛從車場出發(fā)并對一定數(shù)量的客戶提供配送服務(wù)后返回車場。根據(jù)需求的不同可將客戶分為確定性客戶和不確定性客戶。當(dāng)客戶需求不變時，運(yùn)輸網(wǎng)絡(luò)是靜態(tài)車輛路徑問題（Static vehicle routing problem,SVRP）；當(dāng)客戶的需求發(fā)生改變時，調(diào)度系統(tǒng)修改已制定的路徑計(jì)劃，此時的運(yùn)輸網(wǎng)絡(luò)是DVRP。已知每輛車的運(yùn)輸能力為C，每個節(jié)點(diǎn)需求量為模糊數(shù)D，節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的距離為cij，求解滿足運(yùn)輸需求費(fèi)用最小的車輛行駛路線的目標(biāo)是最小化運(yùn)輸車隊(duì)數(shù)量以及最小化運(yùn)輸行駛距離。本文研究的 DVRP包括擁有一隊(duì)同型號車輛的配送中心（配送車場）和待服務(wù)的客戶集合，每個客戶僅允許由一輛車配送服務(wù)一次。模型建立的符號表示為：配送車場編號為0；客戶編號為 1，2，…，N；配送中心車輛編號為 1，2，…，K；i，j表示配送車場點(diǎn)以及客戶點(diǎn)（i, j∈ { 1、2、…、N}）；車輛的最大載重量為Q；車輛k從客戶點(diǎn)i出發(fā)的累積載量為qik，且qik

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

動態(tài)實(shí)時需求發(fā)生前，車輛已經(jīng)對部分客戶進(jìn)行了配送服務(wù)。在車載量允許的情況下，將新的客戶需求加入到已有路徑中，若該需求無法導(dǎo)入已有路徑，則需要增加新的車輛。如果原客戶需求量增加，且超出最大車載量，則選擇此子路徑上最后配送服務(wù)的客戶點(diǎn)作為新客戶處理，直至滿足車載量的限制。如果把該客戶點(diǎn)看作配送車場，則原來的單配送路徑問題就變換為多配送路徑問題。假設(shè) W為靜態(tài)階段尚未服務(wù)的客戶需求與動態(tài)階段新增加客戶需求的總量；M 表示作為新配送車場的客戶點(diǎn)數(shù)量，其編號為N+1、N+2、…、N+M，則原來的車場編號變?yōu)镹+M+1，L表示新增加的車輛數(shù)。靜態(tài)階段從車場出發(fā)的車輛處在第i個客戶位置，其編號為W+i；靜態(tài)階段車輛的剩余車載量為Q-qik。

定義決策變量：

建立 t時刻動態(tài)實(shí)時需求路徑問題的數(shù)學(xué)模型如下：

式（1）表示目標(biāo)函數(shù)，包括靜態(tài)階段未完成配送和動態(tài)階段新增加用戶的運(yùn)輸成本、動態(tài)階段新增加車輛的運(yùn)輸成本以及動態(tài)階段新派出車輛的發(fā)車成本。

式（2）表示每個客戶都必須被配送服務(wù)的約束條件。

式（3）和式（4）表示每個客戶只能被一輛車配送服務(wù)。

式（5）表示每臺從車場出發(fā)的車輛都是滿載狀態(tài)。

式（6）表示車輛給任何客戶配送服務(wù)前不能使空載狀態(tài)。

2 基于云計(jì)算理論的自適應(yīng)遺傳算法

2.1 雙鏈遺傳算法編碼

本文在概率幅編碼的基礎(chǔ)上引入新的補(bǔ)償因子γ（1γ≥），假設(shè)pi表示一條量子染色體，則第i個染色體編碼方案如下：

式中，α、β滿足α+β2=1；a=2π×δ，δ表示（0，

ij 1）間的隨機(jī)數(shù)， i = 1 ,2,… ,n ;j = 1 ,2,… ,m ; n表示種群規(guī)模，m表示量子位個數(shù)。補(bǔ)償因子γ使周期由2π擴(kuò)展為多周期以提高算法的收斂概率。每條染色體包含兩個并列的基因鏈，每個基因鏈對應(yīng)一個優(yōu)化解，則每條染色體對應(yīng)搜索空間的兩個最優(yōu)解，表示DVRP問題的車輛分配鏈和貨物配送鏈，即：

式中，picos和pisin分別叫做余弦解和正弦解，當(dāng)染色體進(jìn)行迭代時，兩個解可同步更新以擴(kuò)大搜索空間，增加最優(yōu)解數(shù)目。

2.2 云交叉算子

在種群的進(jìn)化過程中，假設(shè)兩個父代個體的適應(yīng)度分別表示為f1和f2，父代種群的最大適應(yīng)度表示為Fmax，最小適應(yīng)度表示為Fmin，則存在實(shí)數(shù)pcr滿足：

式中，pc為云交叉算子；t1、t2和均為常數(shù)；=(f1+f2)2；y是關(guān)于Fmax和Fmin的一個正態(tài)隨機(jī)數(shù)。

因?yàn)樵平徊嫠阕油瑫r具有適應(yīng)性和隨機(jī)性的特點(diǎn)，所以，本文設(shè)計(jì)云交叉算子優(yōu)化一般遺傳算法的交叉操作，交叉算子的產(chǎn)生始終是以父代個體的平均適應(yīng)度為基準(zhǔn)而變化，但又隨正態(tài)隨機(jī)數(shù)y的變化而變化。云交叉算子的算法如下：

步驟 1：計(jì)算父代個體適應(yīng)度的均值 Ex，記為

步驟2：以En為期望值，以He為標(biāo)準(zhǔn)差生成一個正態(tài)隨機(jī)數(shù) En′，其中 En=m1(Fmax-Fmin)，He=n1En，m1和n1表示控制系數(shù)。

步驟 3：根據(jù)式（8）計(jì)算得到云交叉算子

適應(yīng)度的平均值，f = max(f1, f2)。

2.3 云變異算子

在種群進(jìn)化過程中，假設(shè)單個父代個體的適應(yīng)度表示為f1，則存在實(shí)數(shù)pmt滿足：

式中，pm為云變異算子。式(9)中 s1、s2和F均為常數(shù)，F(xiàn)max、Fmin和y的概念同式(8)。

云變異算子的穩(wěn)定傾向性由f1、Fmax和Fmin三個參數(shù)所決定，本文設(shè)計(jì)云變異算子優(yōu)化一般遺傳算法的變異操作，云變異算子的算法如下：

步驟1：設(shè)單個父代個體適應(yīng)度的均值Ex，記為

步驟2：以En為期望值，以He為標(biāo)準(zhǔn)差生成一個正態(tài)隨機(jī)數(shù) En′；其中 En=m2(Fmax-Fmin)，He=n2En，m2和n2表示控制系數(shù)。

本文設(shè)計(jì)的基于云模型理論自適應(yīng)遺傳算法的關(guān)鍵是用云交叉算作、云變異算子和云發(fā)生器對遺傳算法的交叉和變異算子進(jìn)行改進(jìn)以提高算法的收斂速度和改善解搜索的效果。

云自適應(yīng)交叉概率和云自適應(yīng)變異概率如圖 1所示：

圖1 云自適應(yīng)交叉概率pc和變異概率pmFig.1 Cloud adaptive crossover probability pc and mutation probability pm

2.4 云自適應(yīng)遺傳算法設(shè)計(jì)

云自適應(yīng)遺傳算法的步驟為：

步驟1：隨機(jī)產(chǎn)生n個個體組成初始種群，進(jìn)行雙鏈量子編碼，并初始化pc和pm；

步驟 2：設(shè)計(jì)表達(dá)式為f′(x) = 1 /Z(x)的適應(yīng)度評價函數(shù)，Z(x)表示個體目標(biāo)函數(shù)值，函數(shù)值越小個體越優(yōu)秀；

步驟3：利用最佳個體保留策略和適應(yīng)度比例選擇進(jìn)行種群個體選擇，以確定進(jìn)入下一代種群個體的范圍；

步驟 4：根據(jù)式（8）利用云發(fā)生器生成交叉算子pc，并對父代個體進(jìn)行交叉操作；

步驟 5：根據(jù)式（9）利用云發(fā)生器生成變異算子pm，并對個體進(jìn)行互換變異操作；

步驟6：通過選取父代種群的m個優(yōu)秀個體和子代種群的相應(yīng)個體組合后重新構(gòu)建新種群，從而擴(kuò)大種群規(guī)模并增加搜索空間；

步驟7：判斷是否滿足停止條件，若沒滿足跳至步驟3；否則停止算法運(yùn)行。

3 數(shù)據(jù)分析與驗(yàn)證

為了對本文提出方法的有效性進(jìn)行驗(yàn)證，設(shè)計(jì)了包括 1個車場、6個動態(tài)需求（新增）客戶點(diǎn)和 12個靜態(tài)需求客戶點(diǎn)的模型。設(shè)車輛行駛區(qū)域?yàn)?0×60（單位：km）的近似正方形。靜態(tài)客戶編號為1，2，3，…，12，新增客戶編號為 a、b、c、d、e、f。約定每個客戶點(diǎn)的配送最大量不超過2 m3，配送車輛的最大載貨量都是16 m3，車輛連續(xù)行駛的最長距離為300 km，同時設(shè)配送車場坐標(biāo)為(25 km，25 km)，動態(tài)和靜態(tài)客戶點(diǎn)信息如表1所示，其中動態(tài)需求出現(xiàn)于“時刻1”。

表1 客戶信息Tab.1 Information of customers

初始配?送車輛數(shù)m示第i個客戶點(diǎn)的需求量；Q表示車輛最大載貨量；α表示貨物裝廂的復(fù)雜度，取值為 0.6；m取值為整數(shù)。在初始時刻車輛對12個靜態(tài)客戶點(diǎn)進(jìn)行配送服務(wù)，調(diào)度方案如圖2所示, 圖中0表示出發(fā)車場,車輛1配送客戶點(diǎn)為 1-2-3-4-5,車輛 2配送客戶點(diǎn)為6-7-8-9- 10-11-12；而當(dāng)時刻1新增客戶需求點(diǎn)a、b、c、d、e和f后，利用本文提出的調(diào)度策略進(jìn)行重調(diào)度。按照初始調(diào)度計(jì)劃派出的2臺車分別位于客戶點(diǎn)4和9，即動態(tài)因子關(guān)鍵點(diǎn)集合為｛4，9｝，此時車輛從這兩個關(guān)鍵點(diǎn)出發(fā)的載貨量集合為｛5.8，5.4｝，利用CAGA對問題進(jìn)行求解，生成時刻1的重調(diào)度方案如圖3所示。在時刻1配送車輛的路徑和載貨率情況如表2所示。

重調(diào)度計(jì)劃表中的載貨率等數(shù)據(jù)表明本文提出的基于云計(jì)算環(huán)境的CAGA及其調(diào)度策略是有效的。為進(jìn)一步驗(yàn)證所提出方法的性能，將 CAGA與已經(jīng)存在的 AIA[9]、CQPSO[10]、PSO+TS[11]和 MADSA[12]算法應(yīng)用于同一問題的求解。由圖 4可知,本文提出的CAGA和AIA算法在執(zhí)行100次運(yùn)算獲得的目標(biāo)值最小，即算法穩(wěn)定性最高, 同時使用CAGA算法求解DVRP問題時，可以最小化總配送距離、節(jié)省配送時間，能夠使載貨率最大化。

圖2 初始調(diào)度方案Fig.2 Initial scheduling

圖4 不同算法的穩(wěn)定性目標(biāo)值比較Fig.4 Objective comparison among different algorithms

圖3 時刻1重調(diào)度方案Fig.3 Rescheduling at moment 1

4 結(jié)束語

表2 時刻1重調(diào)度計(jì)劃Tab.2 Rescheduling at moment 1

本文面向不同約束條件，建立了多目標(biāo) DVRP數(shù)學(xué)模型，提出了基于雙鏈量子進(jìn)行編碼的方法；設(shè)計(jì)云交叉算子和云變異算子對一般遺傳算法的交叉和變異操作進(jìn)行改進(jìn)；進(jìn)而提出了基于云計(jì)算理論的自適應(yīng)遺傳算法求解DVRP問題。為驗(yàn)證算法的有效性，將上述算法應(yīng)用仿真算例，結(jié)果表明：與其他優(yōu)化算法相比，本文算法在求解多目標(biāo)調(diào)度問題時具有收斂速度快、求解質(zhì)量高的優(yōu)點(diǎn)。在本文研究結(jié)果的基礎(chǔ)上，進(jìn)一步的研究應(yīng)著重于考慮基于云計(jì)算的車輛調(diào)度過程中對配送時間點(diǎn)增加提前和拖后懲罰系數(shù)。

[1] Dantzig G. and Ramser J. The truck dispatching problem[J]. Management Science, 1959, (6): 80-9 1.[2] Psaraftis H. N. Dynamic vehicle routing problem[M].In: Golden B L, Assad A A, eds. Vehicle routing:methods and studies. Amstersam, North-Holland:Elsevier Science Ltd, 1988: 223-248.

[3] Pureza V., Laporte G. Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows[J]. Infor: Information System and Operational Research, 2008, 46(3): 165-175.

[4] Mitrovic-Mini S., Laporte G. Waiting strategies for the dynamic pickup and delivery problem with time windows [J]. Transportation Research Part-B-Method Logical, 2004, 38(7): 635-655.

[5] Haghani A., Jung S. A dynamic vehicle routing problem with time-dependent travel times [J].Computers & Operations Research, 2005, 32(11):2959-2986.

[6] Choua S., Gendreau M., Potvin J. Y. Exploiting knowledge about future demands for real-time vehicle dispatching [J]. Transportation Science, 2006,40(2): 211-225.

[7] Hanshar F. T., Ombuki-Berman B. M. Dynamic vehicle routing using genetic algorithms[J]. Applied Intelligence, 2007, 27(1): 89-99.

[8] Fattahi P., Fallahi A. Dynamic scheduling in flexible job shop systems by considering simultaneously efficiency and stability [J]. CIRP Journal of Manufacturing Science and Technology, 2010, 2(2):114-123.

[9] Bagheri A., Zandith M., Mahdavi I., Yanzdanni M.An artificial immune algorithm for the flexible jobshop scheduling problem[J]. Fut Gen Comp Sys,2010, 26(4): 533-541.

[10] 湯健超. 基于混合進(jìn)化算法的若干調(diào)度問題研究[D]. 廣州：華南理工大學(xué), 2012.

[11] 寧 濤. 混合量子算法在車輛路徑問題中應(yīng)用的研究[D]. 大連：大連海事大學(xué), 2013.

[12] Seyed Habib A., Rahmat M., Zandieh M. Yazdani.Developing two multi-objective evolutionary algorithms for the multi-objective flexible job shop scheduling problem [J]. The International Journal of Advanced Manufacturing Technology, 2013, 64(5):915-932.