負載影響下純電動汽車配送路徑規劃及充電策略

劉育良，陳淮莉

（上海海事大學物流科學與工程研究院，上海 201306）

（*通信作者電子郵箱1487630534@qq.com）

0 引言

隨著城市化進程的加快，人們對城市生活的質量也提出了高要求，城市配送物流作為城市生活的重要組成部分之一，配送方式的完善將會有助于城市生活質量的改進。電動汽車在城市配送物流中的應用越來越受到關注，其中以深圳作為首要的代表，連續三年成為純電動物流汽車保有量最大的城市，為綠色的城市物流作出了貢獻。

城市物流配送的問題，就是傳統的車輛路徑規劃問題，但由于電動汽車需要在充電站進行充電，而且充電時間是一個不容忽略的因素，所以純電動汽車應用在城市物流配送中具有其特殊的性質。對于純電動汽車在城市物流配送中的應用研究，Keskin 等［1］將其描述為一個帶時間窗的路徑規劃問題，建立了混合整數線性規劃模型，考慮排隊充電問題和偏離時間窗的懲罰成本，運用數學優化技術CPLEX（WebSphere ILOG CPLEX）來求解小實例。Madankumar等［2］把它作為一種綠色物流，研究了配送及集貨的路徑規劃問題。van Heeswijk等［3］將其描述為帶時間窗的配送問題，建立了配送模型。Schneider 等［4］將其描述為帶有時間窗和充電站的問題，考慮了有限的車輛貨運能力以及客戶時間窗，提出了一種混合啟發式算法，它結合了變量鄰域搜索算法和禁忌搜索啟發式算法，進行了相關問題的實例測試。Barth 等［5］建立了車輛負載與能耗影響的函數關系，Kancharla 等［6］則在此基礎上考慮了負載對純電動汽車路徑的影響，建立了距離最小化的模型，建立了考慮負載消耗的功率估計函數，并提出了一種具有特殊算子的自適應大鄰域搜索算法。蘇粟等［7］也考慮了實時動態能耗的影響，研究了純電動汽車充電路徑規劃，發現考慮實時動態能耗，能夠制定更合理的充電策略。

對純電動汽車在城市物流配送中的研究，設置不同的目標會使計算的結果有所差異。Schiffer等［8］則提出了一個不同的目標函數，不僅最小化了行駛距離，還最小化了所需的車輛、設置的充電站數量以及總成本。他認為如果可以將充電樁選址與車輛的路徑規劃相結合，會得到更優的結果，該目標函數的設置相對來說更符合企業的需求。賈永基等［9］針對多目標獨占性電動汽車路徑問題，提出了基于時間敏感系數的客戶滿意度評價函數，時間敏感系數體現了客戶對未能在指定的時間窗口內得到服務的容忍程度。該研究把客戶的滿意程度量化，以實現客戶的最大滿意度為目標。Schneider 等［10］在考慮交換服務需求不確定性和電能價格不確定性的情況下，計算單站和交換站網絡的最優設備配置，提出了一個針對小問題的最優解算法和一個基于動態規劃和蒙特卡羅采樣的近似算法，為充電作業進行了合理的安排設置。Zhang 等［11］建立了能量消耗最小化的目標函數，并驗證了以能量消耗最低的優越性。

考慮純電動汽車中途充電的問題，可以根據設定的路線安排充電任務，但是對于何時充電，充多少電，也是本領域內研究的一個問題。傳統的研究是考慮在電池的電量低于某個設定值時再充電，這就需要車輛停留一段較長的時間來進行充電任務。但Keskin 等［12］放寬了完全充電限制，允許車輛部分充電，由于充電時間較短，在現實生活中更為實用。Sweda［13］也建立了純電動車輛在充電策略的模型，但是在現有電池技術的情況下，允許部分充電對電池的損耗程度較大，這項研究沒有考慮電池的損耗成本。郭放等［14］指出，當電池進行深度放電之后，對電池的損耗程度會加深，降低電池的使用壽命。目前，在我國市面上的純電動汽車多采用三元鋰電池，這種電池的特性決定了潛在的充電成本。所以，物流企業在安排配送路線以及充電策略時要考慮部分充電對電池帶來的損耗成本。

