考慮時(shí)間窗口的電動出租車路徑規(guī)劃研究

賈永基+郭文娟+鄭瑤

摘 要：首先分析了電動出租車路徑規(guī)劃問題與傳統(tǒng)燃油車路徑規(guī)劃問題的不同，根據(jù)電動汽車的特性以及出租車運(yùn)營模式的特點(diǎn)，建立了考慮時(shí)間窗口的電動出租車路徑規(guī)劃問題的混合整數(shù)規(guī)劃模型；然后采用遺傳算法求解該模型，仿真測試結(jié)果表明，遺傳算法是求解此類問題的有效方法。

關(guān)鍵詞：電動出租車；時(shí)間窗口；車輛路徑問題；遺傳算法

Abstract： Firstly， the paper analyzes the difference between electric taxi routing problem and traditional fuel vehicle routing problem. Based on the characteristics of electric vehicles and taxi operating mode， a hybrid integer programming model of electric taxi routing problem with time windows is established. Then， the genetic algorithm is used to solve the model. The simulation results show that the genetic algorithm is an effective method to solve the problem.

Key words： electric taxi； time window； vehicle routing problem； genetic algorithm

引 言

隨著汽車工業(yè)的迅速發(fā)展，其在造福人類的同時(shí)也帶來了很大的弊端，燃油汽車造成的能源緊缺、環(huán)境污染、城市交通等問題日益嚴(yán)重。為了緩解能源危機(jī)和環(huán)境污染的壓力，在政府的大力支持下，很多出租車公司將電動汽車引入到出租車運(yùn)營中。然而，電動出租車?yán)m(xù)航里程短、充電時(shí)間長的缺點(diǎn)，影響了電動出租車的廣泛使用。考慮到電動出租車的規(guī)模效應(yīng)，出租車公司往往采用換電模式而不是充電模式。換電模式雖然初期投資巨大，但是換電時(shí)間相比充電時(shí)間要短得多，一方面有利于提高電動出租車的使用率，另一方面可以采用夜晚的低峰時(shí)段對電池進(jìn)行充電，從而延長電池壽命、降低電動出租車的使用成本。由于電動出租車路徑規(guī)劃問題需要考慮電動汽車的換電站位置和換電時(shí)間等因素，對傳統(tǒng)車輛路徑規(guī)劃理論有很大的沖擊[1]，不能直接將傳統(tǒng)車輛路徑規(guī)劃理論應(yīng)用到電動出租車路徑規(guī)劃中。為保證服務(wù)質(zhì)量，提高客戶滿意度，需要對電動出租車行駛路徑進(jìn)行有效規(guī)劃。

當(dāng)前，越來越多的國內(nèi)外學(xué)者開始研究電動汽車路徑規(guī)劃問題。文獻(xiàn)[2]有關(guān)電動汽車路徑規(guī)劃問題給出兩個(gè)模型——能源最優(yōu)化路徑模型及距離最優(yōu)化模型，分析了這兩個(gè)模型的優(yōu)缺點(diǎn)：能源最優(yōu)化模型考慮了電動汽車制動時(shí)可以將動能轉(zhuǎn)化為電能的特點(diǎn)，但該模型的數(shù)據(jù)較難收集，實(shí)際應(yīng)用范圍比較窄；距離最優(yōu)化模型簡化了電動汽車路徑規(guī)劃問題，并將該問題描述為帶時(shí)間窗口的，目標(biāo)函數(shù)為最小化旅途時(shí)間的裝卸貨問題。文獻(xiàn)[3]將電動汽車應(yīng)用在城市零擔(dān)物流中，將電動汽車路徑規(guī)劃問題簡化為帶能力約束與時(shí)間窗口約束的問題。文獻(xiàn)[4]研究了電動汽車在城市交通網(wǎng)絡(luò)中的應(yīng)用，構(gòu)建了總行駛距離最短的優(yōu)化模型，并采用遺傳算法求解此問題，仿真測試表明遺傳算法可以求解出該問題的最佳配置網(wǎng)絡(luò)。文獻(xiàn)[5]提出了采用電動汽車作為最后一英里的運(yùn)輸，考慮了電動汽車充電站位置以及客戶時(shí)間窗口，建立了電動汽車路徑規(guī)劃問題的混合整數(shù)規(guī)劃模型，提出了一種變領(lǐng)域搜索算法來解決此類問題。文獻(xiàn)[6]將準(zhǔn)時(shí)化生產(chǎn)的思想應(yīng)用到電動汽車城市物流配送中，并將電動汽車在城市物流的配送問題簡化為帶軟時(shí)間窗口的裝卸貨問題。文獻(xiàn)[7]研究了考慮電動汽車充電時(shí)間以及客戶時(shí)間窗口的電動汽車路徑規(guī)劃問題，建立了數(shù)學(xué)模型，并提出了一種基于變鄰域搜索和禁忌搜索相結(jié)合的混合啟發(fā)式算法。

