黃敏芳，劉敬，郭瓊

（1.華北電力大學(xué) 經(jīng)濟(jì)與管理學(xué)院，北京 102206；2.新能源電力與低碳發(fā)展研究北京市重點(diǎn)實(shí)驗(yàn)室（華北電力大學(xué)），北京 102206）

1 引言

電子商務(wù)環(huán)境下城區(qū)物流配送呈現(xiàn)小批量、多品種、多頻次、短周期和送貨時(shí)間嚴(yán)格等特點(diǎn)。近年來，網(wǎng)上零售企業(yè)，如蘇寧易購、當(dāng)當(dāng)、亞馬遜等，其網(wǎng)上交易訂單量日益增長，由此引發(fā)更加頻繁的交通運(yùn)輸活動。據(jù)兩會報(bào)道顯示，我國快遞量去年一年達(dá)到400億件，占世界超40%的市場份額。國際能源署（IEA）2009年發(fā)布的《運(yùn)輸、能源與二氧化碳：邁向可持續(xù)發(fā)展》[1]的報(bào)告顯示，全球25%的二氧化碳等溫室氣體的排放來源于交通運(yùn)輸。如何通過發(fā)展“綠色物流”來減少電子商務(wù)物流配送對環(huán)境的污染，做好物流配送中的“最后一公里”服務(wù)，是當(dāng)前物流業(yè)面臨的主要難題。北京市《關(guān)于對部分機(jī)動車采取交通管理措施降低污染物排放的通告》[2]提出對城區(qū)內(nèi)送貨車輛環(huán)保問題的監(jiān)控勢在必行。電動汽車逐漸成為電子商務(wù)環(huán)境下頻繁的城區(qū)物流配送活動的最佳選擇。2014年物流與運(yùn)輸車輛高峰論壇[3]首次提出可將電動三輪車用于解決電子商務(wù)城區(qū)物流配送活動。據(jù)國家電網(wǎng)報(bào)顯示，至2017年10月底，全國充電網(wǎng)絡(luò)已覆蓋26個(gè)省、273個(gè)城市，充電樁數(shù)量達(dá)到4.5萬個(gè)。

車輛路徑問題（vehicle routing problem，VRP）是物流運(yùn)作管理面臨的難點(diǎn)問題，該問題可定義為：對一系列發(fā)貨點(diǎn)/收貨點(diǎn)，安排適當(dāng)?shù)男熊嚶肪€，使車輛有序通過，在滿足一定約束條件（如貨物需求量、發(fā)貨量、交貨時(shí)間、車容量限制、行駛里程限制等）下，達(dá)到一定的目標(biāo)，如路程最短、費(fèi)用最小、時(shí)間盡量少、使用車輛盡量少等[4]。目前對于VRP的研究方向多集中在單車場[5]、多車場[6]、單車型[5-6]、多車型[7]、帶時(shí)間窗約束[8-9]、隨機(jī)需求[10-12]等，研究方法可歸結(jié)為精確算法[8]、傳統(tǒng)啟發(fā)式算法[5]以及現(xiàn)代啟發(fā)式算法[6-7,9-11]。如今，隨著國家大力倡導(dǎo)節(jié)能減排，電動物流車已廣泛應(yīng)用到我國的各大城市，電動汽車在物流中的應(yīng)用已成為該行業(yè)相關(guān)學(xué)者的研究熱點(diǎn)。目前，國內(nèi)外已有諸多學(xué)者將電動汽車應(yīng)用到物流配送問題上，并展開研究，如：M Schneider等[13]研究了帶時(shí)間窗和充電站的車輛路徑問題，以最小化車輛數(shù)和總行駛距離為目標(biāo)，采用變鄰域搜索算法和禁忌搜索算法進(jìn)行求解，并設(shè)計(jì)兩種算例分別用CPLEX和禁忌搜索算法得出結(jié)果。Siddiqi等[14]研究了粒子群算法求解電動汽車在多種約束下的路徑優(yōu)化問題。Baouche[15]建立定位的節(jié)能路徑優(yōu)化模型使能源消耗最低。Kobayashi等[16]研究不需要充電、充電一次和充電多次三種情況下電動汽車的路徑搜索，將路徑分為多條子路徑后采用Dijkstra算法精確求解。Wang和Song[17]研究了帶時(shí)間窗的電動汽車的定位和路徑優(yōu)化問題，通過禁忌搜索算法和大規(guī)模鄰域搜索算法相結(jié)合求解。Keskin和Gatay[18]研究了帶時(shí)間窗的電動汽車不完全充電情況下的車輛路徑問題，采用自適應(yīng)大規(guī)模鄰域搜索算法求解。以上文獻(xiàn)均為本文研究的展開提供了借鑒。