在配送模型的求解上，梁承姬等［15］采用改進遺傳算法（Genetic Algorithm，GA）求解，提高了求解速度，快速獲得一個較優的解。Zhang 等［16］設計了蟻群（Ant Colony Optimization，ACO）算法進行求解，發現蟻群算法在求解此類問題時具有良好的特性。馮杰等［17］也采用蟻群算法求解了生鮮品的配送問題，并與遺傳算法和粒子群算法進行比較，驗證了蟻群算法在求解路徑規劃問題時的優越性。

以上文獻對于該問題的研究，并未針對城市物流中的多批次、更細化的時間窗進行解決，并且，單個車輛一般都是在一天中出車一次，并未研究循環多次出車中充電任務的安排。另外，這些研究大都把車輛的電量消耗設定為一個穩定的值，其實負載對車輛電量的消耗有著密切的聯系。本文考慮實時負載對電池輸出功率的影響，更準確地計算電量的損耗，并針對細化的時間窗，考慮多次循環出車的路徑規劃和充電策略。

1 問題描述

城市物流配送是一個很常見的問題，隨著城市化進行的加快發展，城市物流的合理化運營，有助于緩解城市交通壓力。近些年，純電動汽車在技術上的發展取得了一定的成果，這為純電動汽車實現商用奠定了基礎。例如城市公交車，大多都采用了純電動汽車實現了運營，這不僅減少了城市污染氣體的排放，更降低了城市的噪聲污染，為城市生活品質的提升作出了貢獻。如果城市物流配送任務可以大規模使用純電動汽車來進行運營，這對城市生活的改進將會是很明顯的

一般對城市物流配送的研究都是采用燃油車進行配送，由于燃油車當燃料用盡時，很快就能進行補充，對配送任務的時間影響程度很小。但由于純電動汽車的電量是有限的，進行電量補充需要較長的時間，這就對后續的配送任務有較大的影響，尤其是在滿足顧客需求時間窗這一方面更加需要合理的調度。在純電動汽車配送領域內，普遍的研究并沒有考慮貨載重量對車輛耗電的影響。在車輛負載不同時，傳統的內燃機油耗變化范圍較小，而純電動貨車電池耗電情況變化相對較大，由于在配送過程中，車輛的負載在經過每一客戶點時都發生變化，所以純電動車輛的負載影響不能忽略。本文參考了文獻［6］中提到的貨載對車輛實時耗電的影響，公式如下：

本文假定車輛保持勻速在平直的道路上行駛，公式如下：

簡化后為：

其中：M為車的整體質量，包含車重m（單位：kg）和車上的貨物重量μ；v表示車輛行駛的速度（單位：km/h）；a表示車輛的加速度；g表示重力常量；θ為道路坡度角（單位：度）；ρ為空氣密度（單位：kg/m3）；A為迎面面積（單位：m2）；Cd為空氣動力阻力系數；Cr為滾動阻力系數；ε為車輛傳動系效率；pe是連續的發動機功率輸出（單位：kW）。具體的參數設置如表1所示。

表1 能耗公式參數Tab.1 Energy consumption formula parameters

另外，對純電動汽車配送的研究中，很少有安排車輛多次循環出車的情況。由于城市面積有一定的限制，純電動汽車的行駛里程最多大約可以達到220 km，單次出車大多時候可以在配送任務完成之后進行充電，這同時就會加大純電動汽車的運營成本。本文考慮了多個客戶在一天內的需求由少量的純電動汽車循環進行配送，當車輛完成一次配送之后，返回配送中心裝載下一次配送的貨物，同時要考慮中途可能在某一點進行充電，盡可能避免與客戶的需求時間窗沖突，提高配送的時間準確性。考慮負載對能耗的影響，可以更加準確地安排運營計劃。為滿足充電的需求，文中假設有10 個充電站分布在該區域內，采用快速充電的方式為純電動汽車提供充電服務。

