基于車聯網的電動車物流配送路徑優化研究

曹卓 王鑫鑫 徐仟 馬云峰

摘? 要：考慮到電動車在當今物流配送環節中扮演著愈發重要的角色，電動車物流配送過程中充電站位置選擇、充電時機選擇以及相應路徑規劃越來越成為行業內備受關注的問題。文章基于車聯網對電動車物流配送路徑優化進行研究。首先，借助車聯網技術獲取實時交通路況以及充電站相關信息，提出車聯網情境下基于排隊論的充電排隊等待時間預測模型。其次，考慮時間、路徑選擇、電量及載重約束，構建以參與配送車輛的配送時間成本、耗電成本以及時間窗懲罰成本之和最優為目標的電動車物流配送路徑優化模型。最后通過算例驗證模型的可行性以及算法的有效性。實驗結果表明相較于最遲充電策略下的電動車物流配送路徑優化模型，基于車聯網的電動車物流配送路徑優化模型具有顯著優勢。

關鍵詞：車聯網;物流配送;路徑優化;充電選擇

中圖分類號：F253? ? 文獻標志碼：A? ? DOI：10.13714/j.cnki.1002-3100.2023.15.006

Abstract： Considering that electric vehicles play an increasingly important role in today's logistics distribution， the selection of charging station location， charging timing and the corresponding path planning in the logistics distribution of electric vehicles has become an increasingly concerned issue in the industry. Based on the internet of vehicles， this paper studies the optimization of logistics distribution route for electric vehicles. Firstly， the real-time traffic conditions and related information of charging stations were obtained by means of the internet of vehicles technology， and a charging queue waiting time prediction model based on the queuing theory was proposed under the internet of vehicles technology scenario. Secondly， considering the constraints of time， path selection， electric quantity and load， an optimization model of logistics distribution route for electric vehicles was established with the goal of optimizing the sum of distribution time cost， power consumption cost and time window penalty cost of participating vehicles. Finally， an example is given to verify the feasibility of the model and the effectiveness of the algorithm. The experimental results show that compared with the logistics distribution path optimization model of EV based on the latest charging strategy， the logistics distribution path optimization model of EV based on the internet of vehicles has significant advantages.

Key words： internet of vehicles; logistics distribution; path optimization; charging options

0? 引? 言

隨著我國經濟社會的高速發展，城市交通問題、環境污染問題日益凸顯。近年來，末端配送需求的增長讓綠色、可持續的城市物流配送受到高度重視，電動車物流配送所占比重越來越大。EVRP問題是傳統車輛路徑問題的延伸，需要運用電動車進行物流配送，因而需要額外考慮電動車補電、充電站選址、考慮時間窗的約束等問題[1-2]。

電動車物流配送正處于迅速發展階段，現階段充電裝置的供給并不能完全滿足電動車的充電需求，由此產生排隊過程，間接增加了物流企業的運營成本，于是考慮電動車排隊過程，能夠更好地量化配送總時長和企業配送成本問題。Dudin等提出了具有等級評價機制的競爭性排隊系統[3]。Keskin等考慮充電站車輛排隊時間的動態變化性以建立模型，對比了排隊時間對路徑選擇的影響[4]。Mark等人以成本最小和服務水平最高為目標，通過魯棒優化模型研究了電動汽車換電站的選址定容問題[5]?？梢?，目前學者研究考慮排隊論的EVRP問題多停留在傳統站內排隊階段，目標主要是針對充電樁選址定容和優化。

