基于時間窗約束的純電動汽車路徑規劃模型分析

劉穎鑫 （渤海大學 管理學院，遼寧 錦州 121000）

基于時間窗約束的純電動汽車路徑規劃模型分析

劉穎鑫 （渤海大學 管理學院，遼寧 錦州 121000）

隨著環境污染和資源的日益枯竭，發展低碳經濟是我國實現可持續發展的必然之路。物流配送行業作為我國能源消耗和溫室氣體的主要排放來源，備受人們關注。文章采用純電動汽車代替傳統車輛進行物流配送。通過對純電動汽車的優點和配送特征的分析，以及對車輛路徑問題的分類，提出純電動汽車路徑問題。最后，在考慮傳統車輛路徑規劃問題中的貨物裝載量、節點訪問以及時間等約束，結合電動汽車的電池容量、充電設施、充電時間等特點，構建具有時間窗的純電動汽車路徑規劃模型。

純電動汽車；時間窗約束；路徑規劃；物流配送

近年來，電子商務的快速發展極大促進了物流快遞行業的發展，使得多頻次、強時效性的物流配送需求日益增長。電動汽車具有節能環保、噪聲小、能源利用率高等優點，因此更加符合社會的發展需求。和傳統燃油車輛相比，電動汽車可以改善環境質量、減少對石油能源的消耗，從而實現節能減排的目的，因此引起了國內外的廣泛關注，許多物流公司已經開始建立“綠色物流”項目，來減少車輛配送過程中二氧化碳的排放量。采用純電動汽車進行物流的配送活動，有利于降低物流活動對生態環境的不良影響，同時也有利于實現社會利益和環境利益的統一。因此，伴隨著電動汽車的發展，將其應用在城市配送領域已經成為社會發展的趨勢。

1 純電動汽車路徑規劃問題研究現狀分析

1.1 純電動汽車的優點

純電動汽車是由可充電電池提供動力，且符合安全法規和道路交通各項要求的汽車[1]。突出的優勢在于它對環境的污染小，并減少對石油等不可再生資源的消耗。

（1）節能環保、污染小、噪聲小

傳統機動車輛的尾氣排放是大氣污染的主要原因之一，而電能是一種清潔能源，電動汽車以電代油，可以達到改善空氣質量的效果。純電動汽車使用電機驅動，電機工作時產生的噪音遠小于傳統的內燃機，從而降低了噪聲對居民的影響[2]。

（2）降低對石油資源的消耗

電動汽車電量的再次補充，可以通過多種形式獲得，例如風能、核能、太陽能等多種可再生能源，從而可以有效降低對化石能源的依賴，減少傳統汽車能源短缺之憂。

1.2 純電動汽車路徑問題的分類

純電動汽車路徑規劃問題與傳統車輛路徑規劃問題相似。傳統車輛路徑問題（Vehicle Routing Problem，VRP）的構成要素通常包括配送車輛、顧客節點、貨物需求、目標函數和約束條件等。而電動汽車路徑問題還包含充電服務設施、以及行駛里程和充電時間的約束，根據研究的側重點不同，EVRP可以分為不同的類型[3]。具體分類如下所示：

（1）配送車輛屬性。根據車輛的種類分為單車型和多車型車輛路徑問題；根據車輛的貨物裝載量分為滿載和非滿載車輛路徑問題；根據車輛的能力限制分為有容積限制和有載重限制的車輛路徑問題；按照車輛的類型分為傳統燃油機動車和新能源汽車以及混合車輛路徑問題。

（2）客戶屬性。根據客戶需求性質分為確定性需求和隨機需求車輛路徑問題；而根據客戶對配送時間的要求可分為有時間窗和無時間窗限制，有時間窗可以分為：軟時間窗和硬時間窗以及混合時間窗。軟時間窗表示若配送車輛沒有將貨物在顧客要求的時間窗范圍內送達，則將會受到相應的懲罰；而硬時間窗則要求配送車輛必須在客戶要求的時間窗范圍之內到達。