本文研究的是帶軟時(shí)間窗的電動汽車物流配送車輛路徑問題，除了傳統(tǒng)VRP帶來的求解難度以外，電動汽車的應(yīng)用會涉及到行駛過程中的充電問題，大大提升了問題的復(fù)雜度。目前，在電動汽車車輛路徑問題的相關(guān)研究上，關(guān)于具體的成本核算部分，多數(shù)文獻(xiàn)采用不計(jì)充電成本或按充電次數(shù)計(jì)費(fèi)的方式，這種粗略核算的方式會降低結(jié)果的精確度。本文選擇的是由充電度數(shù)決定的充電成本，提高了充電成本核算的精確性，解決了由粗略計(jì)算充電成本導(dǎo)致的車輛路線與實(shí)際情況偏差較大的缺陷，增強(qiáng)了電動汽車在物流配送問題上的應(yīng)用靈活性。由于遺傳算法具有可并行搜索、編碼方式多樣等優(yōu)良特點(diǎn)，可用于解決較復(fù)雜的組合優(yōu)化問題，因此本文采用遺傳算法進(jìn)行求解，并結(jié)合問題實(shí)際特征改進(jìn)算法。

2 問題描述及模型構(gòu)建

2.1 問題描述

本文研究的是配送中心在收到客戶貨物后，用電動物流車給客戶配送。由于電動汽車具有一定的續(xù)駛里程限制，在電量耗盡之前需要及時(shí)進(jìn)行能源補(bǔ)給，目前能源補(bǔ)給的方式主要有三種：常規(guī)充電、快速充電和更換電池。在電子商務(wù)環(huán)境下“最后一公里”配送過程中，因客戶對時(shí)間窗有較嚴(yán)格的限制，所以只能通過快充或更換電池進(jìn)行能源補(bǔ)給。而更換電池的專業(yè)化要求較高，換電車輛需要專業(yè)的維修保養(yǎng)，所以本文考慮的是較為便捷的充電模式。一般情況下，在同城區(qū)中會配置有多個(gè)充電站，為電動汽車的正常行駛提供便利。

本文構(gòu)建模型的目標(biāo)是使整個(gè)配送過程中總物流成本最小。為簡化研究，做出如下假設(shè)：

（1）每個(gè)客戶點(diǎn)只能由一輛車配送，一輛車可以服務(wù)多個(gè)客戶點(diǎn)，電動汽車在配送期間最多可充電一次。不考慮配送車輛的巡回使用；

（2）配送中心數(shù)量為單個(gè)；

（3）所有車輛從配送中心出發(fā)時(shí)均為滿電狀態(tài)；

（4）不考慮充電站車輛排隊(duì)等候，即車輛進(jìn)入充電站就可直接充電，并且車輛在充電站均是充滿電再駛離；

（5）車輛在客戶點(diǎn)停留過程中不消耗電能。

為更清楚的描述問題，本文給出如圖1所示的車輛線路示例。圖1中有1個(gè)配送中心（0），2個(gè)充電站（B1，B2），8個(gè)客戶點(diǎn)（1，2，…，8），圖1（a）為各個(gè)點(diǎn)的位置分布情況，圖1（b）為經(jīng)過計(jì)算機(jī)求解后的最終行駛路線結(jié)果，即為配送中心→1→6→3→B1→7→8→配送中心（路線1），配送中心→2→4→5→配送中心（路線2）。

圖1 車輛路線圖

2.2 符號定義

本文使用的各參數(shù)定義如下：

N=Na?Nc?B，表示配送中心、客戶和充電站的集合，其中，Na表示配送中心的集合，這里為單一配送中心，用o表示，Nc表示客戶點(diǎn)的集合，B表示充電站的集合，A={(i,j)|i,j∈N,i≠j}表示路段的集合，客戶i的時(shí)間窗為(ei,li)，i∈Nc，配送車輛的集合為K，配送車輛用符號k表示，k∈K，單位車輛的啟動成本為f（元/輛），電動汽車單位距離的運(yùn)輸成本為y（元/km），單位距離消耗的電量為e（kW·h/km），單位充電成本為c（元/kW·h），其它符號定義如下：

