基于離散灰狼算法的帶軟時間窗車輛路徑規劃問題

康熙沛 楊家其 叢 喆 余 昊 向子權

(武漢理工大學交通與物流工程學院 武漢 430063)

0 引 言

帶軟時間窗的車輛路徑問題(vehicle routing problem with soft time window, VRPSTW)作為車輛路徑問題(vehicle routing problem, VRP)的衍生子問題，因其數學模型與現實問題相契合，被大量應用于生鮮配送、醫藥配送、便利連鎖店配送等物流配送場景中.

VRP問題已被證明為一個NP-hard問題[1]，傳統的精確算法只能解決小規模的VRP問題，而當VRP問題的規模較大時，精確算法無法求得最優解.因此，在面對大規模VRP問題時通常會采用啟發式算法進行求解.VRPSTW問題因其加入了軟時間窗的因素，使得目標函數不再是單一的追求路徑最短，而是同時要求軟時間窗的懲罰成本和與路徑相關的成本一同最小.這種多目標優化的需要對求解VRPSTW問題的啟發式算法提出了更高的要求.李丹蓮等[2]提出了多染色體遺傳算法來求解單車場多車型帶密集半軟時間窗問題，相比遺傳算法顯著減少了總配送成本.吳斌等[3]提出了一種新型混合算法，對客戶使用密度峰值聚類以縮減問題規模將聚類后的客戶用遺傳算法求解，實驗結果證得該算法具有高效性.石勇國等[4]針對帶軟時間窗車輛路徑問題提出了一種區域劃分與路徑優化的數學模型，結合最小支撐樹算法將客戶劃分出若干區域，使用貪婪算法將每個區域的路徑進行優化，取得了有效的結果.Ding等[5]使用改進的蟻群算法求解帶時間窗車輛路徑規劃問題.Vacic等[6]比較了退火算法、禁忌搜索、遺傳算法、混合遺傳算法求解VRP問題的能力，指出禁忌搜索和混合遺傳算法具有更優的求解能力.最后使用帶自適應變異概率的遺傳算法求解帶時間窗的車輛路徑規劃問題，該算法也被證明具有優秀求解能力.為了解決蟻群算法容易早熟和搜尋速度慢的問題，文中引入了自適應信息素和災難因子防止算法早熟，并且引入節約里程法和λ交換機制來提升搜尋速度.

文中采用一種新型啟發式算法——灰狼算法來求解VRPSTW問題.灰狼算法(grey wolf optimizer, GWO)是由Mirjalili等[7]受到灰狼種群狩獵過程啟發，提出來的一種群智能優化算法.該算法因為較好的求解效果、較強的收斂能力、參數少、容易實現等特點而得到廣泛的應用，但標準灰狼算法屬于數值型優化算法，大多用于求解連續域優化問題.而VRPSTW問題屬于離散的組合優化問題，標準灰狼算法無法對其直接使用.Sopto等[8]通過引入交換算子(swap operator, SO)、交換序列(swap sequence, SS)和局部搜索(partial search, PS)技術對原始灰狼算法進行改進，使灰狼算法可以求解旅行商問題(traveling salesman problem, TSP).通過將灰狼算法與其它啟發式算法，如蟻群算法、遺傳算法、生產者置換法進行對比，發現在大部分算例中灰狼算法求得的結果都更優.這在很大程度上證明了改進的離散灰狼算法在求解離散問題時具備更多優勢.

文中針對物流配送中對配送及時性的要求(如冷鏈配送，生產線物資配送等)，引入單位懲罰成本隨時間變化的時間窗，建立了以總配送成本最小為目標的車輛路徑規劃模型.通過合適的編解碼方案將離散灰狼算法從求解標準TSP問題拓展到求解VRPSTW問題，并通過與遺傳算法進行比較，驗證了離散灰狼算法求解VRPSTW問題的有效性.

1 問題描述與模型構建

1.1 問題描述

VRP問題是指在一個配送系統中，車輛從倉庫出發，需要將貨物送往多個客戶，為了滿足客戶配送需要，且使配送過程的代價函數最小，而對行車路線進行優化的問題.文中所研究的VRPSTW問題在傳統VRP問題中加入時間窗要素，求解過程中目標函數除了包含與行駛距離有關成本外還包含早于時間窗的等待成本以及晚于時間窗的延遲成本.