2 模型建立

2.1 參數定義

模型中各個參數的含義如下：

m表示車重；

μj表示到達客戶j時車的負載量；

xijk表示車輛從i到j且由車輛k來完成任務；

K表示車輛的集合；

τi表示車輛到達i點的時刻；

tij表示車輛從i到j的時間；

si表示車輛在i點的服務時間（卸貨時間）；

yi表示站點i的貨物需求量；

τj表示車輛到j點的時刻；

η表示充電時間關于充電量的比率系數；

N表示充電的次數；

Q表示電池的總電量；

qi表示在i點時的剩余電量；

ej表示到達j的最早時刻；

lj表示到達j的最晚時刻；

Z表示車輛的最大負載量；

Δit表示表示客戶i的貨物的運輸時間；

Δid表示表示客戶i的貨物的運輸距離；

χ表示運輸時間的比例系數；

ω表示運輸距離的比例系數。

2.2 模型建立

式（1）為目標函數，表示企業當天的運營成本最小。

當天的運營成本分為五個部分：

C1表示一個車輛當天配備司機的人工成本，Ck1為一個常量，取值為200。計算公式如下：

C2表示一個車輛的變動運輸成本系數，Ck2是一個常量，取值0.3。該成本包括車輛的維修、變動的保養費用等。這些費用是與車輛的行駛里程成正比關系的，隨著車輛行駛里程的增加而增加。計算公式如下：

C3表示每單位電量的價格，Ck3是一個常量，取值為1。該成本包括汽車中途的充電成本以及返回配送中心之后充滿的成本。計算公式如下：

C4表示貨損成本，貨損是指在貨物在運輸過程中產生的損耗，由于貨物的種類不同，貨損的程度也不一樣。對于易碎品、生鮮品等，貨損量會較普通貨物多一些。本文參考文獻［3］，設定隨著運輸時間和運輸距離的增加，貨損成本隨之增加，Ck4是一個常量，取0.1；χ和ω取值分別為0.4 和0.6。計算公式如下：

C5表示車輛的懲罰成本。由于現實中臨時突發狀況的影響，如堵車、道路維護、調度失誤等情況的發生，加入懲罰成本。當車輛在客戶最早服務時間之前到達時，產生等待成本，懲罰因子ch設為12 元/小時。超出最遲服務時間時，設懲罰成本Mp為無限大，保證必須滿足客戶的服務要求。計算公式如下：

式（2）表示xijk為一個0-1 變量，若車輛k從i到j則為1，否則為0；

式（3）表示每一個客戶的訂單任務都要完成；

式（4）表示充電站最多被訪問一次；

式（5）表示每個節點進入的車輛和離開的車輛數量相等；

式（6）和（7）表示車輛到達i的時刻要小于到達j的時刻；

式（8）表示車輛在每個客戶點時，車輛剩余電量不能低于總電量的15%；

式（9）表示車輛要在客戶需求時間窗內完成配送任務；

式（10）表示車輛在j點時的負載量小于在i點時的負載量；

式（11）表示車輛的負載量在零和最大負載量之間；

式（12）至（14）是對到達j時的剩余電量的約束，不能大于在i的剩余電量，并且都不能大于總電量；

式（15）表示車輛k在完成單次任務之后返回配送中心，裝載下一次配送的貨物；

式（16）表示車輛k在完成一天的任務之后返回配送中心，結束當天配送任務。

3 算法設計

本文所研究的問題是傳統的路徑規劃問題的延伸，由于電動汽車需要充電且充電時長不可忽略的特點，在有時間窗約束情況下的路徑規劃就會比較復雜。再者，純電動汽車在不同負載情況下的能量消耗較燃油車更為明顯。所以，對純電動汽車的負載與能耗關系的考慮，可以更加準確地計算車輛的能耗情況，合理安排下一階段的任務分配情況。蟻群算法在求解路徑規劃問題時采用正向反饋、啟發式搜索的特性，大幅提高了求解的效率。

