基于混合煙花算法的兩級車輛路徑優化研究

熊國文 張 敏,2 張訓杰 張則強,2

1(西南交通大學機械工程學院 四川 成都 610031)

2(西南交通大學軌道交通運維技術與裝備四川省重點實驗室 四川 成都 610031)

0 引 言

城市交通機動車數量增加、道路狀況、環境變化等因素,往往會引起車輛行駛緩慢,進而造成交通擁堵[1-3]。而影響交通擁堵的因素隨著時間和空間的改變而動態變化,即在不同時段,同一路段車輛速度不一定相同;在同一時段,不同路段車輛速度也不一定相同[4]。動態交通狀態導致物流配送體系存在諸多不確定因素[5]。如遇到交通狀態惡劣,會直接影響物流配送的效率,進而超出客戶時間窗,造成延時配送、成本增加、客戶滿意度下降等問題。因此,如何根據動態交通狀態規劃高效的物流配送車輛路徑,是物流企業亟待解決的問題。

基于動態交通狀態的物流配送車輛路徑問題是車輛路徑問題的延伸,旨在動態的交通狀態下規劃出最佳的物流配送方案。其中如道路條件、交通流量、意外事故、天氣情況等動態交通信息,對動態車輛路徑問題的解決起著非常重要的作用[6]。近年來,隨著通信和信息技術發展,動態交通信息可通過相應的平臺快速有效地獲取和處理[7],為研究動態車輛路徑規劃提供了先決條件。如Xiao等[8]認為車輛行駛速度主要由交通和路況決定,首先從相關信息系統獲得交通數據計算車輛在各路段的平均速度,在此基礎上建立以溫室氣體排放量最小為目標函數的混合整數規劃模型。針對動態交通影響物流配送效率,進而超出客戶時間窗,Ghani等[9]研究了交通擁擠導致不必要的時間延誤,從而造成客戶損失。同時,相關學者研究了動態交通物流配送車輛的異構問題,即不同的車輛載重能力、行駛里程等約束不同,如張傳琪等[10]將路網擁擠狀態沿時間軸展開,構建了考慮服務途中動態擁擠的多車型車輛路徑模型,設計了求解該模型的改進遺傳算法。上述文獻皆對動態交通狀態下的車輛路徑問題進行了研究并取得了可喜的成果,但未考慮客戶之間可能存在多條連通路線以及計算車輛在各個路段上的理論行駛時間可能與實際行駛時間相差較大等問題?；诖?李順勇等[11]針對城市路網中的兩節點之間具有多條連通道路的特性研究動態車輛路徑規劃問題,建立了多通路時變網絡下的低碳車輛路徑優化模型。Alinaghian等[12]通過考慮車輛裝載量、速度、道路梯度和城市交通等因素,分析了多路徑選擇對時變車輛路徑問題的重要性,提出了一種基于高斯螢火蟲算法的改進算法,以找到油耗最小的最優路徑。

目前,大多數學者的研究主要集中在單級物流配送車輛路徑優化上,但在實際物流配送中,為了避免大型車進入城市造成污染,很多城市采取車輛限行政策,兩級物流配送模式廣泛應用于各種場景下的商品配送[13-14],即商品先由大型車運輸至各個中轉站,再由小型車運輸至該中轉站所服務的各個需求點[15-17]。若兩級物流配送車輛路徑的優化仍然采用優化單級物流配送車輛路徑的方法,自上而下優化每一級物流配送車輛路徑,則無法實現兩級物流配送車輛路徑的整體優化。近年來,越來越多的學者開始從事兩級車輛路徑問題(Two-echelon Vehicle Routing Problem,2e-VRP)的研究。曾正洋等[18]先將貨物從中心倉庫配送至城市外圍的中轉站,再轉運至需求點,同時,考慮到將部分或全部運輸任務分配給第三方物流公司,第一級車輛在完成配送任務后無須返回中心倉庫,或者必須原路返回,構建了開閉混合式兩級車輛路徑問題的數學模型。張漢鵬等[19]研究應急物資配送中的兩級車輛路徑決策策略與應急物資配送績效問題。但兩級車輛路徑問題的研究中較少考慮關于物流節點之間有多條連通路線、動態的交通等現實物流配送情況。