時間窗是指客戶對于接收貨物的時間有一個時間段，車輛需要在這個時間段內將貨物送達的要求，分為硬時間窗和軟時間窗兩種.硬時間窗是指車輛必須在規定的時間段內送達，超出時間段客戶不會接受貨物，這時是無效解；而軟時間窗指車輛不必在規定的時間段內送達，但是超出時間段會降低客戶滿意度并且會有懲罰成本.在實際問題中，由于硬時間窗約束條件往往會使優化問題不存在可行解域，故通常采用軟時間窗的方式.

VRPSTW指有一個倉庫，多個同一型號的車輛，負責給一組客戶進行配送.客戶對接收貨物有時間段要求.在本文中，車輛早于時間段到達客戶，會等待客戶接受服務而產生等待成本.當車輛晚于時間段到達客戶，會產生等待成本.需要盡量滿足客戶時間窗需求，同時合理規劃車輛路徑，使配送總成本最小.

本模型作如下假設：①倉庫有足夠的車輛完成所有客戶的配送；②車輛從倉庫出發，配送完若干客戶后需要返回倉庫；③單個客戶需要配送的貨物重量小于單車的載重量，并且一個客戶只能由一輛車配送.④所有客戶的位置、需求重量、時間窗已知.

1.2 數學建模

引入的軟時間窗的單位費用定義如下.設一個客戶的時間窗懲罰成本為pi.早于時間窗的單位費用最大值為c3，晚于時間窗的單位費用最大值為c4.隨時間變化的單位費用見圖1.

圖1 成本費率圖

當車輛在[0,ai]、[bi,+∞]區間抵達客戶，單位費用不變.當車輛在[ai,ei]、[li,bi]區間抵達客戶，單位費用成線性變化.當車輛在[ei,li]區間抵達客戶，單位費用為0.

(1)

目標函數為

(2)

(3)

(4)

i=0,k∈{1,2,…,K}

(5)

(6)

(7)

(8)

式為時間窗成本計算公式；式為配送成本最小的目標函數；式～約束每一個客戶只能由一輛車進行服務并且車輛僅訪問一次；式限制車輛只能從車場出發并返回車場，且消去最小回路；式為車輛的載重量約束公式；式為車輛離開客戶點的時間約束公式；式為車輛抵達客戶點的時間約束公式.

2 求解算法

2.1 灰狼算法

灰狼算法將狼群個體分為四種類型來模擬實際的灰狼種群社會階層.其中α、β、δ狼為精英狼，其權力依次下降，負責帶領狼群搜尋隊伍.而ω狼則為普通狼，跟隨精英狼協助捕獵.狩獵開始時，α、β、δ狼快速移動接近獵物，ω狼跟隨這三匹狼進行大范圍搜索，并逐漸包圍獵物，最后對獵物進行進攻狩獵.

基于上述描述可知，在現實中狼群可以有效對獵物進行定位、包圍并捕獲，這一過程通常由α狼主導，β狼和δ狼輔助完成.然而，在一個實際優化問題的解空間中，最優解(即獵物的位置)是未知的.因此，通過算法來描述灰狼的狩獵過程，通常會假定α、β、δ精英狼更靠近獵物，即在迭代過程中算法都將歷史前三的最優解分別選作α、β、δ精英狼，然后驅使其他ω狼(解)根據精英狼的位置不斷更新其自身位置，從而尋求最優解或近似最優解.

灰狼算法數字模型公式為

D=|C·Xp(t)-X(t)|

(9)

X(t+1)=Xp(t)-A·D

(10)

C=2r1

(11)

A=2ar2-a

(12)

式(9)為個體與獵物間的距離:Xp(t)為獵物的位置向量，X(t)為灰狼的位置向量.式(10)為灰狼的位置更新公式:t為目前的迭代代數.A和C為系數向量；a為收斂因子，隨著迭代次數從2線性減小到0；r1和r2的模取[0,1]之間的隨機數.

ω狼根據α、β、δ狼的位置來更新其位置，以此來實現包圍獵物行為的數學公式為