電動出租車路徑規(guī)劃問題屬于非確定性多項(xiàng)式組合難題，很難用精確式算法進(jìn)行大規(guī)模求解，多采用啟發(fā)式算法求得滿意解。遺傳算法是一種借鑒生物界的進(jìn)化規(guī)律演化而來的隨機(jī)搜索方法，具有計(jì)算時(shí)間短、魯棒性好、精度高等優(yōu)點(diǎn)[8]，故本文采用遺傳算法來求解電動出租車路徑規(guī)劃問題。

1 電動出租車路徑規(guī)劃問題的混合整數(shù)規(guī)劃模型

1.1 問題描述與基本假設(shè)

電動出租車路徑規(guī)劃問題描述如下：當(dāng)客戶信息到達(dá)出租車調(diào)度中心后，調(diào)度中心進(jìn)行調(diào)度，安排出租車為這些客戶提供服務(wù)。每個(gè)客戶信息有一個(gè)上車點(diǎn)位置、一個(gè)下車點(diǎn)位置以及時(shí)間窗口要求。電動出租車從車庫出發(fā)，根據(jù)調(diào)度中心的安排，依次服務(wù)所分配的客戶。當(dāng)出租車在客戶指定的上車點(diǎn)拉上客戶之后，必須立即駛向該客戶指定的下車點(diǎn)，而不能駛向其它位置。出租車到達(dá)上車點(diǎn)的時(shí)間需滿足客戶所指定的時(shí)間窗口，若提前到達(dá)則需等待并承擔(dān)等待成本，若延遲到達(dá)則需承擔(dān)懲罰成本。當(dāng)服務(wù)完一個(gè)客戶之后，調(diào)度中心要求電動出租車進(jìn)行電池電量檢查，并把檢查結(jié)果反饋給調(diào)度中心。若該電動出租車服務(wù)完某個(gè)新客戶后，剩余電量能保證該車輛到達(dá)車庫進(jìn)行電池更換，則把該新客戶分配給該出租車；否則，出租車立即返回車庫進(jìn)行電池更換，然后繼續(xù)服務(wù)客戶。當(dāng)電動出租車完成一天的工作之后，返回車庫。

該問題的混合整數(shù)規(guī)劃模型的基本假設(shè)如下：

（1）出租車開始服務(wù)客戶時(shí)，電池都擁有最大電量；

（2）出租車到車庫進(jìn)行電池更換后，電池都擁有最大電量；

（3）電池耗電量與行駛距離成正比；

（4）電動出租車行駛速度恒定，不考慮交通擁堵等突發(fā)狀況；

（5）出租車服務(wù)不允許拼車；

（6）忽略客戶上下車時(shí)間。

1.2 決策變量與參數(shù)定義

假設(shè)o為車庫；G為客戶點(diǎn)集合，|G|為客戶數(shù)量；K為車輛集合，|K|為車輛個(gè)數(shù)；i、j、k表示節(jié)點(diǎn)；S為客戶點(diǎn)i的上車點(diǎn)位置，D為客戶點(diǎn)i的下車點(diǎn)位置；N為所有節(jié)點(diǎn)集合N=G∪o∪S∪D；d表示節(jié)點(diǎn)i到j(luò)的距離；E為電動出租車滿電狀態(tài)時(shí)的最大行駛里程，E為電動出租車到達(dá)節(jié)點(diǎn)j時(shí)剩余電量所能行駛的里程；E為電動出租車離開節(jié)點(diǎn)i時(shí)的剩余電量所能行駛的里程；e表示客戶點(diǎn)i的最早服務(wù)時(shí)刻；l表示客戶點(diǎn)i的最晚服務(wù)時(shí)刻；t表示車輛k到達(dá)客戶點(diǎn)i的時(shí)刻；ft為懲罰值函數(shù)；α為出租車行駛過程中的單位成本；β為更換電池的成本；p為出租車早到的單位時(shí)間懲罰值；q為出租車晚到的單位時(shí)間懲罰值；v表示電動出租車平均速度；X為0-1決策變量，當(dāng)車輛k從客戶點(diǎn)i到j(luò)時(shí)取值為1i≠j，否則為0；Y為0-1決策變量，當(dāng)車輛k到車庫o更換電池時(shí)取值為1，否則為0。

