基于頭腦風暴算法的電動貨車路徑優(yōu)化問題

齊元豪，王 凱，付亞平

(青島大學 電氣工程學院，山東 青島 266000)

0 引 言

近年來，關(guān)于電動汽車在物流領(lǐng)域的研究越來越多[1-2]。但關(guān)于電動汽車路徑問題、物流網(wǎng)絡(luò)智能調(diào)度的研究卻不多。Sawik等人[3]提出了一種使噪聲，污染和成本最小化的路徑模型。梁鳳婷等人[4]以低碳、節(jié)能和低成本為目標，分別對傳統(tǒng)汽車和電動汽車的路徑模型進行對比分析。郭戈等人[5]從充電、路徑和車隊配置等角度,著重介紹了3種路徑優(yōu)化分支。金仙力等人[6]提出了一種基于遺傳算法的路徑優(yōu)化算法,用以解決帶時間約束條件的車輛路徑問題。Muratori等人[7]提出了一種描述電動汽車電池能耗的模型。Zhou等人[8]提出了一種電動汽車路徑選擇和充電站位置分布的模型。Zeng等人[9]提出了一種基于隨機地形來進行電量管理的策略。Wang等人[10]對電動汽車與傳統(tǒng)汽車進行了分析對比。

由于市場需求的不斷擴大，物流配送中心車輛資源的有限性，因而在車輛資源與市場之間存在時間和配送服務(wù)上的矛盾與沖突。如何有效分配物流車輛以及提高服務(wù)質(zhì)量一直是車輛調(diào)度問題的關(guān)鍵[11-12]。為此，在這些成果的基礎(chǔ)上，文中研究了帶有時間窗的電動貨車路徑優(yōu)化問題(EVRPTW)，以電動貨車耗電量、顧客滿意度為目的建立數(shù)學模型，以此來對物流中心的車輛調(diào)度任務(wù)進行有效管理和合理分配有限的電動貨車資源。同時，將人工智能方法引入此物流網(wǎng)絡(luò)的智能調(diào)度中，利用智能算法、調(diào)度經(jīng)驗等來求解最優(yōu)解，形成合理有效的調(diào)度方案。

1 問題描述

文中研究的問題屬于帶時間窗有容量的電動汽車路徑優(yōu)化問題(electric vehicle routing problem with time windows，EVRPTW)。此問題可描述為，現(xiàn)有一物流配送中心，電動貨車不唯一且為同一類型。要求電動貨車滿電量從配送中心出發(fā)，前往客戶點送貨，然后回到配送中心。在此過程中，每個客戶點只能被一輛電動貨車服務(wù)且只能服務(wù)一次，同時，每個顧客點都有一個時間窗，電動貨車無論早到還是晚到都會影響顧客滿意度。而電動貨車在配送過程允許去充電站充電。該研究的目標是使電動貨車在整個配送過程中的總耗電量最小、客戶滿意度最高。

2 EVRPTW模型

2.1 電動汽車耗電量模型

參考文獻[7,13]，電動汽車的電量消耗模型如下：

(1)

(2)

Pin=βPout

(3)

其中，E為所有電動貨車從出發(fā)到返回過程中消耗的總電量；Pout、Pin分別為電動貨車牽引階段電池電量輸出功率、再生制動階段電池電量輸入功率；v(t)為電動貨車的行駛速度；M為電動貨車的質(zhì)量；g、fr、α、ρa、CD、Af、δ、β分別為一常數(shù)參數(shù)，其中，0<β<1。

式(1)為電動汽車行駛過程中的耗電量，由兩部分組成，前者為牽引階段耗電量，后者為制動階段耗電量；式(2)則為電動汽車牽引階段耗電功率；式(3)為電動汽車制動階段耗電功率。

2.2 顧客滿意度模型

參考文獻[14-15]中關(guān)于顧客滿意度的描述，文中的顧客滿意度模型如下：

(4)

其中，S為顧客滿意度；Tje、Tjl、Tjk分別為電動貨車k到達j點顧客滿意度為0的最早到達時間、最晚到達時間以及實際到達時間。

式(4)為j點顧客的滿意度，是由電動貨車的到達時間決定的。根據(jù)到達時間可分為三部分：早于ej，ej與lj之間，晚于lj，滿意度計算公式分別如上式所示。

2.3 EVRPTW模型

模型如下：

(5)

(6)

約束條件如下：

(7)

(8)

(9)

(10)

Qmin≤Qjk≤Qmax,j∈V,k∈K

(11)

QOk=Qmax，k∈K

(12)