本文設計的蟻群算法考慮了時間窗的約束，加入了時間緊迫因子，最大限度地保證車輛滿足客戶服務時間窗。在進行下一客戶點的選擇時，車上已載貨物與下一站點客戶需求之和不能大于車輛最大負載，到達下一站點的電量不能低于總電量的15%，以此來限制螞蟻的選擇范圍。在螞蟻的單次旅行中，負載量由配送中心開始為最大，每訪問一個客戶，負載減小，到達后一站點的負載量始終小于在前一站點的負載量。在當天配送任務開始時，螞蟻在配送中心處的電量為100%，車輛的電量在到達充電站之前，電量逐漸減少，在每一客戶站點比前一站點電量低。螞蟻在完成單次配送任務返回配送中心后，負載量由0 變為下次配送任務的總貨量，進行下一次配送任務。

蟻群算法中兩個重要的因素為轉移概率和信息素更新，轉移概率用來設定螞蟻選擇下一站點的選擇規則，信息素更新機制決定螞蟻選擇路線的概率，以下結合實際問題作出相應設置，并給出了算法的具體流程。

3.1 轉移概率

轉移概率函數的設置是路徑規劃的重要因素，對客戶點的選擇起著重要的作用。首先將螞蟻放置在配送中心0 處，依次進行下一個站點的選擇。在進行下一個站點的選擇時，要考慮路徑上的信息素濃度τij(t)，它表示在t次迭代時，路徑i到j上的信息素量，初始時刻均設置為0。當路徑上經過的螞蟻越多，留下的信息素量則越多，下一只螞蟻則優先選擇該路線，以此形成正反饋機制。另外，還要考慮距離的因素，當進行下一站點選擇時，在滿足其他條件的同時，優先選擇距離較近的站點。設立啟發函數ηij(t)=1/dij，表示隨路徑的加長，選擇該站點的期望則越低。最后，考慮到本文中的是時間窗約束情況，加入時間緊迫因子，其中Ej表示時間窗的最早到達時間，Lj表示時間窗的最晚到達時間。同時考慮三種因素，參考文獻［15-17］，設定第k只螞蟻從i到j的轉移概率函數如下：

其中：allowk表示待訪問站點的集合；α表示信息素的重要程度；β表示距離因子的重要程度；γ表示時間緊迫因子的重要程度。

3.2 信息素更新

每只螞蟻在產生一條路徑之后，在路徑上釋放信息素，原路徑上的信息素隨之逐漸消失。當所有螞蟻完成一次循環后，各個客戶點之間的信息素濃度需要隨之更新。設定ρ為信息素的消逝程度，0 ＜ρ＜1，信息素更新的公式為：

由公式可知，當路徑距離越短時，該路徑上各處的信息素濃度越高，下一只螞蟻選擇該路徑的可能性越大。

3.3 算法步驟

步驟1 設置各代的螞蟻數量和最大的迭代次數，初始化禁忌表，初始化各點之間的信息素濃度，初始化參數，計算各點之間的距離和車輛穿越兩點之間的時間。

步驟2 把所有的螞蟻都放置在配送中心0點處，禁忌表的第一列均設置為配送中心0處。

步驟3 依照禁忌表，根據殘留的信息素量和啟發式信息，受到轉移概率函數的約束，獨立選擇下一位置。

步驟4 判斷車輛電量到達下一站點時電量是否仍大于電池總量的15%，是則繼續下一步；否則，前往最近的充電站進行充電，返回步驟3，重新選擇下一站點。

步驟5 判斷下一點的需求與已載貨物之和是否超過車輛最大負載，若超過，在禁忌表上填入配送中心0 處，車輛返回配送中心裝載貨物，進行下一次配送任務的規劃；否則填入選擇的位置點。

步驟6 返回步驟3，直到單只螞蟻把所有的客戶點都加入到禁忌表中，再開始下一只螞蟻的旅行。