1.3 目標(biāo)函數(shù)與約束條件

電動出租車路徑規(guī)劃模型的目標(biāo)函數(shù)與約束條件如下：

其中：式（1）是目標(biāo)函數(shù)，最小化電動出租車總運(yùn)營成本，包括車輛行駛成本、電池更換成本和服務(wù)客戶的時(shí)間懲罰成本；式（2）表示從車庫出發(fā)的車輛數(shù)不超過|K|；式（3）表示車輛到達(dá)客戶的上車點(diǎn)后，下一節(jié)點(diǎn)必定是該客戶的下車點(diǎn)；式（4）表示車輛在離開車庫后其電池為滿電狀態(tài)；式（5）表示電動出租車的里程約束；式（6）表示服務(wù)完客戶后，電動出租車剩余電量所能行駛的里程要大于返回車庫的行駛里程；式（7）表示時(shí)間約束，當(dāng)X為1時(shí)，電動出租車抵達(dá)j的時(shí)間等于電動出租車到達(dá)i的時(shí)間加上從i行駛到j(luò)所花費(fèi)的時(shí)間；當(dāng)X為0時(shí)，不等式自然滿足；式（8）表示違反客戶時(shí)間窗口的懲罰成本。

2 基于遺傳算法的模型求解算法

遺傳算法是一種模擬自然界生物進(jìn)化過程的一種隨機(jī)搜索啟發(fā)式算法，它不一定能找到最優(yōu)解，卻可以不斷地尋找更優(yōu)的解。遺傳算法本身所具有的并行搜索能力、魯棒性強(qiáng)、實(shí)現(xiàn)簡單等諸多優(yōu)點(diǎn)，使其在求解大規(guī)模組合優(yōu)化問題時(shí)顯示出了優(yōu)越的性能。因此，本文使用遺傳算法來求解上文提出的電動出租車路徑規(guī)劃問題。典型的遺傳算法的基本流程如圖1所示。

2.1 染色體編碼與適應(yīng)度函數(shù)

本文采用序數(shù)編碼方式，即用序數(shù)1到n表示n個(gè)客戶，0表示車庫，則電動出租車路徑規(guī)劃問題的一個(gè)可行解可編碼成長度為n+m的染色體：

其中δ表示第k輛車服務(wù)的第i個(gè)客戶。這樣的染色體結(jié)構(gòu)可以理解為第k輛車從車庫0出發(fā)，經(jīng)過客戶δ，δ，…，δ后回到車庫0，形成1條子路徑，總共形成包括m條子路徑的完整路徑。

本文選取模型的目標(biāo)函數(shù)作為遺傳算法的適用度函數(shù)。

2.2 遺傳算子

（1）選擇算子

本文采用輪盤賭選擇方法進(jìn)行染色體的選擇。

（2）交叉算子

本文采用部分匹配交叉算子，首先從第一個(gè)父代染色體中隨機(jī)選一個(gè)基因段作為待交叉基因段，然后將該基因段復(fù)制到子代染色體的相應(yīng)位置，產(chǎn)生一個(gè)原始子代，接著刪除第二個(gè)父代染色體中原始子代中已有的客戶，得到原始子代所需要的其它客戶的順序，并按這個(gè)順序?qū)⒖蛻粢来味ㄎ坏皆甲哟目杖蔽恢蒙稀?/p>

（3）變異算子

本文使用的變異算子，將隨機(jī)選擇的變異基因不是插入到一個(gè)隨機(jī)產(chǎn)生的位置，而是將該基因插入到染色體的使得目標(biāo)函數(shù)增加值最小的最優(yōu)變異位置。

2.3 控制參數(shù)與停止條件

交叉算子與變異算子的作用效果受到交叉率和變異率的控制，要想得到遺傳算法的最優(yōu)性能，必須確定這些參數(shù)的最優(yōu)設(shè)置，然而這些參數(shù)的具體選取往往與所求解的問題相關(guān)，只能根據(jù)經(jīng)驗(yàn)或者實(shí)驗(yàn)來確定。

由于遺傳算法具有較大的隨機(jī)性，本文選擇迭代次數(shù)作為算法的終止條件。

3 測試與分析

3.1 測試實(shí)例