（3）需求屬性。根據需求是否可被拆分，可分為需求可拆分和需求不可拆分車輛路徑問題；根據需求服務的種類，分為純送貨車輛路徑問題，即車輛將貨物送到客戶點；純取貨車輛路徑問題，車輛對客戶點的貨物進行收集；以及同時取送貨的車輛路徑問題，表示為車輛在訪問顧客點時，不僅包含裝貨任務還包括卸貨任務。

（4）網絡屬性。根據網絡的不確定性劃分，可以分為靜態車輛路徑問題：在進行車輛路徑優化之前，所有與配送車輛相關的信息已經確定，并不會隨著時間變化而變化；動態車輛路徑問題，進行路徑優化之前，所有和車輛相關的信息并不是全部確定而且部分信息會隨著時間的變化而變化。

（5）目標函數。根據研究問題的不同，需要構建不同的約束條件和目標函數。從優化目標函數的個數可分為單目標和多目標車輛路徑問題，常構建的目標函數包括車輛的行駛距離最短、行駛時間最少、運輸車輛的成本最低以及客戶的滿意度最大化等。

1.3 純電動汽車路徑規劃模型約束條件描述

本文將假設一個網絡模型，即找到從給定原點到給定目的地的“最佳”路線，中途可能經過充電站進行電量的補充，但規定行駛里程不超過規定的范圍d。令網絡圖G=V,（）E ，V為客戶節點集合，E為弧集合。令節點s,t∈V代表電動汽車的起始點和終點。令dij表示每條弧i,j∈E的長度，讓F?V代表電動汽車充電站的集合。所以將電動汽車最短路徑問題定義為在網絡圖G中，規定電動汽車在行駛距離小于d的情況下，找到從節點s開始并在節點t結束的最短路線。如圖1所示，為求解原始車輛路徑問題從節點s開始到節點t的最短路線最短的行駛距離為39，途中有顏色的節點5、9、11和13分別代表充電服務設施。

圖1 VRP最短行駛路線

（1） 續航能力的約束

電動汽車由于受到自身電池技術的限制，因此行駛的距離相對于較短。目前，我國應用于物流行業配送的電動汽車的續駛里程在200公里左右，雖然可以滿足同城配送的需求，但是配送的半徑范圍遠小于傳統燃油車輛。如果圖1中的d=20，則電動車在行駛過程中為了能到達目的地，即完成配送任務，則車輛至少要到達充電站一次。在限制的范圍內，車輛可以到達節點5和節點9這兩個充電站進行充電。然后再選擇其中一個節點作為起始點，繼續完成配送任務。在行駛里程為d的約束下，從節點s開始可以到達所有節點的最短路徑如圖2所示，藍色方框代表從s開始所能到達節點的距離。

（2） 充電服務設施

傳統的VRP，訪問的頂點為服務的對象或者是配送中心，每兩個頂點之間恰好連接一次，行駛的過程中沒有回路，即為完整的圖。但EVRP訪問的頂點還包括可能經過的充電站。近幾年，我國極大地鼓勵電動汽車的發展，并且出臺了很多優惠政策，使其市場占有率逐年增加。但電動汽車充電服務設施還處于初期建設階段，充電服務不能滿足發展需要。傳統燃油汽車的加油站相對較多，配送車輛在行駛的過程中尋找加油站的耗費時間較小。因此，研究電動汽車配送路徑更加重要。電動汽車因為續航能力的約束，在行駛過程中當剩余的電量不足以繼續配送時，需要進入充電站進行電量的補充。由于目前充電站的布局并不完善，因此在配送路徑中，有的充電站可能不被訪問或者不止一次被訪問，導致配送距離大幅度的增加，從而增加物流的配送成本。如圖3所示為電動車在配送過程中可能的行駛路線。

圖2 行駛里程約束下可到達節點的最短路徑

圖3 電動汽車可能的行駛路線

因為在配送過程中增加了對充電站的訪問，可能會造成行駛線路的迂回，因此可以考慮電動車從起始點到達目的地經過加油站的最短行駛距離，此時把充電站看成訪問的坐標點。行駛的路線如圖4所示，圖中數值代表最短可行駛路徑的距離。此時該網絡圖中最短的行駛路徑為s-5（充電站） -13（充電站）-t，行駛距離為43。對應原網絡圖中電動車的行駛路線為s-1-4-5（充電站） -4-7-13（充電站） -14-t。與圖1中的最短行駛路段7-12-14相比，包括了迂回路線4-5-4和繞行路線7-13-14。具體如圖5所示。