Wjk=(Wik-wj)xijk,i∈V,j∈V,k∈K

(13)

Wjk≤Wmax,j∈V,k∈K

(14)

tkc+tkp)xijkyik，i∈V,j∈V,k∈K

(15)

tjk=max{Tjk,ej},j∈S∪O,k∈K

(16)

Tik=0,i∈O,k∈K

(17)

(18)

其中，K為電動貨車集；O為配貨中心；R為充電站點集；S為顧客點集；V為三者集合；Ekij為電動貨車k從i點到j(luò)點的耗電量；tkp為電動貨車k的排隊等候時間；Qmax、Qmin、Qjk分別為電動貨車的電池容量、最低電量允許值以及實時電量；Wjk為電動貨車k在j點的重量；wj為卸貨量；Wmax為最大載重量；tijk為行駛時間；vk為卸貨速度；tkc為充電時間；yjk、xijk、zj分別為一判定值，若j點為充電站，zj為1，否則為0，若電動貨車k在j點充電yjk為1，否則為0，若電動貨車k從i到j(luò)行駛，xijk為1，否則為0；A為一任意大數(shù)值。

式(5)表示整個配送過程中電動貨車消耗的總電能；式(6)為整個配送過程中的顧客滿意度之和；式(7)確保每個顧客只被一輛車服務(wù)；式(8)確保貨車路徑不重復(fù)；式(9)確保電動貨車都從配送中心出發(fā)最后返回配送中心；式(10)為電動貨車在j點時的電量；式(11)為電動貨車的電量約束；式(12)表示電動貨車滿電量出發(fā)；式(13)為電動貨車j點的載重量；式(14)為電動貨車的載重量不能超過自身容量；式(15)為電動貨車j點的到達時間，第一項為不充電時到達下一點的時間，第二項為充電時到達下一點的時間；式(16)為電動貨車j點開始卸貨的時間，最早卸貨時間為客戶要求的最早到達時間；式(17)表示電動貨車從配送中心出發(fā)時間為0；式(18)為調(diào)用的電動貨車數(shù)量。

3 頭腦風暴算法

頭腦風暴(BSO)[16-18]是一種將搜索空間不斷縮減的算法。此算法通過不斷迭代，最終將局部最優(yōu)解慢慢精確至全局最優(yōu)解。其基本過程如圖1所示。

圖1 頭腦風暴算法流程

3.1 種群初始化

隨機產(chǎn)生n個個體，每個個體代表一種配送方案。這里應(yīng)用Matlab仿真軟件進行仿真，故個體采用二維編碼的方式進行表示。例如，若用數(shù)字0表示配送中心，數(shù)字1-10表示顧客，數(shù)字11-13表示充電站，則個體隨機產(chǎn)生的過程可表示如下：首先，得到顧客經(jīng)過順序，如[1 2 3 4 5 6 7 8 9 10]；其次，鑒于顧客貨物需求以及電動貨車容量進行分組，若顧客需求皆為3，電動貨車容量為10，則上述順序可更新為[0 1 2 3 0 4 5 6 0 7 8 9 0 10 0]，每兩個數(shù)字0之間的數(shù)字即為一輛電動貨車的配送路線，此順序即采用了4輛電動貨車；再次，根據(jù)上述順序中每輛電動貨車的配送順序求解耗電量、剩余電量，根據(jù)剩余電量是否能支撐電動貨車到達下一個顧客點最近充電站為判定依據(jù)進行充電行為，充電量約束滿足式(11)，最高電量為充滿，最低電量為剛好到達下一充電站或配送中心。例如[0 1 2 11 3 0 4 5 6 0 7 12 8 9 0 10 0]，此順序中就表示第一輛與第三輛電動貨車需要在配送過程中充電，而此順序即為個體表示。最后，將個體存放至二維數(shù)組中，每一行代表一個個體。

3.2 聚 類

將n個個體進行分類，聚成m個類，分別計算每個個體的適應(yīng)度值并選出每一類的最優(yōu)個體作為聚類中心。此適應(yīng)度值為耗電量與顧客滿意度倒數(shù)之和，適應(yīng)度值最小者即為最優(yōu)個體。耗電量與顧客滿意度的求解方式見2.1節(jié)、2.2節(jié)。

3.3 產(chǎn)生新個體