本文選用的實(shí)驗(yàn)數(shù)據(jù)來自Solomon設(shè)計(jì)的VRPTW標(biāo)準(zhǔn)測試題庫[9]，對測試實(shí)例做以下假設(shè)：僅有一個(gè)單一的車庫，而且車輛類型都是一樣的，每個(gè)客戶都指定一個(gè)時(shí)間窗口，客戶均勻分布于70×70的坐標(biāo)平面上，車庫位于坐標(biāo)平面的中心位置（35，35）。有20個(gè)位于不同地點(diǎn)的客戶，這些客戶點(diǎn)的最早服務(wù)時(shí)間、最晚服務(wù)時(shí)間以及目的地均不相同。每位客戶的上、下車點(diǎn)坐標(biāo)以及時(shí)間窗口的數(shù)據(jù)如表1所示，其分布情況如圖2所示，其中三角形表示車庫位置，實(shí)心圓點(diǎn)表示客戶上車點(diǎn)，菱形表示客戶下車點(diǎn)。

3.2 測試結(jié)果分析

利用matlab 2012b編寫遺傳算法程序，設(shè)置出租車提前到達(dá)客戶點(diǎn)的懲罰值p為0.5；延遲到達(dá)客戶點(diǎn)的懲罰值q為1.5；出租車行駛過程中產(chǎn)生的成本α為8；更換電池產(chǎn)生的成本β為20；出租車最大電量所對應(yīng)的最大行駛里程為60公里；交叉率為0.7，變異率為0.6，迭代次數(shù)為1 000，種群規(guī)模為500。

遺傳算法優(yōu)化結(jié)果與進(jìn)化代數(shù)的關(guān)系如圖3所示。從中可以看出，在迭代的初期，種群的適應(yīng)度比較低，曲線處于陡峭的狀態(tài)并且下降趨勢明顯；迭代達(dá)到500次以后，曲線下降趨勢明顯變慢，且波動非常不明顯；迭代次數(shù)達(dá)到620次的時(shí)候，曲線已經(jīng)幾乎不再波動，說明已進(jìn)化至最優(yōu)解，此時(shí)的最優(yōu)值為9 965.61，最優(yōu)解為電動出租車需求數(shù)量為3，其最優(yōu)行駛路線如表2所示。

4 結(jié) 論

本文主要針對城市當(dāng)中的電動出租車預(yù)約接送客戶的問題，進(jìn)行合理的路徑規(guī)劃與建模研究。在電動出租車行駛過程中，需要考慮行駛路徑是否最短，是否回車庫進(jìn)行電池更換，還需要考慮客戶的時(shí)間需求，盡可能的不違背客戶時(shí)間等因素。

本文首先建立了電動出租車路徑規(guī)劃問題的混合整數(shù)規(guī)劃模型，目標(biāo)函數(shù)為最小化出租車運(yùn)營總成本。然后，編寫了遺傳算法程序用于求解該問題，并設(shè)計(jì)了仿真測試的實(shí)例。測試結(jié)果表明，遺傳算法是求解此類電動出租車路徑規(guī)劃問題的有效算法。

參考文獻(xiàn)：

[1] 歐雯雯，葉瑞克，鮑健強(qiáng). 電動汽車的節(jié)能減碳價(jià)值研究[J]. 未來與發(fā)展，2012，2（5）：36-40.

[2] Touati-Moungla N， Jost V. Combinatorial optimization for electric vehicles management[J]. 能源與動力工程（英文版），2012（5）：738-743.

[3] Conrad RG， Figliozzi MA. The Recharging Vehicle Routing Problem[C] // Proceedings of the 2011 Industrial Engineering Research Conference， Reno， USA， 2011.

[4] Taniguchi E， Kawakatsu S， Tsuji H. New cooperative system using electric vans for urban freight transport[C] // International Conference on Urban Transport， Greenville， SC， USA， 2010.

[5] Schneider M， Stenger A， Goeke D. The Electric Vehicle Routing Problem with Time Windows and Recharging Stations[J]. Transportation Science， 2014，22（8）：1-22.

[6] Bhusiria N， Qureshia AG， Taniguchia E. Application of the Just-In-Time Concept in Urban Freight Transport[J]. Procedia-Social and Behavioral Sciences， 2014，125（3）：171-185.

[7] Eisner J， Funke S， Storandt S. Optimal route planning for electric vehicles in large networks[C] // The Twenty-Fifth AAAI Conference on Artificial Intelligence， Stuttgart， Germany， 2011.

[8] 馬洪坤，楊偉. 基于遺傳蟻群算法的帶時(shí)間窗多車場車輛調(diào)度問題[J]. 西華大學(xué)學(xué)報(bào)（自然科學(xué)版），2016，35（3）：31-35.

[9] 佚名. VRPTW Benchmark Problems[EB/OL]. （2005-03-24）[2016-11-25]. http：//w.cba.neu.edu/～msolomon/problems.htm.