毛慧婷，石建邁，周玉珍，陳 超

（國防科技大學(xué) 系統(tǒng)工程學(xué)院 信息系統(tǒng)工程重點實驗室，湖南 長沙 410073）

1 引言

隨著溫室氣體的大量排放以及全球氣候變暖等環(huán)境問題日益嚴(yán)重，近年來關(guān)于如何降低交通運(yùn)輸領(lǐng)域碳排放的研究越來越多。根據(jù)歐盟的統(tǒng)計數(shù)據(jù)，大約20%—25%全球能源消耗和二氧化碳排放量源于交通運(yùn)輸系統(tǒng)，其中陸上交通占75%[1]。目前國內(nèi)外各大商業(yè)公司已經(jīng)意識到充電汽車在綠色物流領(lǐng)域具有明顯優(yōu)勢，開始研究以充電汽車為主導(dǎo)的物流配送系統(tǒng)。

車輛路徑問題（vehicle routing problem，VRP）是物流運(yùn)作管理的經(jīng)典問題，通過優(yōu)化配送車輛的行駛路徑來提高物流配送的效益，如路程最短、費(fèi)用最小、時間盡量少、使用車輛盡量少等[2]。應(yīng)用電動汽車替代傳統(tǒng)汽車進(jìn)行物流配送，在帶來環(huán)境和成本等方面效益的同時，也為車輛路徑規(guī)劃問題帶來了新的挑戰(zhàn)，引起了國內(nèi)外學(xué)者的廣泛關(guān)注。相對于傳統(tǒng)路徑規(guī)劃，電動汽車的路徑規(guī)劃問題增加了中途充電站的選擇決策，使得解空間的組合更多，求解難度更高。

從當(dāng)前充電站的主流服務(wù)方式來看，一般分為快速充電和更換電池兩種模式。在快速充電模式下，一般假設(shè)電動汽車在充電站充滿電池，其充電時間由到達(dá)充電站時的剩余電量決定[3-8]。Schneider等[3]研究了帶時間窗口的電動汽車路徑規(guī)劃問題，以最小化車輛數(shù)和總行駛距離為目標(biāo)，提出了一種變鄰域搜索與禁忌搜索相結(jié)合的混合啟發(fā)式算法。Hiermann等[5]研究了電動汽車與燃油汽車混合模式下的路徑規(guī)劃問題，并設(shè)計了分支定價與混合啟發(fā)式算法。Montoya等[6]分析了非線性充電速率對電動汽車路徑規(guī)劃的影響，并設(shè)計了針對非線性充電情況的搜索算子。Guo等[7]提出應(yīng)用遺傳算法求解帶時間窗口的電動汽車路徑規(guī)劃問題。國內(nèi)學(xué)者黃敏芳等[8]提出了帶軟時間窗及充電站定位的電動汽車車輛路徑問題，并設(shè)計改進(jìn)了遺傳算法進(jìn)行求解。在快速充電模式下，電動汽車也可以選擇部分充電，而不是一次充滿，從而節(jié)約時間和費(fèi)用[9-11]。Keskin等[9]研究了部分充電模式下的路徑規(guī)劃問題，實驗結(jié)果顯示，部分充電策略相比較于完全充電策略可以有效減少配送里程。Ding等[10]通過實驗對比，證明了部分充電模式下電動汽車的充電時間、客戶點的等待時間以及行駛時長都相對較短。Macrina等[11]研究了混合車隊中電動汽車允許部分充電情況下的車輛路徑規(guī)劃問題，并應(yīng)用大鄰域搜索算法進(jìn)行了求解。Verma[12]提出了快速充電與電池更換兩種模式下的電動汽車路徑規(guī)劃，并限定電動汽車采用快速充電時必須充滿。