步驟7 直到所有的螞蟻都遍歷了所有的客戶點，找到所有可行解中的最優解，更新信息素，更新禁忌表，進行下一代的迭代，返回步驟1。

步驟8 迭代到最大次數，在各代中的最優解中挑選出一個最優的解。

4 算例分析

4.1 算例設置

本文以城市A 為例，采用Solomon 算例中的30 個客戶的基本數據，按照現有的城市物流配送模式完成配送任務。各客戶點的訂單需求及服務時間如表2所示。

各個客戶的位置坐標如圖1 所示。圖1 中：“0”表示配送中心的位置；“220 km，最大負載量為2 000 kg。按照我國現有的快速充電站”表示客戶的位置坐標，共30個客戶；“”表示充電站的位置，共10個充電站。由圖1可知，客戶均勻地分布在城市區域內，以配送中心為中心大致呈一個扇形。在表2中具體指出了各個客戶的貨物需求量以及服務時間窗，時間窗的范圍為一個小時。為完成配送任務，需盡可能地在客戶要求的服務時間內送達，且要保證車輛的路線距離更短，成本相對最低。在配送過程中，允許車輛當天多次配送，配送途中需要進行充電，車輛的充電時間需要考慮在內。

根據負載的不同，純電動汽車的行駛里程為180 km～的特點，設定充電時間關于充電量的比率系數η為2，表示當充電量為1 kWh時，充電時間為2 min。該區域內設有10個充電站，編號為C1 到C10。車輛在配送中心的裝貨時間設定為30 min，在每一站點的停留卸貨時間為10 min。

采用Matlab2016 編程語言對該案例進行求解，運行環境為64 位Windows 10 操作系統，運行內存為4 GB，CPU 頻率為1.60 GHz。運行10次，選取最優的一次運行結果。

圖1 客戶位置坐標Fig.1 Customer location coordinates

4.2 結果及分析

4.2.1 路徑規劃及充電策略分析

蟻群算法是一種仿生學的智能算法，模擬螞蟻的先天覓食行為，在求解路徑規劃問題時有著較好的優勢。在模型求解中，轉移概率函數中的相關參數對求解的結果及求解的速度有著較大的影響。其中，信息素的重要程度α過大時，螞蟻隨機選擇路徑的概率較小，過小時又會產生局部最優的結果。距離因子β過大或過小時，容易導致路徑局部最優［13］；時間緊迫因子γ越小時，螞蟻會自動選擇更近的時間窗［15］。根據本文的模型特點，設置α=1，β=5，γ=2，結合4.1 節設置的案例，求解得到路徑規劃如圖2所示。

各個車輛的路徑、起始時間、充電次數及行駛里程如表3所示。

由圖2和表3可知，該天的配送任務由三輛純電動汽車完成，車輛1、2、3 的行駛里程分別為275.79 km、266.31 km、278.53 km。三輛車均在中途充電一次，車輛1 在C3 充電站充電，車輛2 在C6 充電站充電，車輛3 在C1 充電站充電。每輛車當天均執行兩次配送任務，提高了車輛的利用率，減少對車輛的使用，同時也降低了配備的司機的人工成本。

圖2 路徑規劃Fig.2 Path planning

表3 各車輛行駛記錄Tab.3 Driving records of vehicles

4.2.2 考慮負載對路徑的影響分析

本文考慮了負載對車輛實時能耗的影響，通過建立功率關于負載重量的能耗函數，計算車輛的實時能耗情況，來為路徑規劃和充電策略提供依據。傳統的能耗計算方法是設定一個穩定值，根據目前我國純電動貨車的實際參數，設定車輛在速度為50 km/h、勻速行駛的情況下，每小時的耗電功率為12.5 kW，結合本文的案例，對是否考慮負載情況下的路徑規劃及充電策略進行比較分析。表4 為兩種情況下的參數比較。

表4 是否考慮負載影響對比Tab.4 Comparison of considering or not considering load impact