自兩級車輛路徑提出以來,學者和專家提出了不同的求解算法。Wang等[20]針對具有隨機需求的兩級容量車輛路徑問題,提出了一種基于遺傳算法新的求解方法。Li等[21]考慮碳排放量,研究兩級長途運輸系統中的車輛路徑優化問題,提出了一種改進的局部搜索階段的Clarke和Wright節約啟發式算法(CW),有效降低二氧化碳的排放量。Hemmelmayr等[22]針對兩級車輛路徑問題和位置路徑問題,提出了一種自適應大鄰域搜索啟發式算法。胡喬宇等[23]研究了客戶需求隨機的兩級車輛路徑問題,設計了一種基于蒙特卡洛仿真優化方法,將仿真過程嵌入到啟發式算法的鄰域搜索過程進行求解。Belgin等[24]研究了兩級同時取送車輛路徑問題,提出了一種基于變鄰域下降和局部搜索的混合啟發式算法。由于兩級車輛路徑屬于NP-hard問題,求解比較復雜,難以同時確保求解速度和求解質量。為了解決此問題,本文結合煙花算法和遺傳算法各自的優點,提出一種混合煙花算法,以提高收斂速度、降低迭代次數達到同時確保求解速度和求解質量。

鑒于上述有關兩級動態物流配送車輛路徑以及求解方法研究的不足,結合物流配送的實際情況,從車流量大小、道路施工情況、天氣惡劣程度等動態交通因素分析對車速的實時影響,以車輛載重為約束條件,同時考慮客戶時間窗,配送時間超出客戶時間窗則產生懲罰成本,建立以物流配送總成本最小為優化目標的兩級動態物流配送車輛路徑優化模型。針對煙花算法收斂速度慢的缺陷,用插入法生成較優的初始種群,引入交叉操作提出一種新的混合煙花算法。通過計算兩級車輛路徑問題標準算例,與遺傳算法和現有文獻運算結果作對比,驗證了算法的有效性和高效性。

1 問題與建模

1.1 問題描述與假設

兩級物流配送系統包括一個配送中心、若干中轉站和若干客戶,兩級物流配送的網絡結構如圖1所示,D點代表配送中心,S點代表中轉站,C點代表客戶點?？蛻羲枭唐肥紫扔纱笮蛙噺呐渌椭行倪\輸至各個中轉站,然后由小型車將商品從中轉站運輸至各個需求點,要求其配送總時間在客戶能接受的范圍內,否則會產生較大的懲罰成本。其中大型車配送階段稱為第一級物流配送,由于中轉站的需求可能大于車輛容量,因此,第一級物流配送屬于需求可拆分配送,如圖1中實線箭頭所示;小型車配送階段稱為第二級物流配送,此階段需求不可拆分配送,如圖1中虛線箭頭所示。為進一步切合實際物流配送,本文考慮動態交通對物流配送的影響,以及各個節點之間有多條交通狀態不一致的連通道路,使該問題更加符合實際物流配送。

圖1 2e-VRP網絡結構

綜合考慮帶時間窗的兩級動態物流配送特點,做出如下假設：(1) 每條配送線路上的客戶需求量之和不能超過配送車輛的最大載重量Q1和Q2;(2) 第一級中轉站貨物可拆分配送,第二級需求點貨物不可拆分配送,每級物流配送使用同一種車型;(3) 每個客戶的需求數量必須得到滿足且只能由一輛車配送;(4) 每輛車從配送中心或中轉站出發,完成配送任務后返回到相應的配送中心或中轉站;(5) 每項配送任務必須在客戶要求的時間范圍內完成,否則就會產生高昂的懲罰費用;(6) 車輛一旦確認了所服務的客戶之后便不能再更改。

1.2 符號說明

根據以上假設,構建混合整數規劃模型,設定模型參數與決策變量。

D：配送中心集合;

S：中轉站集合;

P：需求點集合;

C：總成本;

c1：一級車輛單位距離運輸成本;

c2：二級車輛單位距離運輸成本;

c3：時間懲罰成本;

dij：節點i到節點j之間的距離;

Q1：一級車輛最大載重;

Q2：二級車輛最大載重;

U：一級車輛集合;

K：二級車輛集合;

qi：需求點i的需求量;

v1：一級車輛最大行駛速度;

v2：二級車輛最大行駛速度;

v1ij：一級車輛從節點i到節點j的實際速度;

M：一個足夠大的數;

Ti：客戶i能接受的最長配送時間;

es：中轉站s的需求量;

Tsu：一級車輛u達到中轉站s的時間;

Tik：二級車輛k達到需求點i的時間;

ti：到達客戶i的時間;

Zsu：一級車輛u給中轉站s的運輸量;

riju：一級車輛u訪問中轉站i后訪問j,riju∈{0,1};

