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

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

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

隨著環(huán)境污染和資源的日益枯竭，發(fā)展低碳經(jīng)濟(jì)是我國實(shí)現(xiàn)可持續(xù)發(fā)展的必然之路。物流配送行業(yè)作為我國能源消耗和溫室氣體的主要排放來源，備受人們關(guān)注。文章采用純電動汽車代替?zhèn)鹘y(tǒng)車輛進(jìn)行物流配送。通過對純電動汽車的優(yōu)點(diǎn)和配送特征的分析，以及對車輛路徑問題的分類，提出純電動汽車路徑問題。最后，在考慮傳統(tǒng)車輛路徑規(guī)劃問題中的貨物裝載量、節(jié)點(diǎn)訪問以及時間等約束，結(jié)合電動汽車的電池容量、充電設(shè)施、充電時間等特點(diǎn)，構(gòu)建具有時間窗的純電動汽車路徑規(guī)劃模型。

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

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

1 純電動汽車路徑規(guī)劃問題研究現(xiàn)狀分析

1.1 純電動汽車的優(yōu)點(diǎn)

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

（1）節(jié)能環(huán)保、污染小、噪聲小

傳統(tǒng)機(jī)動車輛的尾氣排放是大氣污染的主要原因之一，而電能是一種清潔能源，電動汽車以電代油，可以達(dá)到改善空氣質(zhì)量的效果。純電動汽車使用電機(jī)驅(qū)動，電機(jī)工作時產(chǎn)生的噪音遠(yuǎn)小于傳統(tǒng)的內(nèi)燃機(jī)，從而降低了噪聲對居民的影響[2]。

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

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

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

純電動汽車路徑規(guī)劃問題與傳統(tǒng)車輛路徑規(guī)劃問題相似。傳統(tǒng)車輛路徑問題（Vehicle Routing Problem，VRP）的構(gòu)成要素通常包括配送車輛、顧客節(jié)點(diǎn)、貨物需求、目標(biāo)函數(shù)和約束條件等。而電動汽車路徑問題還包含充電服務(wù)設(shè)施、以及行駛里程和充電時間的約束，根據(jù)研究的側(cè)重點(diǎn)不同，EVRP可以分為不同的類型[3]。具體分類如下所示：

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

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

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

（4）網(wǎng)絡(luò)屬性。根據(jù)網(wǎng)絡(luò)的不確定性劃分，可以分為靜態(tài)車輛路徑問題：在進(jìn)行車輛路徑優(yōu)化之前，所有與配送車輛相關(guān)的信息已經(jīng)確定，并不會隨著時間變化而變化；動態(tài)車輛路徑問題，進(jìn)行路徑優(yōu)化之前，所有和車輛相關(guān)的信息并不是全部確定而且部分信息會隨著時間的變化而變化。

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

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

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

圖1 VRP最短行駛路線

（1） 續(xù)航能力的約束

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

（2） 充電服務(wù)設(shè)施

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

圖2 行駛里程約束下可到達(dá)節(jié)點(diǎn)的最短路徑

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

因?yàn)樵谂渌瓦^程中增加了對充電站的訪問，可能會造成行駛線路的迂回，因此可以考慮電動車從起始點(diǎn)到達(dá)目的地經(jīng)過加油站的最短行駛距離，此時把充電站看成訪問的坐標(biāo)點(diǎn)。行駛的路線如圖4所示，圖中數(shù)值代表最短可行駛路徑的距離。此時該網(wǎng)絡(luò)圖中最短的行駛路徑為s-5（充電站） -13（充電站）-t，行駛距離為43。對應(yīng)原網(wǎng)絡(luò)圖中電動車的行駛路線為s-1-4-5（充電站） -4-7-13（充電站） -14-t。與圖1中的最短行駛路段7-12-14相比，包括了迂回路線4-5-4和繞行路線7-13-14。具體如圖5所示。

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

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

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

（3） 充電方式

電動汽車的充電模式有三種：可以分為快速充電、慢速充電和機(jī)械充電[4]?？焖俪潆娔Ｊ揭卜Q作應(yīng)急充電，短時間內(nèi)為電池提供大電流的充電服務(wù)，這種充電模式可以滿足顧客在短時間內(nèi)的用電需求，充電時間大概在20分鐘左右。因?yàn)閷﹄姵剡M(jìn)行大功率的充電，所以加速縮短了電池的使用壽命。但目前，我國在建設(shè)大型充電服務(wù)設(shè)施的時候，多采用此種充電方式。配送車輛在行駛的過程中可以采取快速充電方式，為了提高配送過程中顧客的滿意度，所以應(yīng)該把行駛過程中的充電時間考慮在規(guī)劃模型中。

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

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

2 純電動汽車路徑規(guī)劃模型的構(gòu)建

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

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

2.2 建立模型

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

表1 模型參數(shù)描述

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

節(jié)點(diǎn)訪問約束：

貨物裝載量約束：

時間約束：

電池容量約束：

0-1決策變量：

基于EVRP問題的基本含義可歸納為如下所示的基本模型結(jié)構(gòu)：

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

3 總結(jié)與展望

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

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

[1]麻友良，嚴(yán)云兵.電動汽車概論[M].北京：機(jī)械工業(yè)出版社，2012.

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

[3]柳開濟(jì).純電動物流配送車運(yùn)營調(diào)度模型設(shè)計(jì)與實(shí)現(xiàn)[D].成都：電子科技大學(xué)（碩士學(xué)位論文），2016.

[4]劉華旭.基于電動汽車技術(shù)特征的共同配送調(diào)度優(yōu)化研究[D].北京：北京交通大學(xué)（碩士學(xué)位論文），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]邢芳芳，賈永基，蔣琪,等.帶充電設(shè)施的電動班車路徑規(guī)劃問題研究[J].中國管理科學(xué)與工程，2016,5(4):149-156.

[10]楊裙，馮鵬祥.電動汽車物流配送系統(tǒng)的換電站選址與路徑優(yōu)化問題研究[J].中國管理科學(xué)，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

遼寧省社科規(guī)劃基金重點(diǎn)項(xiàng)目，項(xiàng)目編號：L16AGL002。

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