隨著車聯網技術的發展，對探討實時數據和預測數據對電動車充電位置和時機選擇的影響成為可能，車聯網情境下的車輛路徑問題已經引起部分學者關注。5G車聯網和邊緣計算技術的出現，車聯網和傳感器的快速發展為車車協同、車路協同系統提供了保障[6]。鄧友均等利用群智感知技術實時獲得車流與充電站信息，建立電動車路徑優化和充電導航模型[7]。Malikopoulos等建立了智能網聯車輛速度協調優化控制算法，相較人類駕駛能夠降低26%～30%的行程時間[8]。劉智萍等提出基于免疫遺傳優化的實時交通路徑誘導方法。根據期望行駛速度，設定出行預期速率臨界值，利用路網節點間的動態連通性優化路網架構，構建了實時交通局部路網模型[9]。趙建峰等提出了一種新型實用的基于車聯網及云計算平臺的電動車物流的多目標優化調度算法[10]。曾志等通過分析影響路徑阻抗因素，構建路段阻抗函數，提出基于改進型的Logit模型的路徑分配方法?；?G通信平臺和數據傳輸系統，收集各路徑的數據信息，將結果發送給車輛[11]。

總而言之，現有文獻大多只關注電動車充電方式、充電樁選址以及車聯網下的路網優化，較少考慮續航能力、換電站布局和客戶時間窗等約束條件下，通過實時數據和預測數據來選擇電動車充電位置和充電時機。而在車聯網情境下，電動車充電實時數據的獲取成為可能，進一步探討實時數據和預測數據對電動車充電位置及時機的選擇也變得可能和必要。因此本文基于路徑規劃理論和排隊論建立基于車聯網的電動車物流配送路徑優化模型，并以時間窗、續航里程、載重、電量做為約束條件，采用遺傳算法進行求解。

1? 問題與模型

1.1? 問題描述及假設。基于車聯網的電動車物流配送路徑優化問題描述為：單配送中心向多個客戶點進行物流配送，各個客戶點的需求量、地理位置、服務時間以及時間窗要求均已知。配送區域內存在r個充電站，充電車輛滿足先到先充、充完即走的充電策略，且車輛到達服從參數為λ的泊松分布，目標是實現配送總成本最小。為了使本研究更貼近實際問題，現對該數學模型作出以下假設：（1）參與物流配送的電動車均為同一車型，最大裝載量、額定電池容量、單位里程電池電量消耗均一致;（2）配送車輛均從配送中心出發，完成配送任務后返回至物流中心;（3）各個客戶點均只被一輛電動車服務;（4）配送車輛早于或晚于時間窗范圍到達，需接受懲罰成本;（5）配送車輛在充完電后為滿電狀態，且只在配送路徑上耗電，到達客戶點服務時間不耗電，默認熄火狀態;（6）每輛車輛充電速率均為常量，不考慮電池老化導致充電速率的變化;（7）不考慮車輛因實時載重差異導致車輛耗電不同;（8）每個客戶點的服務時間為定值。

1.2? 參數和變量。數學模型中參數、變量及其含義如表1所示。

1.3? 目標函數。本文模型以配送總時間成本C、耗電成本C和時間窗成本C之和作為優化目標，三部分成本之和達到最小即為所追求的目標。其中行駛時間成本、客戶點服務時間成本、排隊時間成本和充電時間成本之和為配送時間成本，目標函數即：

MinC=MinC

+C

+C

（1）

（1）配送時間成本

C=C

T

+T

+T

+T? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

式中：T、T、T和T分別表示行駛時間、客戶點服務時間、排隊時間和充電時間，C表示單位時間配送人員的勞動成本。各部分時間求法如下：

T=∑∑

x? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （3）

v=? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （4）

式（3）中，v表示在車聯網情境下，t時刻路徑ij上車輛k的速度。由決策中心通過WiFi、RFID等無線傳感技術，收集正在配送電動車輛上傳的定位信息，從而計算出該速度。式（4）中，dist為計算復雜路網的歐幾里得距離，l和l分別表示路徑ij上電動車輛k在t和t+1時刻的坐標。

T=∑∑1

-z

·T? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （5）

T=? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （6）

T=? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7）

綜上，配送總時間成本表達式為：

C=C

∑

∑

x+

∑

∑1-

z·

T

++C? ?（8）