從電動汽車物流系統(tǒng)的運(yùn)行來看，完全或部分快速充電策略的充電成本較低，但是需要一定的充電時間，可能使得電動汽車由于客戶時間窗口不滿足而減少客戶訪問數(shù)量；直接更換電池的策略在時間上可以忽略不計，但一般成本較高。當(dāng)前文獻(xiàn)大多研究一種充電策略下的路徑規(guī)劃，很少考慮兩種充電策略混合模式下的電動汽車路徑優(yōu)化。當(dāng)電動汽車在充電站既可以選擇快速部分充電，也可以選擇更換電池時，電動汽車的充電策略更加靈活柔性，進(jìn)而降低總體成本。但是這種混合柔性的充電策略使得電動汽車路徑規(guī)劃的建模和求解更加復(fù)雜。在傳統(tǒng)電動汽車路徑規(guī)劃模型的基礎(chǔ)上，本文研究了柔性充電策略下帶時間窗的電動汽車路徑規(guī)劃問題，建立了問題的非線性混合整數(shù)規(guī)劃模型。通過結(jié)合蟻群算法和局部搜索策略，設(shè)計了一種改進(jìn)型蟻群算法，提高了問題的求解效率。通過三種不同客戶分布模式下的路徑優(yōu)化實驗，驗證了算法的有效性，并分析了柔性充電方式對于降低配送總成本的效果。

2 數(shù)學(xué)模型構(gòu)建

2.1 問題描述

本文研究的電動汽車路徑規(guī)劃問題中，每個客戶點都有特定的服務(wù)時間窗口以及服務(wù)時長。配送車隊均由同一類型的電動汽車組成，具有固定大小的車載容量以及最大的行駛里程。在行駛過程中，電量隨著行駛距離成比例消耗。電動汽車電量不足時，可以訪問充電站補(bǔ)充電量。所有充電站均可提供兩種充電方式：（1）快速充電，可以根據(jù)電動汽車的實際需要進(jìn)行部分充電或充滿；（2）更換電池，直接為電動汽車更換上新的滿電電池。考慮到電池替換所花的時間很短，這里我們假設(shè)電池更換的時間可忽略不計。

在本文的模型中,目標(biāo)函數(shù)是最小化配送總成本，包括車輛固定成本、行駛成本、等待成本以及充電成本。建模中的其他設(shè)定如下：

（1）每個客戶點只能由一輛車配送，一輛車可以服務(wù)多個客戶點；

（2）配送中心數(shù)量為單個，所有車輛從配送中心出發(fā)并回到配送中心；

（3）所有車輛從配送中心出發(fā)時均為滿電狀態(tài)，并且不考慮配送車輛的重復(fù)使用；

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

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

2.2 符號定義

在建模過程中，V={1,...,N}表示客戶點集合，F(xiàn)表示充電站集合，頂點0和N+1分別為出發(fā)點和結(jié)束點，兩者重合，為配送中心的位置。設(shè)集合V'=V?F，為了區(qū)別不同實例中的倉庫，以0或者N+1作 為 該 集 合 的 下 標(biāo) ，如?{0} 和?{N+1}。 A={(i,j)|i,j∈表示路段的集合。每一條路段都有相應(yīng)的距離值dij以及行駛時間tij，車輛電池的電量消耗率為r。在充電站采用快速充電方式時，電動汽車的充電率為g。若選擇更換電池，則每次電池替換的成本為cs。Di表示客戶i的需求量，si為客戶服務(wù)時長，客戶點的服務(wù)時間窗口為[ei,li]。電動汽車的容量表示為C，電池容量為Q。模型中的連續(xù)決策變量包括：τi,ui和vi分別為車輛到達(dá)客戶點i的服務(wù)開始時間，剩余貨物容量和剩余電量水平，qi為電動汽車在充電站采用快充模式時的充電量，Yi為車輛離開充電站i時的電量水平，δi為在客戶點i∈N處的等待時間。如果路徑中含有路段(i,j)，0-1決策變量xij的值取1，否則取0；如果在充電站i∈F選擇了電池交換技術(shù)0-1決策變量yi的值取1，否則取0；如果在充電站i∈F選擇了傳統(tǒng)充電方式0-1決策變量zi的值取1，否則取0。