xijk：二級車輛k訪問需求點i后訪問j,xijk∈{0,1};

yik：需求點i的需求量由二級車輛k配送,yik∈{0,1}。

1.3 數學模型

用具有代表性的車流量指數、天氣惡劣指數、道路施工指數刻畫交通狀態,參數α1ij表示節點i到節點j的車流量指數,α2ij表示節點i到節點j的天氣惡劣指數,α3ij表示節點i到節點j的道路施工指數。一級與二級車輛從節點i到節點j的實際速度由式(1)和式(2)求得。

v1ij=α1ij×α2ij×α3ij×v1

(1)

v2ij=α1ij×α2ij×α3ij×v2

(2)

一級物流配送車輛路徑成本設為f1,則：

(3)

二級物流配送車輛路徑成本設為f2,則：

(4)

配送延時懲罰成本設為f3,則：

(5)

目標函數：minC=λ1f1+λ2f2+λ3f3

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

tiu+dis/v1is+M×(1-risu)≥tsui∈D∪S,s∈S,u∈U

(17)

tiu+dis/v1is-M×(1-risu)≤tsui∈D∪S,s∈S,u∈U

(18)

tik+dij/v2ij+max(tsu)+M×(1-xijk)≥tju

s∈S,i∈S∪P,j∈P,k∈K

(19)

tik+dij/v2ij+max(tsu)-M×(1-xijk)≤tju

s∈S,i∈S∪P,j∈P,k∈K

(20)

ti=maxtik

(21)

上述模型中式(6)為目標函數,式(7)表示一級車輛不能超載;式(8)表示二級車輛不能超載;式(9-10)表示一級車輛路徑連貫;式(11)和式(12)表示每個需求點由一輛二級車服務一次;式(13)保證中轉站的需求量配送完成,式(14)表示每輛車從配送中心出發,經過若干需求點后回到配送中心;式(15)表示每輛車從中轉站出發,經過若干需求點后回到出發的中轉站;式(16)求出中轉的貨物需求量;式(17)-式(21)求貨物到達需求點的時間。

2 算法設計

2.1 解的編碼

本文采用實數編碼,以多行序列形式表示上述問題的解,如圖2所示,正方形代表配送中心,三角形代表中轉站,圓形代表需求點。圖2中解的含義是：配送中心需要兩輛一級車為兩個中轉站配送貨物,其路線是D-S1-S2-D和D-S2-D;中轉站1需要兩輛二級車為5個需求點配送貨物,其路徑是S1-8-5-S1和S1-3-7-6-S1;中轉站2需要一輛二級車為三個需求點配送貨物,其路徑是：S2-2-1-4-S2。

圖2 解的表示方法

2.2 插入算法

插入算法由Mole等提出[25],該算法的基本思想是將需求點依次插入到車輛中,每插入一個需求點都使得總成本增量最小,以此生成較好的解。為了增加初始種群的多樣性,本文從需求點所有可插入的位置中,挑選成本增量較小的幾個位置以概率Pi選擇其中一個位置插入需求點。Pi由式(22)計算,其中：Cost_add(i)代表的是第i個位置的成本增量;I代表位置集合,為了避免選擇成本增量較大的位置,對位置集合I設了限制條件,即當需求點可插入位置數量小于a時,位置集合I就是所有需求點可插入的位置集合,否則,位置集合I指成本增量從小到大的前a個對應位置集合,a的值可視情況而定,a越大,則初始解的多樣性越好,但初始解的質量可能也會下降。

(22)

具體步驟如下：首先新建車輛,選擇待插入的需求點,判斷是否需要新建車輛,若需要則新建車輛,否則選擇使得成本增量盡可能小的位置插入需求點,判斷需求點是否插入完畢,沒有則繼續選擇待插入的需求點繼續插入,需求點插入完畢則生成個體。插入算法偽代碼如下：

1V=[V1=[],V1_weight=0],k=2

2 fori=1：n

3point=Pi

4 ifVi_weight+q[point]>Q,i∈[1,2,…,k-1]

5V=[Vk=[],Vk_weight=0],k=k+1

6 forj=1：i×(k-1)

7cost_add(j)=0

8cost_add(j)=cost(V[j],point)+

cost(V[j+1],point)-cost(V[j],V[j-1])

9l=select(cost_add)

10m=vehicle(l)

11V=insert(l,point),

Vm_weight=Vm_weight+q[point]

12 Return個體