(13)

(14)

(15)

式(13)中:Dα、Dβ和Dδ分別為α、β、δ狼與其他個體間的距離;Xα、Xβ、Xδ為α、β、δ狼的位置，為ω或其他狼的位置.式(14)中:X1、X2、X3為ω或其他狼朝α、β、δ狼前進的步長和方向.式(15)中，通過將X1、X2、X3加權來確定該匹狼的最終位置.

在該公式中，A和C對于控制狼群狼群搜索和包圍獵物起到了非常重要的作用.A在數學上模擬了狼靠近目標和遠離目標的行為.當其模小于1時，灰狼靠近獵物，進行包圍或狩獵.當其模大于1時，灰狼遠離獵物，在全局范圍尋找更優解.向量C的模數值范圍是[0,2]，它的作用是為目標對移動的影響定義一個權重.以式(1)為例，當其模小于1時，目標對移動的影響會減弱，阻止灰狼快速接近目標，防止算法快速陷入局部最優.而當其模大于1時，目標對移動的影響增強，灰狼會快速接近目標，得到局部最優.

2.2 離散灰狼算法

文獻[8]將SO、SS引入到灰狼算法中，重新定義了灰狼算法的位置更新公式，利用改進后的離散灰狼算法求解TSP問題.文中引用SO和SS概念來修改灰狼算法，并針對VRPSTW問題設計整數型編解碼規則，最后應用修改后的灰狼算法求解VRPSTW問題.

2.2.1SO、SS的應用

SO(i,j)是交換算子，表示將一個序列中位于i和j位置的數進行交換.對于具體序列A=(1,2,3,4,5)，具體交換子SO(1,3)，有A+SO(1,3)=(3,2,1,4,5).其中“+”表示將SO(1,3)應用到序列A上，使得A位于1和3位置的數進行交換.

SS是交換序列，它是由多個SO組成的，SS可表示為(SO1,SO2,SO3,…,SOn).SS作用于序列，表示將組成SS的所有SO按順序應用到該序列.SS的常用法如下.要使特定的序列B=(2,1,4,3,5)經過SS的變換成為序列A=(1,2,3,4,5)，則可以產生SS=A-B=(SO(1,2),SO(3,4)).該SS表示將B中元素的位置交換以得到A.更詳細的關于SO、SS表述可以參考文獻[10-11].

通過引入SO和SS，灰狼算法的位置更新公式變化如下：

D=c1×(Xα-Xt)+c2×(Xβ-Xt)+

c3×(Xδ-Xt)

(16)

Xt+1=Xt+D

(17)

(Xα-Xt)作為交換序，表示離散空間中當前狼與α狼的距離.在離散問題的決策空間中，當前狼Xt經過(Xα-Xt)的變換可以成為Xα.(Xβ-Xt)與(Xδ-Xt)同理.c1是一個[0,1]的隨機變量，其代表著(Xα-Xt)以概率c1得到完全保留.c2、c3同理.式為更新t代狼位置的公式.

PS可以在一定程度上改善離散灰狼算法容易陷入局部最優的問題，并且可以加快收斂速度.PS技術表述為依次將SS中的SO作用于解S，并且每作用一次將當前解的適應度計算出來并記錄，最后得到的解是記錄的解中最優解.應用PS技術使得SS中只有部分SO作用于S，所以叫局部搜索技術.

程序流程圖見圖2.

圖2 算法流程圖

2.2.2編碼與解碼

文中定義的VRPSTW問題有N+1個位置點，記作{0,1,2,…,N}，其中0表示倉庫，{1,2,…,N}表示客戶.采用整數編碼的方式，將客戶的號碼按其配送順序組成序列，該序列為VRPSTW問題的一個解.

在解碼的過程中，一個序列包含多輛車的配送順序信息.根據車的載重量和客戶貨物重量對序列進行分割，分割后的每一段序列代表著一輛車的配送路徑.

假設有客戶{1,2,3,4,5,6,7}，每個客戶需求貨物的重量是1.3t，每輛車的載重量是6 t.則在解序列{2,3,1,4,5,6,7}中{2,3,1,4}子序列客戶貨物重量為5.2 t，分配給車輛1進行配送，其配送的順序為{0,2,3,1,4,0}.{5,6,7}子序列客戶貨物重量為3.9 t，分配給車輛2進行配送，其配送順序為{0,5,6,7,0}.