模型中所用到的符號總結(jié)如下，見表1。

2.3 數(shù)學(xué)模型

混合柔性充電策略支持下的電動汽車配送路徑優(yōu)化數(shù)學(xué)模型如下：

表1 模型中的符號表示

模型中公式（1）為目標(biāo)函數(shù)，最小化總體成本。約束（2）和（3）確保每個客戶點都恰好被一輛車訪問一次。約束（4）為網(wǎng)絡(luò)流平衡條件。約束（5）和（6）確保了路徑中客戶點之間時間窗的連續(xù)可行性。約束（7）保證車輛服務(wù)開始的時間在時間窗內(nèi)。約束（5）-（7）同時消除了路徑中的子回路。約束（8）和（9）確保滿足所有客戶點的需求量。約束（10）和（11）限定電池的電量始終非負(fù)。約束（12）計算車輛離開充電站時的電量水平。約束（13）限制車輛在充電站至多只能選擇一種充電方式。約束（14）確保車輛充完電后的電量不超過最大電池容量。約束（15）-（17）限定所有決策變量的取值范圍。

3 求解算法設(shè)計

為了解決混合充電模式下的電動汽車路徑優(yōu)化問題，本文設(shè)計了一種改進(jìn)的蟻群算法。蟻群算法是一種源于生物界的新仿生類隨機(jī)型搜索算法，由意大利學(xué)者Dorigo等提出，具有群體合作、正反饋選擇、并行計算等特點。作為一種有效的啟發(fā)式算法，近年來蟻群算法逐漸被用于求解各種車輛路徑規(guī)劃問題[13-17]。

為適應(yīng)本文中的電動汽車路徑優(yōu)化求解，對蟻群算法進(jìn)行了兩方面的改進(jìn)。首先考慮到充電站的選擇和充電策略的優(yōu)化，設(shè)計了一個最優(yōu)充電站插入啟發(fā)式；其次鑒于問題的復(fù)雜性，引入局部搜索算法，擴(kuò)大蟻群算法迭代過程中的搜索空間，增加最優(yōu)解的搜索概率。改進(jìn)蟻群算法的主要步驟見算法1。

算法1:改進(jìn)蟻群算法

Step1 參數(shù)初始化；

Step2 鄰近點搜索構(gòu)造初始可行解ψ0；

Step3 設(shè)定初始信息素濃度；

Step4 讓k只螞蟻同時從配送中心出發(fā)，并行搜索產(chǎn)生k個未插入充電站的解φ；

Step5 調(diào)用充電站插入算法，插入充電站；

Step6 調(diào)用局部搜索算法，進(jìn)行局部搜索；

Step7 信息素更新；

Step8 若算法循環(huán)到最大次數(shù)NCmax后停止，輸出最優(yōu)可行解Ψbest；否則，轉(zhuǎn)到Step4。

3.1 蟻群初始解構(gòu)造

蟻群是正反饋系統(tǒng)，在覓食過程中，每只螞蟻會在所經(jīng)過的路徑上留下一種化學(xué)物質(zhì)—信息素，后面的螞蟻可分辨其強(qiáng)度，從而選擇信息素濃度高的路徑。隨著信息素的揮發(fā)，采用正反饋機(jī)制，螞蟻將會選擇相對較短且信息素濃度較高的路徑。隨著路徑上的信息素不斷進(jìn)行更新和累積，螞蟻最終會找到覓食的最短路徑。

本文利用鄰近點搜索及充電站插入算法來生成初始可行解（ψ0）。所有路徑的信息素初始濃度設(shè)為該初始解目標(biāo)函數(shù)值的倒數(shù)。設(shè)蟻群系統(tǒng)的規(guī)模為P，螞蟻在生成解的過程中不斷選擇下一個客戶點進(jìn)行訪問，直至沒有滿足條件的客戶點。然后該螞蟻返回配送中心重新出發(fā)，直到訪問完所有客戶點。螞蟻在選擇下一個客戶點 j是根據(jù)一個轉(zhuǎn)移概率公式來決定的，該概率公式同時考慮了信息素濃度以及路徑的距離長短。轉(zhuǎn)移概率公式如下：