在上述偽代碼中,V代表車輛集合,其中Vk代表的是第k輛車所服務的客戶順序,Vk_weight是第k輛車的載貨量;P代表的是客戶點集合,Cost_add(j)代表的是第j個位置的成本增量,Cost(V(j),Point)則是代表第j個位置對應的客戶點Vh(j)與Point之間的成本,Select(Cost_add)選擇成本增量盡可能小對應的插入位置,vehicle(l)代表位置l所在車輛,insert(l,Point)將客戶點Point插入到第l個位置。經過插入算法可以得到總配送成本盡可能小的初始種群,同時,由于選擇插入的位置不一定是成本增量最小的位置,使得初始種群多樣化。

2.3 爆炸操作

首先通過式(23)計算煙花個體爆炸的火花數,然后針對個體的每輛車采用爆炸操作產生火花,爆炸操作如圖3所示,隨機選擇兩個位置,交換其對應位置的需求點編號,計算出爆炸后新車輛的配送費用,用配送費用最小的新車輛代替原來的車輛。

圖3 爆炸過程

(23)

式中：Si為第i個個體產生的火花數;m是最大火花數量;F(i)是第i個個體的適應度值;Fmax=max{F(i)};ε為一個極小的常數,避免分母為零。同時,為了限制火花數量過多或過少,設定如下的產生火花數量的限制公式：

(24)

式中：round()為取整函數;a和b為給定的常數。

2.4 車輛交叉

首先求出群體最優解,然后用群體最優解中車輛的某一段需求點序列代替個體中的某一段相同長度的需求點序列,最后將重復的需求點刪除,并且將沒有被服務的需求點用插入算法重新插入到車輛中,形成新的可行解。車輛交叉操作如圖4所示。

圖4 交叉操作

2.5 算法流程

本文所提混合煙花算法,融入了插入法和交叉操作,保證了算法的全局搜索與快速收斂性能,首先采用插入算法生成較好的初始種群;其次計算適應度值并找出最優初始解;然后引入遺傳算法中的交叉算子,使得煙花個體與最優煙花個體執行交叉操作;再利用煙花算法的爆炸算子產生爆炸火花,提高算法的尋優能力;最后采用精英策略保留較好的煙花個體進入下一次迭代。HFWA流程如圖5所示,其中Gen為迭代次數。

圖5 算法流程

3 算法驗證

本文使用2e-VRP標準算例對本文提出的HFWA進行可行性驗證,標準算例以車輛行駛路徑最短和使用車輛數最小為目標函數,車輛載重等為約束條件。標準算例數據來源于https：//www.univie.ac.at/prolog/research/TwoEVRP/。并將HFWA計算結果與官網給出的最優結果、GA、Marinelli[26]和Jie等[27]求解結果進行比較。其計算結果為使用Inter(R) Core(TM)i3-6100CPU@3.70 GHz處理器,仿真軟件采用MATLAB 2010b。兩種算法的種群規模都設置為200,HFWA迭代次數為50,GA迭代次數為500,計算10次的平均結果見表1。

對比表1中27個標準算例解的質量可見,GA僅能求出10個標準算例的最優解,其余結果與最優解相差較大。而HFWA有24個標準算例均能求出最優解,其余3個算例與現有最優解也相差較少。對比求解效率可見,由于HFWA使用了插入算法,設計較為復雜,提高了收斂速度,以降低迭代次數為代價提高求解效率,相較于GA在求解效率上快了1倍。而相較于文獻[26]和文獻[27]在求解質量與效率上同樣具有優勢。綜上,證明了HFWA的可行性與良好的求解性能。

4 實 驗

本文在標準算例(Set2a_E_n33_k4_s1_9)的實驗數據基礎上,通過隨機生成客戶點的時間窗演化為本文的實驗數據(見表2)。隨機生成了各個路段在各時刻的車流量指數、天氣惡劣指數、道路施工指數(如表3所示,由于數據量太大,表3中僅僅列出前五個客戶路段之間在某時刻的刻畫交通狀態的各項指數)。若某兩個客戶點之間的交通狀態比較惡劣,從而使得物流配送成本急劇上漲,則會重新選擇一條交通狀況較好,路徑不劇增的新路線,使得物流配送總成本變化幅度較小。

表2 實驗數據

表3 交通狀態指數

在表2中序號1至序號32為需要服務的客戶點,客戶點1和9被選擇為中轉站,為方便編碼,將中轉重新設置為33和34,35為配送中心。一級配送網絡中使用載重量為20 000的大型車,二級配送網絡中使用載重量為8 000的小型車。