3 算例分析

3.1 實驗設置

該工廠的生產線配送問題中，有1個倉庫和16個生產線，集配中心有足夠車輛同時配送.每輛車的載重量為6t，行駛速度為28.8 km/h，行駛成本為5元/km，每輛車的啟用成本為100元.早于時間窗到達生產線的等待成本為210元/h，晚于時間窗到達生產線的延遲成本為300元/h.各生產線的物料需求量、坐標、時間窗、服務時間見表1.

3.2 模型求解及分析

共進行20組實驗，每種算法在參數不變的情況下，分別進行10次實驗，得到的統計結果如表2.將每種算法的最好結果進行記錄，成本成分見表3，優化后的車輛路徑見圖3，收斂曲線對比見圖4.

離散灰狼算法的種群大小為50，迭代次數為100.遺傳算法的種群大小為50，遺傳代數為100，交叉概率為0.2，變異概率為0.1.

表1 客戶信息表

表2 GWO和GA算法的統計結果表

表3 GWO和GA算法的成本成分表

圖3 車輛路徑圖

圖4 GWO和GA算法的收斂曲線對比圖

由表2可知：離散改進后的GWO算法相較于GA算法在除了計算時間的各項指標中都表現得更加優秀.GWO算法在具有尋優優勢的同時，還具有更好的算法穩健性.在本文15個客戶點規模下，GWO算法表現出的搜索能力明顯強于GA算法，并且平均6.54秒的計算時間在實際問題的求解中可以接受.

由圖3可知：GWO算法求得的路徑較為優秀，路徑大多成環狀，交叉較少.而GA算法求得的路徑較差，交叉較多，車輛迂回行駛的路徑較長.又由表3成本成分表可知：GWO解的時間窗成本比GA多，GWO解的距離成本比GA少.可以判斷GWO相比GA在增加了少量的時間窗成本代價下顯著降低了車輛行駛距離成本，這一判斷在圖3中互為印證.由圖4可知：GWO算法比GA算法收斂快，約在37次迭代就達到了收斂，而GA約在63次迭代才達到收斂.

顯然，GWO算法求解VRPSTW問題有較大的優勢，可以較好權衡時間窗成本和車輛行駛距離成本，尋得最優解.配送路徑1為11—13—14—15，車輛載重量利用率為95%.配送路徑2為7—4—5，車輛載重量利用率為81.6%.配送路徑3為2—3—1—12，車輛載重量利用率為80%.配送路徑4為6—10—9—8，車輛載重量利用率為90%.

4 結 論

1) 通過引入SS、SO的機制使標準灰狼算法離散化，進而可以求解VRPSTW問題.將離散灰狼算法與遺傳算法進行對比實驗，實驗結果證明了離散灰狼算法求解VRPSTW問題的有效性.并且結果還表明離散灰狼算法比遺傳算法搜索能力更強、收斂速度更快.

2) 離散灰狼算法通過引入SS、SO機制來處理離散解，并依據標準灰狼算法的理念重新定義灰狼位置更新公式，從而可將灰狼算法應用于離散、組合優化問題.為了解決引入SS、SO后產生的求解效率低、易陷入局部最優的問題，采用了PS技術.PS技術計算了離散空間中每個解接近最優解過程中每一次應用SO的適應度，以此搜尋更優的解，以增加計算量為代價，顯著增加了求解效率，一定程度上避免了局部最優解的問題.但是PS技術增加了大量計算，使得算法在求解大規模問題時耗時過長.未來的將會研究其他方式替換PS技術來改進離散灰狼算法.

3) 為了驗證離散灰狼算法在求解VRPSTW問題的有效性，在不失一般性的前提下，文中在數學建模中定義了若干假設，使得數學模型更清晰直觀.在下一步研究中，會基于實際應用場景來松弛假設條件，定義帶有多維特質約束條件的VRPSTW問題，使得建立的數學模型具有更高的現實意義.同時，還會展開灰狼算法求解多車場路徑優化模型的研究.