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

康熙沛 楊家其 叢 喆 余 昊 向子權(quán)

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

0 引 言

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

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

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

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

1 問題描述與模型構(gòu)建

1.1 問題描述

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

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

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

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

1.2 數(shù)學(xué)建模

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

圖1 成本費率圖

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

(1)

目標(biāo)函數(shù)為

(2)

(3)

(4)

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

(5)

(6)

(7)

(8)

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

2 求解算法

2.1 灰狼算法

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

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

灰狼算法數(shù)字模型公式為

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為目前的迭代代數(shù).A和C為系數(shù)向量；a為收斂因子，隨著迭代次數(shù)從2線性減小到0；r1和r2的模取[0,1]之間的隨機數(shù).

ω狼根據(jù)α、β、δ狼的位置來更新其位置，以此來實現(xiàn)包圍獵物行為的數(shù)學(xué)公式為

(13)

(14)

(15)

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

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

2.2 離散灰狼算法

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

2.2.1SO、SS的應(yīng)用

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

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

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

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

c3×(Xδ-Xt)

(16)

Xt+1=Xt+D

(17)

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

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

程序流程圖見圖2.

圖2 算法流程圖

2.2.2編碼與解碼

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

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

假設(shè)有客戶{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進(jìn)行配送，其配送的順序為{0,2,3,1,4,0}.{5,6,7}子序列客戶貨物重量為3.9 t，分配給車輛2進(jìn)行配送，其配送順序為{0,5,6,7,0}.

3 算例分析

3.1 實驗設(shè)置

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

3.2 模型求解及分析

共進(jìn)行20組實驗，每種算法在參數(shù)不變的情況下，分別進(jìn)行10次實驗，得到的統(tǒng)計結(jié)果如表2.將每種算法的最好結(jié)果進(jìn)行記錄，成本成分見表3，優(yōu)化后的車輛路徑見圖3，收斂曲線對比見圖4.

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

表1 客戶信息表

表2 GWO和GA算法的統(tǒng)計結(jié)果表

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

圖3 車輛路徑圖

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

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

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

顯然，GWO算法求解VRPSTW問題有較大的優(yōu)勢，可以較好權(quán)衡時間窗成本和車輛行駛距離成本，尋得最優(yōu)解.配送路徑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 結(jié) 論

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

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

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