圖4 配送車輛訪問加油站的最短行駛路線

圖5 電動汽車的最短行駛路線

對于以電動汽車為主的物流企業，電動汽車前去充電的行駛路程較長，所以在車輛路徑問題中要考慮充電服務設施的位置。因此對電動汽車充電服務設施進行合理的規劃，不僅能加快電動汽車的普及，降低溫室氣體的排放和改善環境質量，而且有利于電動汽車進行電量的補充。

（3） 充電方式

電動汽車的充電模式有三種：可以分為快速充電、慢速充電和機械充電[4]。快速充電模式也稱作應急充電，短時間內為電池提供大電流的充電服務，這種充電模式可以滿足顧客在短時間內的用電需求，充電時間大概在20分鐘左右。因為對電池進行大功率的充電，所以加速縮短了電池的使用壽命。但目前，我國在建設大型充電服務設施的時候，多采用此種充電方式。配送車輛在行駛的過程中可以采取快速充電方式，為了提高配送過程中顧客的滿意度，所以應該把行駛過程中的充電時間考慮在規劃模型中。

而慢速充電模式也稱為普通充電，該充電過程的電流較小，可在家中或停車場等地方對車輛進行充電。但充電的時間相對較長，一般在6到8小時之間，會給電動汽車用戶的出行帶來不便，有時會難以滿足電動汽車用戶緊急出行的需求。慢充適合用于每日行駛里程較短的用戶，對于電池續航里程較大的電動汽車而言，可以利用晚間停運的時候進行電量的補充，因此注重時效的物流配送車輛在行駛過程中不適合選用此種充電方式。

機械充電模式即更換電動汽車的電池組，該方式是在充電服務設施處由專業人員將快要耗盡電量的電池組取下，然后更換充滿電的電池組。更換電池組消耗的時間大約和傳統汽車加油的時間相同，一般為5到10分鐘，然后將換下的電池組送達到指定的地點完成充電。這種充電方式不僅可以有效減少對電池的損害，延長使用壽命，而且降低了電池的使用成本。

2 純電動汽車路徑規劃模型的構建

2.1 純電動汽車路徑問題概述

車輛路徑問題（Vehicle Routing Problem，VRP），其目的是盡量減少配送車輛訪問客戶的運輸成本。車輛從配送中心開始進行配送，每個客戶只被訪問一次，訪問全部的客戶后再返回到配送中心。目前，已經提出了VRP許多擴展形式，以符合現實世界的約束和條件。車輛路徑問題是由學者G.Dantzig和J.Ramser在1959年首先提出的，是物流配送中組合優化領域的熱點問題，并廣泛地應用于現實生活中。電動汽車路徑問題（Electric Vehicle Routing Problem，EVRP）為車輛路徑問題的拓展，具體可以描述電動汽車從配送中心出發（已經充滿電），依次訪問一系列給定的具有不同貨物需求的顧客點，運輸車輛負責配送貨物的同時并規劃出適當的行車路線，來滿足客戶的需求。如果配送過程中超過車輛的貨物裝載量約束，則車輛將返回配送中心進行裝貨，如果超過行駛里程的約束，則到最近的充電服務設施去充電。然后配送車輛繼續訪問客戶點，直至訪問完所有的客戶點，完成配送任務后再返回到配送中心。

2.2 建立模型

隨著對電動汽車路徑問題的不斷研究，根據約束條件的不同，可以構建出不同的模型。如下是在傳統車輛路徑問題研究的基礎上，針對單車型、具有電池容量和貨物裝載量約束，構建的具有三下標的數學模型[5-10]。模型參數描述如表1所示：

表1 模型參數描述

目標函數：

節點訪問約束：

貨物裝載量約束：

時間約束：

電池容量約束：

0-1決策變量：

基于EVRP問題的基本含義可歸納為如下所示的基本模型結構：

基于純電動汽車的配送特征，通過電池容量約束、貨物裝載量約束、節點約束和時間約束，其中時間約束包括對客戶的服務時間、車輛的充電時間以及行駛時間，構建目標函數為配送距離最小化的規劃模型，即在滿足顧客需求的情況下，盡可能做到能源消耗和成本的最小化。