Z：配送總成本；

qi：客戶點(diǎn)i的需求量；

Qk：配送車輛k的車載容量，k∈K；

Qik：配送車輛k離開i點(diǎn)時(shí)最多可剩余貨物量，k∈K，i∈N；

dij：i點(diǎn)到j(luò)點(diǎn)的距離（單位：km），i,j∈N；

V：配送車輛勻速行駛速度；

U：配送車輛的最大電池容量；

：車輛k到達(dá)i點(diǎn)時(shí)的剩余電量；

：車輛k離開i點(diǎn)時(shí)的剩余電量；

r：充電率；

Ti：配送車輛到達(dá)客戶點(diǎn)i的時(shí)間；

：配送車輛離開客戶點(diǎn)i的時(shí)間；

Wi：配送車輛在i點(diǎn)的等待時(shí)間；

Si：配送車輛在客戶點(diǎn)i的服務(wù)時(shí)間。

決策變量為：

物流配送電動汽車車輛路徑問題需考慮客戶訂單的時(shí)間窗。時(shí)間窗分為硬時(shí)間窗、軟時(shí)間窗和混合時(shí)間窗。硬時(shí)間窗要求車輛必須要在時(shí)間窗內(nèi)到達(dá)，早到必須等待，而遲到則拒收。軟時(shí)間窗是客戶對時(shí)間窗要求具有較大的彈性，允許配送員（車輛）提前或延后到達(dá)客戶，在實(shí)際生活中更實(shí)用、更靈活。軟時(shí)間窗需要考慮準(zhǔn)時(shí)到達(dá)、提前到達(dá)與延遲到達(dá)等不同情形下的懲罰成本，因此帶軟時(shí)間窗的求解難度更大?；旌蠒r(shí)間窗表示若配送員（車輛）在期望時(shí)間窗內(nèi)到達(dá)，則客戶滿意度為100%，若在期望時(shí)間窗外，但在允許時(shí)間窗內(nèi)到達(dá)，則客戶滿意度會隨著時(shí)間差的增大而降低。本文對帶軟時(shí)間窗的物流配送電動汽車充電站定位與車輛路徑問題進(jìn)行剖析，用EPU表示車輛提前到達(dá)產(chǎn)生的單位時(shí)間機(jī)會成本，LPU表示車輛延遲到達(dá)產(chǎn)生的單位時(shí)間懲罰成本，則客戶i的懲罰成本Pi(Ti)可表示為：

2.3 模型構(gòu)建

基于上述參數(shù)定義、決策變量、假設(shè)條件和懲罰成本函數(shù)，構(gòu)建了帶軟時(shí)間窗的電動汽車車輛路徑問題的非線性規(guī)劃模型。

模型中式（1）為目標(biāo)函數(shù)，表示配送總成本最小，包括啟動車輛成本、運(yùn)輸成本、充電成本以及表示客戶滿意度的懲罰成本；式（2）表示每個(gè)客戶點(diǎn)到達(dá)和離開的車輛數(shù)相等，即流量平衡；式（3）表示配送車輛的起點(diǎn)和終點(diǎn)都是配送中心；式（4）表示車輛裝載容量和客戶需求量之間的關(guān)系，若配送車輛從客戶i到客戶j進(jìn)行配送，則車輛離開j點(diǎn)的最多可剩余貨物量至多為車輛離開i時(shí)的最多可剩余貨物量減去j點(diǎn)的需求量，否則該約束松弛；式（5）表示車輛k從配送中心出發(fā)時(shí)滿載；式（6）表示每輛電動汽車服務(wù)客戶的需求量之和不超過車載容量；式（7）表示配送車輛離開i點(diǎn)時(shí)的時(shí)間；式（8）表示配送車輛離開i點(diǎn)到達(dá)j點(diǎn)的時(shí)間；式（9）表示電動汽車若提前到達(dá)，則需等待，等待時(shí)間為ei-Ti，否則，無需等待，等待時(shí)間為0；公式（10）表示配送車輛離開j點(diǎn)時(shí)的時(shí)間；式（11）和式（12）分別表示配送車輛離開配送中心與充電站時(shí)電量均充滿；式（13）表示配送車輛在客戶點(diǎn)服務(wù)期間不消耗電能；式（14）表示電量與行駛里程的關(guān)系；式（15）確保電動汽車有足夠的電量到達(dá)路線上的每一個(gè)點(diǎn)；式（16）保證每次配送任務(wù)都以配送中心為起點(diǎn)和終點(diǎn)。

