考慮時間窗口的電動出租車路徑規劃研究

賈永基+郭文娟+鄭瑤

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

關鍵詞：電動出租車；時間窗口；車輛路徑問題；遺傳算法

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

引 言

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

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

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

1 電動出租車路徑規劃問題的混合整數規劃模型

1.1 問題描述與基本假設

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

該問題的混合整數規劃模型的基本假設如下：

（1）出租車開始服務客戶時，電池都擁有最大電量；

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

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

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

（5）出租車服務不允許拼車；

（6）忽略客戶上下車時間。

1.2 決策變量與參數定義

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

1.3 目標函數與約束條件

電動出租車路徑規劃模型的目標函數與約束條件如下：

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

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

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

2.1 染色體編碼與適應度函數

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

其中δ表示第k輛車服務的第i個客戶。這樣的染色體結構可以理解為第k輛車從車庫0出發，經過客戶δ，δ，…，δ后回到車庫0，形成1條子路徑，總共形成包括m條子路徑的完整路徑。

本文選取模型的目標函數作為遺傳算法的適用度函數。

2.2 遺傳算子

（1）選擇算子

本文采用輪盤賭選擇方法進行染色體的選擇。

（2）交叉算子

本文采用部分匹配交叉算子，首先從第一個父代染色體中隨機選一個基因段作為待交叉基因段，然后將該基因段復制到子代染色體的相應位置，產生一個原始子代，接著刪除第二個父代染色體中原始子代中已有的客戶，得到原始子代所需要的其它客戶的順序，并按這個順序將客戶依次定位到原始子代的空缺位置上。

（3）變異算子

本文使用的變異算子，將隨機選擇的變異基因不是插入到一個隨機產生的位置，而是將該基因插入到染色體的使得目標函數增加值最小的最優變異位置。

2.3 控制參數與停止條件

交叉算子與變異算子的作用效果受到交叉率和變異率的控制，要想得到遺傳算法的最優性能，必須確定這些參數的最優設置，然而這些參數的具體選取往往與所求解的問題相關，只能根據經驗或者實驗來確定。

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

3 測試與分析

3.1 測試實例

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

3.2 測試結果分析

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

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

4 結 論

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

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

參考文獻：

[1] 歐雯雯，葉瑞克，鮑健強. 電動汽車的節能減碳價值研究[J]. 未來與發展，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] 馬洪坤，楊偉. 基于遺傳蟻群算法的帶時間窗多車場車輛調度問題[J]. 西華大學學報（自然科學版），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.