為了說明在優化物流配送時,考慮交通狀態的必要性,本文將不考慮交通狀態條件下優化的車輛路徑代入交通狀態條件下得到的結果,與考慮交通狀態下的優化結果進行對比分析。其車輛單位距離成本設置為1,延時懲罰成本設置為2,算法參數與求解標準算例一致。計算結果見表4,HFWA和GA優化后的兩級車輛路徑見圖6至圖9,其中實線表示第一級車輛路徑,虛線表示第二級車輛路徑。

表4 實驗計算結果

圖6 HFWA不考慮交通狀態的兩級車輛路徑

圖7 HFWA考慮交通狀態的兩級車輛路徑

圖8 GA不考慮交通狀態的兩級車輛路徑

圖9 GA考慮交通狀態的兩級車輛路徑

從表4中可以得出,HFWA考慮交通狀態下的優化結果,在靜態交通下比不考慮交通狀態條件優化結果代入到考慮交通狀態后得到的總成本減少了17.8%,在動態交通狀態下減少了10.5%,總成本平均減少了14.2%,說明了優化物流配送時考慮交通條件的必要性。而GA優化性能相較于HFWA相對較差。同時,考慮了交通狀態在運輸總成本、路徑成本、延時成本相較于不考慮交通狀態都有所增加,動態交通相較于靜態交通,各個成本也有所變化,這是因為在物流配送過程中,交通狀態變惡劣、不同道路交通狀態在不同時刻不一致、物流節點間的路徑選擇策略緣故,使得車輛速度緩慢,車輛路徑增加,配送時間延長,客戶滿意度下降。靜態路徑成本和動態路徑成本不同則說明了在貨物裝車后的實際配送過程中,因交通狀態的時刻變化,雖然車輛所服務的客戶不再改變,但所行走的路線卻根據動態交通狀態做出了相應的變化以降低配送成本。從圖6到圖9也可以看出是否考慮交通對車輛路徑也有所影響。在不考慮交通狀態條件下,雖然對于延時配送成本,HFWA求解結果略高于GA求解結果,但是對于總成本以及路徑成本,HFWA求解結果都遠遠低于GA求解結果。

由于車流量和道路施工情況在每個需求點之間不同,分析比較困難,而天氣狀態在一段時間內,各個需求點之間都相差有限。為了研究交通狀態的影響因素對二級物流配送成本的影響,本文首先隨機生成各個需求點之間的各個時刻的車流量指數和道路施工指數,將其固定不變,以天氣狀態指數為變量分析天氣狀態對配送成本、車輛行駛路徑和延時懲罰成本情況的影響,分析計算結果如圖10、圖11和圖12所示。

圖11 天氣情況對車輛行駛路徑的影響

圖12 天氣情況對延時配送成本的影響

分析圖10、圖11、圖12可知,在車流量指數和道路施工指數已知不變的情況下,運輸總成本和延時配送成本隨著天氣的好轉而降低,車輛行駛路徑的長度總體上也隨著天氣的好轉而縮短。在實際中,除了天氣,考慮車流量以及道路施工等影響因素會更加符合實際物流配送,說明本文研究交通狀態對運輸成本的影響符合實際物流配送過程,可以在動態交通狀態下有效降低物流配送成本,具有實際的應用價值,為動態二級物流配送路徑優化提供了新思路。

5 結 語

本文考慮了車流量、道路施工和天氣狀態對交通狀態的影響,將動態的交通狀態和時間窗同時引入到兩級物流配送中,建立了帶時間窗的動態兩級物流配送車輛路徑優化數學模型,設計了求解該復雜問題的混合煙花算法。并利用混合煙花算法和遺傳算法計算2e-VRP標準算例,并與現有文獻所提算法對比說明本文算法的可行性和高效性。在標準算例的基礎上構造新的具有時間窗的實驗數據,然后用兩種算法計算帶時間窗的動態兩級物流配送車輛路徑規劃數學模型,結果表明混合煙花算法收斂速度快,迭代次數少,且求解質量和求解效率均優于遺傳算法。最后,分析了交通狀態的影響因素對車輛路徑以及配送成本的影響;證明了在實際物流配送車輛路徑規劃過程中,考慮動態交通的優化結果更加符合實際物流配送過程,具有實際應用價值,且算法設計合理,為求解動態交通的兩級物流配送車輛路徑問題提供了新方法。

本文僅僅考慮了一部分影響交通狀態的因素,在實際的物流配送過程中,還存在車輛限行政策、客戶需求的動態變化等因素,這值得在后續的研究中進一步探討。