（2）耗電成本

車輛配送過程中，車身驅動用電以及車載設備用電等方面均會耗費電量，現假設車輛耗電成本與車輛行駛距離呈正相關，其中β表示單位時間充電電價，可得耗電成本公式如下：

C=β·

∑

∑

·

d

x? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （9）

（3）時間窗成本

城市配送可能遇到一些不可控因素，導致到達客戶點時間與客戶預期時間不符，從而引發時間窗懲罰成本。設定令客戶滿意的時間窗區間為

T，

T，如果車輛提早到達懲罰成本為γ，延遲到達則懲罰成本為γ。因此，本文時間窗懲罰成本見式（10）。

F

T=

（10）

由此可得，時間窗成本為：

C=∑∑F

T? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（11）

1.4? 約束條件。在所建的基于車聯網的電動車物流配送優化模型中，需要滿足以下四方面約束，即時間約束、路徑選擇約束、電量約束和載重約束。

（1）時間約束

對于被訪問的任意客戶點j，電動車k到達該客戶點的時刻可以表示如下：

T=x

T+1-

z

T

+z

T

+， ?k∈K; ?s∈S; ?i， j∈V; i≠j? ? ? ? ? ? ? ? ? ? ? ? （12）

式中，當z=1時，車輛前往充電站充電，當z=0時，車輛前往下一客戶點或者返回配送中心。

（2）路徑選擇約束

∑x=∑x， ?i∈V， k∈K? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （13）

∑∑x=1， ?j∈C? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （14）

∑x=∑x， ?k∈K? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （15）

x=

（16）

x=

（17）

式中：約束（13）表示車輛訪問節點后立即離開，保持進入和離開任意節點的車輛數量相等。約束（14）表示配送過程中一個客戶點只能被訪問一次。約束（15）表示每輛電動車配送的起點和終點均為配送中心。約束（16）為0～1約束，比較兩段時間耗費情況從而選擇更優路徑，前者為從客戶點i出發先前往r充電站再前往下一客戶點j ，計算i-r-j行駛時間以及在充電站r排隊與充電的時間之和;后者為從客戶點i出發先前往客戶點j再前往充電站r排隊與充電，計算i-j-r行駛時間以及在充電站r排隊與充電時間之和。如果前者總時間長，則選擇先前往下一客戶點j;反之，則選擇先前往r充電站充電。由于各客戶點的服務時間相等，因此，在此約束中無需考慮服務時間的差異。約束（17）也為0～1約束，表示車輛行駛到下一客戶點時不足以保證再行駛至任意充電站，則立即前往充電站，否則可以前往下一客戶點。

（3）電量約束

EQ=EQz， ?i∈S， ?k∈K? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （18）

10%EQ≤EQ≤EQ， ?k∈K， ?i∈V? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（19）

EQ=EQ-edx， ?i， j∈V， i≠j， ?k∈K? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（20）

EQ=EQ， ?j∈C， ?k∈K? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（21）

式中：約束（18）表示訪問充電站后電動車剩余電量為100%。約束（19）表示電動車剩余電量最低不得低于10%。約束（20）表示車輛到達客戶點j時的剩余電量，其中e表示單位里程消耗電量。約束（21）表示在客戶點服務時，車輛不消耗電量。

（4）載重約束

由于路徑分配后，每輛電動車均會沿指定路線對各客戶點進行配送直至配送任務結束返回配送中心，配送中途不得返回配送中心裝卸貨，因此，需要約束路徑上各個客戶點需求總量不得大于電動車最大載重量。

∑∑xq≤W， ?k∈K? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（22）

2? 算法與設計

本文采用遺傳算法求解車輛充電時的路徑規劃模型。利用遺傳演變原理，模仿生物的生存進化，通過選擇（Selection）、交叉（Crossover）與變異（Mutation）等基本操作因子，使種群中個體的適應度（Fitness）不斷提高。