其中dij為邊的長度。

3.2 信息素更新

在搜索過程中信息素的更新至關(guān)重要。首先由于自然界中螞蟻留下的信息素會隨著時間的推移而揮發(fā)，因此在更新過程中引入了信息素?fù)]發(fā)機(jī)制。其次本文采取了精英螞蟻策略，即除了螞蟻搜索產(chǎn)生的最優(yōu)解所經(jīng)過的路徑之外，其余精英螞蟻所產(chǎn)生的較優(yōu)可接受路徑也會被用來更新信息素的濃度。本文中，信息素濃度按如下方式進(jìn)行更新：

其中，Q是一個常數(shù)，Costib為當(dāng)前最優(yōu)解，為δth精英螞蟻的解。

3.3 充電站啟發(fā)式插入算法

由于電動汽車電池容量有限，其行駛里程往往受到電量水平的限制。蟻群算法所構(gòu)造的未插入充電站的解（φ0）往往存在違背里程約束的路徑。因此，這些路徑中需要插入充電站對車輛進(jìn)行適當(dāng)充電才能順利完成該條路徑的配送。為此本文設(shè)計了一個充電站最優(yōu)插入啟發(fā)式算法，主要步驟見算法2。

算法2:充電站啟發(fā)式插入算法

輸入：未插入充電站的解γ0

輸出：最優(yōu)可行解γfea

Step1 找出解γ0中所有違背電動里程約束的不可行路徑；

Step2 找到電動汽車出發(fā)后能到達(dá)的最遠(yuǎn)客戶點；

Step3 對最遠(yuǎn)點與配送中心或者前一個充電站之間的所有點進(jìn)行以下循環(huán)；

Step4 在當(dāng)前點后插入距離最近的充電站；

Step5 確定充電水平；

Step6 檢查時間窗可行性；

Step7 若該條路徑違背時間窗，則移除相應(yīng)的客戶點到移除點集合Vunvisit；

Step8 若算法已遍歷所有可插充電站位置，則循環(huán)停止，否則轉(zhuǎn)到Step3;

Step9 若集合Vunvisit不為空，則用鄰近點搜索并重復(fù)以上Step1-9，否則算法停止。

充電站插入算法的基本思路是對于超過車輛最大里程的回路，找到電動汽車出發(fā)后能到達(dá)的最遠(yuǎn)客戶點，即車輛從配送中心或者充電站出發(fā)可到達(dá)但無法繼續(xù)到達(dá)下一個客戶點。在該客戶點后插入距離最近的充電站。若余下的路徑仍里程違背，則繼續(xù)按此方式插入充電站。在搜索過程中，遍歷所有可插入充電站的位置。

在插充電站過程中，充電方式的選擇將會決定充電之后的電池電量水平。由于路徑中充電次數(shù)不定，假定當(dāng)快速充電模式下所需的充電時間超過某一個閾值T0時，將選擇電池交換技術(shù)作為充電方式。否則，選擇快速充電方式按照實際需求對車輛進(jìn)行部分充電。T0的定義如下：

其中，σ是一個0-1之間的參數(shù)，Q g表示將電量為0的電池進(jìn)行快速充電至充滿所需要的時間。

當(dāng)充電水平確定之后，檢查該回路上的客戶點時間窗是否仍然滿足。若有客戶點的時間窗不滿足，則將該客戶點從該路徑中移除并將其添加到集合Vunvisit。在整個充電站插入的過程中，可行解的接受第一準(zhǔn)則首先是盡可能保留較多的客戶點，其次則是接受較低配送成本的可行解。

3.4 局部搜索算法