3 算法設(shè)計(jì)

3.1 算法原理

算法求解原理如圖2所示。

圖2 算法流程圖

3.2 算法步驟

算法設(shè)計(jì)中的核心內(nèi)容如下：

（1）編碼設(shè)計(jì)。遺傳算法的編碼方式有二進(jìn)制編碼、格雷碼編碼以及自然數(shù)編碼。本文采用應(yīng)用較為普遍的自然數(shù)編碼。染色體長度為m+ch+k+2，其中m表示客戶點(diǎn)數(shù)量，ch表示充電站數(shù)量，k表示所需車輛數(shù)，數(shù)字2代表車輛出發(fā)和返回均在配送中心。配送中心編碼為0，客戶點(diǎn)序列為1，2，…，m，充電站序列用m+1，m+2，…，m+ch表示。如用3輛車為8個(gè)客戶服務(wù)，充電站個(gè)數(shù)為2，則其某一染色體可以是0，6，5，7，0，8，9，1，0，2，3，10，4，0，表示路線一為車輛1從配送中心出發(fā)，依次為客戶6，5，7服務(wù)后返回配送中心，路線二為車輛2從配送中心出發(fā)，在為客戶8服務(wù)后去充電站9充電，再為客戶1服務(wù)后返回配送中心，路線三為車輛3從配送中心出發(fā)，先為客戶2，客戶3服務(wù)后去充電站10充電，再去服務(wù)客戶4，最后返回配送中心。

（2）約束處理與適應(yīng)度函數(shù)。對于電動汽車的行駛里程以及載重限制，若直接對染色體操作，則會導(dǎo)致染色體長度不同，進(jìn)而無法進(jìn)行之后的交叉、變異等操作，故本文采用懲罰函數(shù)的形式對行駛里程和載重進(jìn)行約束。為尋求最經(jīng)濟(jì)的配送方案，本文以物流成本作為優(yōu)化目標(biāo)，對于其中的充電成本，目前有按充電次數(shù)計(jì)費(fèi)以及不計(jì)充電成本兩種方式，不計(jì)充電成本適用于有自建充電站的物流企業(yè)，但對于沒有自建充電站的企業(yè)來說，按充電次數(shù)來計(jì)算充電成本是不夠準(zhǔn)確的，為增加成本核算的精確度，這里選擇根據(jù)充電度數(shù)計(jì)算充電成本，引入矩陣Dis來記錄所有路線方案中車輛到達(dá)某一點(diǎn)i（i∈N）的已行駛路程，一旦判斷車輛到達(dá)充電站j（j∈B），即可通過矩陣Dis獲取該充電站對應(yīng)的已行駛里程數(shù)，記為dj。由假設(shè)條件電動車在充電站充滿電再駛離，可通過公式dj*e*c計(jì)算得出在充電站j花費(fèi)的充電成本（若c的單位為元/h，則是根據(jù)充電時(shí)長計(jì)算的，這里是根據(jù)充電度數(shù)）。這種方式增加了電動汽車配送成本核算的靈活性。最后制定出的目標(biāo)函數(shù)如下：

其中，d1(i)代表某條染色體的總運(yùn)輸距離（這里的i是染色體的序號），e2(i)（這里的i是染色體的序號）代表所有車輛在所有充電站前電動汽車行駛的總距離，ddd(i)和qqq(i)設(shè)計(jì)時(shí)均為0或1，滿足里程條件或載重條件的為0，否則為1，M是很大的正數(shù)，使得不滿足約束條件的染色體的目標(biāo)值很大。由于動態(tài)線性標(biāo)定法可以擴(kuò)大適應(yīng)度函數(shù)尋優(yōu)能力[11]，故本文采用此方法進(jìn)行計(jì)算，具體適應(yīng)度函數(shù)如下：