本文的遺傳算法流程如下：

Step1? 選擇適合本文模型的自然數編碼方法，基于成本最小化，設計充電情境下的電動車配送路徑;

Step2? 根據本文提出的約束子函數，考慮車輛載重約束、客戶時間窗約束、成本約束等設置算法參數;

Step3? 初始種群定義為500，為了使初始種群在區域內呈線性分布，采用randi函數隨機生成初始種群;

Step4? 適應度計算，將目標函數C的倒數作為適應度，即f=;

Step5? 采用輪盤賭法，將適應度值大小靠后的染色體復制進入下一代，進行選擇;

Step6? 標記初始變量i=0，采用改進型交叉方法，對父代個體進行配對，以父代目標函數值排序，目標函數值大的與大的配對，小的與小的配對，然后利用混沌序列確定交叉點，最后進行交叉處理，該改進型交叉方法能有效提高算法收斂精度;

Step7? 根據本文給定的變異率0.05，采用互換變異，隨機選取染色體上兩個等位基因，交換基因值，得到新的染色體;

Step8? 將上一步得到的父代帶入下一輪循環中;

Step9? 計算適應度值，不斷地進行運算直到得到的結果滿足停止條件，此時可以停止運行，輸出結果，否則，轉至Step5。

3? 算例仿真

3.1? 實驗設置。引入適用于本文模型的隨機生成客戶點算例進行仿真實驗。該算例的客戶點數量為30個，表示為節點1～30;充電站節點數量為3個，坐標表示為節點3161.7，43.6、3224.1，21.4、3331.7，56.6;配送中心的坐標為43.0，44.0，服務時間為960min;車輛額定載重量為7.5t;為方便計算，將配送途中所有車輛的平均行駛速度定為40km/h，續航里程為300km，車輛早于的客戶規定的時間窗到達的懲罰權重為15元/小時，晚到的單位懲罰權重為35元/小時?？蛻酎c信息如表2所示。

3.2? 實驗結果分析。程序采用python3.9.2編程實現，在Intel（R）Core（TM）i7CPU2.60GHz，內存4GB的微機上運行。遺傳算法參數設定如下：種群規模取100，最大迭代次數取500，變異概率取0.05。導入算例數據，可以看出，在代碼迭代計算200次后，迭代曲線收斂，此刻所得值可視為該模型最優解。迭代收斂曲線如圖1所示。

表3為本文算法求出的算例結果，配送中心將會派遣3輛電動車進行配送，均未出現電量耗盡情形，其中配送成本為1 102.3元，耗電成本為757.9元，時間窗成本為436.3元，總成本為2 296.5元。

3.3? 對比分析。將最遲充電策略下的電動車物流配送路徑優化模型M2與本文模型M1進行對比實驗。最遲充電策略指車輛在電量到達閾值時前往充電站充電，本文閾值取10%EQ。模型M2的其他約束條件與模型M1一致，對比實驗結果如表4所示。

對比分析結果表明，在考慮車聯網情境下，相比最遲充電策略下的電動車物流配送路徑優化模型，在排隊與充電時間上節省了30.4%，體現出車聯網在物流配送中節省排隊與充電時間具有顯著優勢，能減少無效時耗，減少配送人員工資開支，也在一定程度上減緩配送人員疲勞度，避免安全隱患。另外，在時間窗成本上節省了23.2%，體現出充電時機選擇在時間窗成本減少上發揮的作用，合適的充電時機不僅能減少排隊與充電環節的時間消耗，而且能從物流配送全局考慮，協調各環節，實現最優路徑方案;而且時間窗滿足率的提高能夠有效提升客戶滿意度，客戶對該物流企業的能力及信譽更加滿意，利于企業的長遠發展?？偝杀痉矫婀澥×?4.6%，進一步證明該模型能有效節省物流配送成本。