如公式所示：XNEW=XSELECT+δ(μ，σ)，其中XNEW為新個體，XSELECT為選擇的個體，δ(μ，σ)為以μ為均值、σ為方差的高斯隨機函數(shù)。經(jīng)過一系列的變異、交叉操作，產(chǎn)生新個體。其中，用于新個體產(chǎn)生公式中的個體選擇操作參照圖1中的選擇過程。通過選擇條件P1、P2、P3、P4、P5來決定選擇對象，然后根據(jù)選擇的對象進行交叉、變異操作。該研究中的交叉操作采用兩點交叉、變異也采用兩點變異。兩點交叉即為通過選擇操作P5選擇的兩個對象作為交叉父本，通過設(shè)置兩個交叉點來進行交叉互換，然后通過映射消除重復(fù)位置的因素，最終得到交叉后的個體。例如，現(xiàn)有兩個選擇對象：[1 2 3 4 5 6]和[6 5 4 3 2 1]，交叉點為第3、第5個位置，那么保持交叉點中間位置不變其余位置互換得到：[6 5 3 4 5 1]和[1 2 4 3 2 6]，經(jīng)過映射消除得到：[6 2 3 4 5 1]和[1 5 4 3 2 6]，即為交叉后結(jié)果。而變異操作則通過對選擇操作P4選擇的對象進行兩點調(diào)換。例如，現(xiàn)有一選擇對象：[1 2 3 4 5 6]，變異點同樣為第3、第5個位置，經(jīng)過變異操作后為：[1 2 5 4 3 6]。

3.4 更新個體

將新個體與原個體相比較，保留適應(yīng)度值更好的個體。將每一代的最優(yōu)個體依次存在二維數(shù)組中，每一行代表此迭代的最優(yōu)結(jié)果。

3.5 輸出最優(yōu)解

當達到最大迭代次數(shù)后，輸出適應(yīng)度值最優(yōu)的個體。

4 算例分析

能耗公式中常數(shù)參數(shù)的取值由參考文獻[19-20]確定。圖2為應(yīng)用遺傳算法與頭腦風暴算法10顧客數(shù)，迭代100次的適應(yīng)度值收斂曲線。其中應(yīng)用頭腦風暴算法得到的收斂曲線相較于遺傳算法，適應(yīng)度值更小，收斂速度更快。具體數(shù)值如表1所示。整體來看，無論是采用遺傳算法還是頭腦風暴算法，在耗電量、顧客滿意度以及總目標值方面結(jié)果都相差不大，可見該模型的正確性與實用性。具體來看，采用遺傳算法的耗電量為286.61，比采用頭腦風暴算法的263.69多了22.92；而顧客滿意度的導(dǎo)數(shù)方面，采用遺傳算法的690.78要比頭腦風暴算法的724.58少33.8；也就是說采用頭腦風暴算法得到的最優(yōu)解，其耗電量要比遺傳算法少，顧客滿意度高。可見，該模型采用頭腦風暴算法相較于遺傳算法具有更好的收斂速度和收斂精度。

為了驗證頭腦風暴算法的可行性、有效性，文中引入了三個基準測試函數(shù)分別對兩種算法進行測試。測試結(jié)果如表2所示。通過表2可知，對3個基準測試函數(shù)的實驗中，頭腦風暴算法的各項結(jié)果都優(yōu)于遺傳算法，具有較好的適應(yīng)度值、平均值以及較小的標準差。這說明頭腦風暴算法具有較好的優(yōu)化精度和較強的魯棒性。由此，驗證了頭腦風暴算法的可行性、有效性。

圖2 適應(yīng)度值收斂曲線

表1 各算法具體適應(yīng)度值

表2 測試結(jié)果

結(jié)合對比結(jié)果可以得知，該模型能夠充分利用電動貨車電池容量、顧客時間窗的要求，從而達到降低電動貨車耗電量、充電量的效果，進而實現(xiàn)節(jié)省配送時間、提高顧客滿意度的要求。

5 結(jié)束語

探討了基于頭腦風暴算法的電動貨車路徑優(yōu)化問題，根據(jù)電動貨車的耗電量以及顧客滿意度提出了一種智能調(diào)度方法——EVRPTW模型。通過運用一種計算機智能調(diào)度算法——頭腦風暴算法，優(yōu)化配送中心電動貨車運營調(diào)度問題，從而制定出符合實際情況的運營調(diào)度方案。仿真實驗驗證了該方法的可行性，同時也驗證了頭腦風暴算法在解決此類問題上的可行性和有效性，進而驗證了提出的模型及算法能夠節(jié)省電動貨車耗電量，節(jié)省配送時間，提高顧客滿意度。但此類問題是在理想情況下進行研究的，忽視了實際問題中的許多隨機因素，比如排隊充電時間等，這些希望在之后的研究中加以解決。