為了進(jìn)一步防止蟻群算法陷入局部優(yōu)，引入局部搜索算法，擴(kuò)大蟻群算法每次迭代過程中的搜索空間，提高可行解尋優(yōu)的質(zhì)量。本文中，局部搜索算法的核心是移除算子和插入算子。在搜索過程中，考慮到客戶點位置每一次的重新調(diào)整都很可能會導(dǎo)致充電站最優(yōu)插入位置的改變，因此局部搜索是在當(dāng)前解移除充電站之后的路徑上進(jìn)行的。在每一次迭代之后，重新對調(diào)整后的路徑應(yīng)用充電站插入算法，生成可行解。

3.4.1 移除算子。本文中使用的移除算子分為兩類：路徑移除和客戶點移除。路徑移除是指移除被選中回路上的所有客戶點，而客戶點移除則是移除一定數(shù)量λ的客戶點。λ由總的客戶點數(shù)量決定，在一個特定區(qū)間內(nèi)隨機(jī)選擇。

（1）最短路徑刪除算子：該算子從當(dāng)前解中挑選出最短的一條回路，刪除該回路上所有客戶點并將這些客戶點放進(jìn)移除列表中，該算子的目的是盡可能最大化車載量的利用率。

（2）結(jié)束最早路徑刪除算子：該算子從當(dāng)前解中選擇配送時間結(jié)束最早的一條回路，刪除該回路上所有客戶點并將這些客戶點放進(jìn)移除列表中，該算子的目的是基于現(xiàn)實因素考慮，盡可能達(dá)到相應(yīng)的工作時長。

（3）隨機(jī)客戶點刪除算子：該算子從當(dāng)前解中隨機(jī)選擇λ客戶點刪除，隨機(jī)性的刪除操作可以使得搜索過程更加多樣化，防止陷入局部優(yōu)。

（4）最差客戶點刪除：該算子計算出當(dāng)前解中每個客戶點距離前后鄰接的客戶點距離之和，按此數(shù)值進(jìn)行降序排序，選擇前λ個客戶點進(jìn)行刪除。

3.4.2 插入算子。插入算子是將移除列表中的客戶點重新插回被破壞的當(dāng)前解中，在插入過程中需要考慮該條回路的車容量及時間窗的可行性，但不需要考慮車輛里程的限制。

（1）貪婪插入：將被移除客戶點依次插回到當(dāng)前解最優(yōu)的位置，使得每次插入增加的成本最低。

（2）后悔值-2插入：找出所有被移除客戶點的最優(yōu)和次優(yōu)插入位置，并計算最優(yōu)插入成本和次優(yōu)插入成本，取兩者的差值，將差值較大的客戶點優(yōu)先插入其最優(yōu)位置。

在搜索過程中，所有移除和插入算子均有一個相同的權(quán)重，按照輪盤賭進(jìn)行隨機(jī)選擇組合。局部搜索算法的主要步驟見算法3。

算法3:局部搜索算法

輸入：未插入充電站的初始解φ0

輸出：最優(yōu)可行解Ψbest

Step1 對各個算子的權(quán)重進(jìn)行初始化；

Step2 將初始解φ0插入充電站產(chǎn)生當(dāng)前可行解，Ψcurrent，Ψbest←Ψcurrent；

Step3 移除當(dāng)前可行解中的充電站；

Step4 隨機(jī)挑選一個移除算子，生成客戶點移除列表?；

Step5 隨機(jī)選擇一個插入算子，將列表?中的客戶點重新插入當(dāng)前解；

Step6 調(diào)用插入算法，插入充電站生成當(dāng)前可行解Ψcurrent；

Step7 若當(dāng)前可行解的總成本低于最優(yōu)解，則Ψbest←Ψcurrent；

Step8 若算法循環(huán)到最大次數(shù)NCmax后停止，輸出最優(yōu)可行解Ψbest；否則，轉(zhuǎn)到Step3。

4 實驗結(jié)果及分析

為了對模型和算法進(jìn)行驗證，采用三個典型客戶分布的算例進(jìn)行實驗。每個算例中共包含122個點，其中一個配送中心、100個客戶點、21個充電站。三個算例中，算例A的客戶點呈隨機(jī)分散分布，如圖1所示；算例B中客戶點呈簇狀聚集分布，如圖2所示；算例C中的客戶點分布兼具簇狀聚集和隨機(jī)分散的特點，如圖3所示。