總體來說，基于車聯網的電動車路徑優化模型能夠有效減少配送過程中的充電排隊時間，選擇更加合適的充電時機，減少配送全過程中的成本，對于當今日漸流行的電動車配送更具優勢。

4? 結束語

電動車物流配送過程中電動車的充電行為選擇，對成本控制造成較大影響，應引起物流企業的高度重視。本文借助車聯網技術獲取實時交通路況以及充電站相關信息，對電動車物流配送路徑優化進行研究，考慮時間、路徑選擇、電量及載重約束，構建了以參與配送車輛的配送時間總成本、耗電成本以及時間窗懲罰成本之和最優為目標的電動車物流配送路徑優化模型，并運用遺傳算法進行求解。仿真實驗結果表明該模型可以有效解決電動車物流配送中的排隊時間以及充電時機的問題，為配送總成本的節省提供有效幫助。但本文未考慮實際配送過程中因車輛貨物重量的改變所導致的耗電量的影響，后續的研究中會加以改進。

參考文獻：

[1]? CORDEAU J F. VRP with time windows， the vehicle routing problem[J]. SIAM Monographs on Discreate Mathematics and Applications， 2002（9）：157-193.

[2] 邵賽，畢軍，關偉. 基于電動汽車的動態需求車輛路徑問題[J]. 吉林大學學報，2017，47（6）：1688-1695.

[3]? DUDIN A N， DUDIN S A， DUDINA O S， et al. Competitive queueing systems with comparative rating dependent arrivals[J]. Operations Research Perspectives， 2020（7）：100139.

[4]? KESKIN M， LAPORTE G， CATAY B. Electric vehicle routing problem with time-dependent waiting times at recharging stations[J]. Computers & Operations Research， 2019，107：77-94.

[5]? MARK H Y， RONG Y， SHEN Z J M. Infrastructure planning for electric vehicles wit battery swapping[J]. Management Science， 2013，59（7）：1557-1575.

[6] 李靜林，劉志晗，楊放春. 車聯網體系結構及其關鍵技術[J]. 北京郵電大學學報，2014，37（6）：95-100.

[7] 鄧友均，李明，余千，等. 基于實時信息感知的電動汽車物流配送路徑優化與充電導航[J]. 南方電網技術，2017，11（2）：41-49.

[8]? MALIKOPOULOSA A， HONG S， PARK B B， et al. Optimal control for speed harmonization of automated vehicles[J]. IEEE Transactions on Intelligent Transportation Systems， 2018，20（7）：2405-2417.

[9] 劉智萍，周清華，彭吉瓊，等. 基于免疫遺傳優化的實時交通路徑誘導方法[J]. 計算機仿真，2022，39（2）：98-101，418.

[10] 趙建峰，袁細國，梁伯棟，等. 基于車聯網及云計算的電動物流車智能調度算法[J]. 公路交通科技，2019，36（6）：112-124.

[11] 曾志，曾璐，肖松，等. 基于5G的路徑選擇協同優化研究[J]. 科技與創新，2022（2）：159-163，167.

收稿日期：2022-12-14

基金項目：湖北省高校哲社重大課題項目（19ZD015）;中國物流學會研究課題項目（2022CSLKT3-336）

作者簡介：曹? 卓（1999—），男，湖北荊州人，武漢科技大學管理學院碩士研究生，研究方向：物流系統調度優化;王鑫鑫（1980—），男，湖北十堰人，武漢科技大學管理學院，副教授，碩士生導師，研究方向：數字化轉型與商業模式創新、智慧物流;徐? 仟（1998—），女，河南信陽人，武漢科技大學管理學院碩士研究生，研究方向：物流系統調度優化;馬云峰（1972—），男，吉林蛟河人，武漢科技大學管理學院，教授，碩士生導師，研究方向：物流系統規劃、管理定量分析。

引文格式：曹卓，王鑫鑫，徐仟，等. 基于車聯網的電動車物流配送路徑優化研究[J]. 物流科技，2023，46（15）：26-30.