3 總結與展望

隨著純電動汽車的大力推廣使用，越來越多的企業采用純電動汽車進行物流的配送活動。通過上述對純電動汽車的續航里程、充電服務設施以及充電時間的分析，可以看出純電動汽車路徑問題與傳統的車輛路徑問題大不相同。本文研究帶有時間窗的純電動汽車路徑規劃問題，綜合考慮節點約束、貨物容量約束、時間約束以及電池容量約束，構建行駛距離最小化的車輛路徑規劃模型，從而減少純電動汽車在配送過程中的迂回距離。合理的配送路徑，能夠有效提高客戶的滿意度，降低車輛在行駛過程中的配送成本，并對純電動汽車的推廣應用起到積極的作用。

近幾年，電動汽車已經成為一種發展趨勢，目前大多數學者研究的是靜態車輛路徑規劃，而在實際的物流配送過程中，存在很多動態因素，如客戶需求量的不確定性等，所以需要針對電動汽車自身的特點建立更加符合實際的多約束條件的數學模型，更好地應用于實際配送過程中。

[1]麻友良，嚴云兵.電動汽車概論[M].北京：機械工業出版社，2012.

[2]歐雯要，葉瑞克，鮑健強.電動汽車的節能減碳價值研究[J].未來與發展，2012,2(5):36-40.

[3]柳開濟.純電動物流配送車運營調度模型設計與實現[D].成都：電子科技大學（碩士學位論文），2016.

[4]劉華旭.基于電動汽車技術特征的共同配送調度優化研究[D].北京：北京交通大學（碩士學位論文），2012.

[5]Narath Bhusiri,Ali Gul Qureshi,Eiichi Taniguchi.Application of the Just-In-Time Concept in Urban Freight Transport[J].Procedia-Social and Behavioral Sciences,2014,125(3):171-185.

[6]Michael Schneider,Andreas Stenger,Dominik Goeke.The Electric Vehicle Routing Problem with Time Windows and Recharging Stations[J].Institute for Operations Research and the Management Sciences,2014,14(2):1-22.

[7]Alejandro Montoya,Christelle Guéret,Jorge E.Mendoza,et al.A modified multi-space sampling heuristic for the green vehicle routing problem[J].Transportation Research Part C Emerging Technologies,2016,70:113-128.

[8]A Afroditi,M Boile,S Theofanis,et al.Electric Vehicle Routing Problem with industry constraints:trends and insights for future research[J].Transportation Research Procedia,2014(3):452-459.

[9]邢芳芳，賈永基，蔣琪,等.帶充電設施的電動班車路徑規劃問題研究[J].中國管理科學與工程，2016,5(4):149-156.

[10]楊裙，馮鵬祥.電動汽車物流配送系統的換電站選址與路徑優化問題研究[J].中國管理科學，2015,23(9):87-96.

Analysis of Pure Electric Vehicle Path Planning Model Based on Time Window Constraint

LIU Yingxin (School of Management,Bohai University,Jinzhou 121000,China)

With the environmental pollution and the depletion of resources,the development of low-carbon economy is the inevitable way to achieve sustainable development in China.As the main source of energy consumption and greenhouse gas emissions,logistics and distribution industry has attracted much attention.Therefore,this paper uses pure electric vehicles instead of traditional vehicles for logistics and distribution.Through the analysis of the advantages and distribution characteristics of pure electric vehicles,and the classification of vehicle routing problems,the paper proposes the pure electric vehicle routing problem.Finally,considering the characteristics of cargo loading,node access and time constraints in the traditional vehicle routing problem,a pure electric vehicle path planning model with time window is constructed according to the characteristics of electric vehicle battery capacity,charging facilities and charging time.

pure electric vehicle;time window constraint;path planning;logistics distribution

U116.2

A

1002-3100（2017）12-0083-05

2017-10-21

遼寧省社科規劃基金重點項目，項目編號：L16AGL002。

劉穎鑫（1993-），女，遼寧瓦房店人，渤海大學管理學院物流工程專業碩士研究生，研究方向：物流工程與管理。