（3）選擇。采用輪盤賭的方式，計(jì)算初始染色體的適應(yīng)度。生成一個(gè)隨機(jī)數(shù)，根據(jù)選擇概率判斷是否進(jìn)行選擇操作，若滿足條件，則選擇適應(yīng)度大的兩條染色體作為父代染色體，否則，不進(jìn)行選擇操作。

（4）交叉。為獲得較好性能的染色體，提高算法的尋優(yōu)能力，本文采用交換某段子路徑的交叉方式，具體操作如下：

Step1：分別在兩個(gè)父代染色體上隨機(jī)選擇一段子路徑（如子路徑A和子路徑B）。

父代染色體1：

父代染色體2：

Step2：被選擇的子路徑前置。將父代染色體1中的子路徑A前置，同時(shí)，將該染色體中除子路徑A外的編碼按父代染色體2中的順序排列，在末尾填0，最后再將剩余的0插入到除子路徑外的染色體段中，得到子代染色體1。同理得到子代染色體2。

父代染色體1：

父代染色體2：

（5）變異。選擇2-交換變異算子進(jìn)行染色體變異，即在父代染色體上隨機(jī)選擇2個(gè)位置進(jìn)行交換，再將變異后的染色體重插入子代中去。

4 算例分析

選取一個(gè)中等規(guī)模算例來驗(yàn)證本文提出模型和求解算法的有效性，算例中共包含42個(gè)點(diǎn)，包括1個(gè)配送中心，35個(gè)客戶，6個(gè)充電站。各個(gè)點(diǎn)的位置坐標(biāo)、客戶需求量、時(shí)間窗和客戶點(diǎn)停留時(shí)間均給定（也可由計(jì)算機(jī)在一定范圍內(nèi)隨機(jī)生成）。電動汽車的續(xù)航里程為200km，其他參數(shù)數(shù)值設(shè)置見表1。

表1 初始參數(shù)值

采用MATLAB語言編寫程序，在處理器為Intel(R)Core(TM)i5-3230M，內(nèi)存為4G的筆記本上運(yùn)行，交叉和變異概率分別為0.9和0.05，迭代500次，重復(fù)求解10次，取最小的運(yùn)行結(jié)果做為最優(yōu)路線，得到的最小配送成本為3 525.63元。

表2 車輛路線表

圖3 車輛路線圖

表3 配送成本與車輛數(shù)數(shù)據(jù)表

改變配送車輛數(shù)，重新求解，結(jié)果見表3，發(fā)現(xiàn)隨著車輛數(shù)的增加，配送成本總體呈上升趨勢，這是由于車輛的啟動成本在總成本中所占比重大于充電成本、行駛成本和懲罰成本的比重，使得增加車輛的代價(jià)較大。然而也出現(xiàn)了增加車輛數(shù)成本反而降低的現(xiàn)象，原因是雖然車輛數(shù)量的增多增加了啟動成本，但其通過提高配送效率所降低的懲罰成本已大于增加的車輛啟動成本了。

5 結(jié)語

從網(wǎng)上零售商的配送中心角度出發(fā)，提出了帶軟時(shí)間窗及充電站定位的電動汽車車輛路徑問題，從配送中心角度分析了車輛使用數(shù)量與使用成本對總物流配送成本的影響。借助計(jì)算機(jī)實(shí)現(xiàn)了基于遺傳算法的求解方法，獲得最優(yōu)配送路線。提出的根據(jù)充電度數(shù)來計(jì)算充電成本的方式，增強(qiáng)了成本核算的精確性，克服了已有研究中不計(jì)充電成本或粗算充電成本的不足。此外，在采用遺傳算法求解問題時(shí)，采用改進(jìn)交叉算子，使得優(yōu)秀的子路徑能夠最大程度上被保留，該方法比采用順序交叉、循環(huán)交叉、位置交叉更適用于多車輛配送的車輛路徑問題。

物流配送活動中會產(chǎn)生不確定性情況，如路況、車況等，可結(jié)合該類情況提出更實(shí)用的問題求解方法；電動汽車到達(dá)充電站往往會產(chǎn)生等待時(shí)間，可通過對車輛的排隊(duì)分布進(jìn)行模擬，獲得合理的等待時(shí)間，在問題求解中將該時(shí)間因素考慮進(jìn)去。