圖1 算例A中點的分布

圖2 算例B中點的分布

圖3 算例C中點的分布

在實驗中電動汽車的相關(guān)成本參數(shù)見表2。電池更換成本設(shè)定為給一個電量為0的電池進(jìn)行快速充電充滿所需成本的1.2倍。

表2 電動汽車成本相關(guān)參數(shù)值

蟻群算法相關(guān)的參數(shù)值設(shè)定為P=30，α=5，β=5，φ =0.25，Q=100，算法所有代碼由Visual C++編程實現(xiàn)。

4.1 局部搜索算法的效果

為了防止蟻群算法陷入局部最優(yōu)，本文設(shè)計了以移除和插入算子為核心的局部搜索算法，與蟻群算法集成，來擴(kuò)大解空間的搜索效率。傳統(tǒng)蟻群算法（ACO）和集成局部搜索的蟻群算法（ACO-LS）求解三個算例的計算結(jié)果見表3，負(fù)Δ%值意味著最優(yōu)解質(zhì)量的提高。實驗結(jié)果證實，局部搜索可以大大增強(qiáng)算法全局尋優(yōu)的能力，從而顯著地提高最優(yōu)解的質(zhì)量。

表3 蟻群算法改進(jìn)效果對比實驗結(jié)果

4.2 充電策略對比分析

基于三個實例，進(jìn)一步對比分析了不同充電策略即允許部分充電的快充策略、更換電池以及兩者混合的充電策略對配送成本的影響，實驗結(jié)果見表4。結(jié)果顯示，對于三個不同的實例，混合充電策略相比于單一充電策略均能有效降低配送總成本，這是因為多種充電方式能更靈活地安排充電模式，使得車輛成本、等待成本及充電成本都相對較低。雖然單一電池更換策略使得車輛數(shù)能最大程度地減少，但是由于換電池的成本顯著增加了，所以配送總成本不僅沒有降低反而有所上升。而單一部分快充策略雖能最大程度地降低充電成本，但由于其充電時間較長，會出現(xiàn)更多客戶點的時間窗不可行，導(dǎo)致需要更多的車輛去服務(wù)客戶，從而大幅度增加了車輛使用成本，使得總成本上升。

表4 不同充電策略對比

5 總結(jié)與展望

為了更好地降低充電時間對客戶時間窗的影響，本文提出了混合柔性充電方式支持下帶時間窗的電動汽車路徑問題。柔性充電策略的引入為充電汽車的應(yīng)用提供了更加靈活的運(yùn)作方式，也提供了進(jìn)一步降低配送時間和成本的可行途徑。針對電動汽車的中途充電需求，在傳統(tǒng)車輛路徑的基礎(chǔ)上，本文設(shè)計了一種充電站啟發(fā)插入算法快速計算充電站的插入位置。同時，通過設(shè)計局部搜索算法并集成到蟻群算法的迭代過程中，提出了一種改進(jìn)的蟻群算法。以三個具備典型客戶點分布的實例為基礎(chǔ)，對比了改進(jìn)蟻群算法的效果。實驗結(jié)果顯示蟻群算法中嵌入的局部搜索對于提高解的質(zhì)量有著顯著的優(yōu)勢。通過混合充電策略和單一充電策略的對比試驗，驗證了混合充電策略對于降低配送成本的作用。為物流公司選擇充電方式提供了具有參考價值的建議。

在下一步的研究中，電動汽車路徑規(guī)劃問題可以考慮更多的現(xiàn)實約束因素。例如，配送過程中的交通道路擁堵情況往往會影響配送的效率。在大規(guī)模配送場景中，多配送中心的電動汽車路徑規(guī)劃問題具有很高的應(yīng)用潛力，具有較大的研究意義。此外，考慮充電樁的選址與路徑問題相結(jié)合也是未來研究的方向之一。