由表4 可知，車輛1 和車輛2 在路徑規劃和充電站點的選擇上沒有區別，但車輛2在不考慮負載的影響下，完成客戶12的配送任務之后，去最近的充電站C6 時，剩余電量只剩13.76%，這會導致車輛過度消耗電量，甚至可能引起剩余電量不足的后果。車輛3 在不考慮負載影響時，選擇的是充電站C2，電量正常，但是總路徑卻增加了11.57 km。所以，考慮負載對能耗的實時影響，便于安排合適的充電計劃，在路徑規劃上也能有所優化。

4.2.3 運營成本比較分析

該次配送情況下，各車輛成本結果如表5所示。

表5 各車輛各項成本統計 單位：元Tab.5 Cost statistics of vehicles unit：Yuan

表6 為電動車輛與燃油車輛在同種情況下的運營成本對比。

表6 不同車型成本比較 單位：元Tab.6 Cost comparison of different vehicle types unit：Yuan

由表6 可知，在不考慮純電動車輛的購置成本情況下，純電動車輛的運營成本比傳統燃油車輛低。一方面是因為純電動貨車定期保養的成本較低，另一方面是因為燃油的成本比耗電的成本要高得多。目前用純電動汽車進行物流配送不能普及的主要原因之一就是純電動汽車的車輛購置成本和更換電池的費用較高。但是隨著純電動汽車和電池的成本的下降，純電動汽車在城市物流配送中的應用，不僅可以節約成本，更能降低對城市的空氣污染及噪聲污染。另外，隨著充電基礎設施的大力建設，純電動車輛在路徑規劃和充電策略上也能進一步優化。

4.3 不同規模算例分析

以上的算例包含30 個客戶、10 個快速充電站，是一個較小的數據規模。隨著數據規模的增加，為研究是否考慮負載情況對車輛路徑規劃及充電策略的影響，再選取不同規模的樣本數據進行分析。以C表示客戶數量，R表示充電站的數量。每組實驗進行10 次，選取最優的一個結果，對比情況如表7所示。

表7 不同規模算例比較分析Tab.7 Comparative analysis of different scale examples

由表7 可知，在考慮負載情況下，車輛的當天總行駛距離要比不考慮負載時更優，配送路徑平均減少2%。另外，配送成本也相對有所降低，從而驗證了考慮負載影響對配送路徑規劃優化作用。另一方面，在實驗中，不考慮負載對實時影響時，車輛實際電量存在低于總電量15%的情況，這對配送任務的完成會有一定的干擾。

4.4 算法比較

本文研究的問題屬于路徑規劃問題的范疇，解決此類問題較多采用遺傳算法（GA）。而在文中，設計了蟻群（ACO）算法進行求解。蟻群算法在處理路徑規劃問題時，采用正反饋機制，能高效地尋找最優結果。針對4.3節中實驗的5組樣本數據，采用GA 和ACO 算法進行實驗對比，每組數據均實驗10次，采取最優的一次結果。遺傳算法的種群規模為100，最大迭代次數為500，交叉概率為0.8，變異概率為0.2。結果對比如表8所示。

表8 GA與ACO實驗結果對比Tab.8 Comparison of experimental results of GA and ACO

由實驗結果對比可知，對于5組樣本數據，ACO 在求解這一問題時，能夠得到一個更優的結果；在運行時間上，ACO 比GA也是有著更快的求解速度。由此可知，蟻群算法在求解這一問題時具有較好的特性。

5 結語

本文考慮新能源汽車的發展趨勢，建立了以純電動汽車為基礎的城市物流配送模型，優化配送路徑，降低企業的物流配送成本。由于純電動汽車在一整天的配送過程中需要進行充電，并且充電時間較長不可忽略，故本文結合客戶的時間窗約束以及負載對車輛實時耗電的影響，合理制定電動汽車的充電計劃，避免超出客戶的服務時間，提高服務的時效性。目前，由于純電動汽車的購買成本較高，電池的技術尚未成熟，相較于燃油車來說，在固定成本這一環節仍存在一定的劣勢。但隨著環保力度的加大以及電池技術的進步，用純電動汽車來進行城市物流的配送將會得到普及。