不確定環(huán)境下車輛配送路徑魯棒優(yōu)化及求解算法*

趙 瀟，夏緒輝，王 蕾，曹建華

(1.武漢科技大學 機械傳動與制造工程湖北省重點實驗室，武漢 430081；2.湖北文理學院 機械工程學院，湖北 襄陽 441053)

0 引言

車輛配送路徑規(guī)劃是供應鏈及物流、生產制造運作管理領域的基本問題，它對于提高物料流轉效率起著至關重要的作用。因此，自車輛路徑問題提出以來便受到國內外學者的廣泛關注，時至今日仍然是該領域的熱點問題之一[1-3]。其中，難點主要體現(xiàn)在兩個方面。一是由于客觀環(huán)境的不確定性，需求以及交通運輸相關情況往往多變，由此可能導致當前方案的可行性降低，進而造成總體成本的增加或效率的降低；二是車輛路徑規(guī)劃問題一般屬于NP-Hard問題，其求解效率隨著問題規(guī)模的增加呈指數(shù)式驟然下降。配送路徑優(yōu)化是決定整個系統(tǒng)運作效率與成本的關鍵之一[4]。

目前，針對該類問題的研究已有大量研究成果[5]。但是，在不確定環(huán)境下，多數(shù)研究成果均是在隨機規(guī)劃與動態(tài)規(guī)劃框架下完成[6]。在隨機規(guī)劃下，車輛路徑問題中的隨機因素，如客戶需求或道路通行時間，通常被看作是服從某已知概率分布的隨機事件。但是在現(xiàn)實條件下，不確定因素往往不會嚴格服務某一分布，而且，要準確獲得或求出該概率分布信息基本難以實現(xiàn)。在動態(tài)規(guī)劃框架下，按照配送階段或路徑路段可將運輸問題劃分為多個階段，基于此可構建面向車輛路徑問題的動態(tài)規(guī)劃模型。該方面雖然直觀易懂，但是，動態(tài)規(guī)劃算法由于其天生存在的維數(shù)災難問題使得其難以處理大規(guī)模的優(yōu)化問題。因此，動態(tài)規(guī)劃下的車輛路徑問題其有效性也具有一定局限性。

針對上述兩個難題，本文將研究在不確定環(huán)境下，特別是當需求信息或運輸時間等不確定因素相關數(shù)據無法完全獲知時，如何合理規(guī)劃車輛配送路徑，以實現(xiàn)運輸成本的最小化這一為基本目標，同時控制配送或回收貨物的延遲率，進而提高配送方案在不確定環(huán)境下的運作效率。

1 問題描述與模型構建

1.1 問題描述

為了模型構建的科學性和有效性，本文做出如下假設：

(1) 每一個需求點只能被一輛配送車輛所服務；

(2) 上游具備的庫存總量可以滿足下游所有客戶的需求；

(3) 不考慮物資在配送中心以及運輸過程中的裝卸貨時間；

(4) 物資運輸?shù)膯挝毁M用和配送中心的存儲費用都是已知的；

(5) 產品的生產量都是已知的；

(6) 從供應商到配送中心以及配送中心到需求點的距離都是已知的。

假設當前在某一網絡包含{1,…,n}需求點，其組成集合V={1,…,n}。假設任意兩點之間的單位配送費用為cij，通行時間為tij，每個點的配送需求為di，且當前共有K輛具有相同運輸能力C的運輸車輛。在此，對于每一個車輛的配送任務而言，其可允許的總的配送時間上限假設為L，即如果假設每一輛車在初始時刻出發(fā)，那么它應在L時間到達最后一個目的地。通過L可反映不同配送需求點在時間上的要求。當車輛到達時間超出L時，還將接受βk的單位懲罰成本。

在上述背景下，要求完成所有配送需求的總成本最低。為此，涉及到的決策變量如下所示：

uki:車輛k服務完i點后剩余的物資數(shù)量或搭載能力，

wki:車輛到達最后需求點的時間。

1.2 魯棒優(yōu)化模型

現(xiàn)實條件下，由于外部環(huán)境的復雜性，獲得關鍵參數(shù)(如需求或行程時間)的精確取值或者準確的概率分布往往是極其困難甚至是不可能的。由此可能導致基于傳統(tǒng)模型得到的路徑規(guī)劃方案在現(xiàn)實中的可行性較低，甚至失效，即上述模型得到的方案在不確定環(huán)境下的魯棒性較低。為此，本部分將研究對應的魯棒優(yōu)化模型，以提高在不能得到需求或行程時間準確值時的方案可行性。魯棒優(yōu)化是當前實現(xiàn)上述目標的主要方法之一，基于當前國內外相關研究成果[7-8]，本文將構建面向配送車輛路徑規(guī)劃的魯棒優(yōu)化模型。

假設各個配送點的需求是相互獨立的，當不確定因素未知時，可假定其屬于某一不確定集合。具體地，不確定因素有各配送點需求di和兩點之間行程時間tij(不失一般性，假設任意車輛在任意相同兩點之間的行程時間相同)，那么定義不確定集合U={Ud,Ut}，以及

(1)

(2)

Y3={y∈Rs|yTQy≤1}；

特別地，當Z滿足以下條件時，不確定集合Ut分別可構成凸包集合、箱型集合及橢圓形集合等。

Z3={z∈Rs|zTQz≤1}。

基于上述定義，便可得到在不確定需求或行程時間參數(shù)下的配送車輛路徑規(guī)劃魯棒優(yōu)化模型(Robust Delivery Vehicle Routing Problem，RDVRP)。

(3)

(4)

(5)

(6)

(7)

(8)

(9)

ukj-uki+C(1-xkij)≥dj,?k∈K,i,j∈V,d∈Ud

(10)

di≤uki≤C,?i∈V,d∈Ud

(11)

xkij∈{0,1},?(i,j)∈V,k∈K,

(12)

wk,uki≥0,?k∈K

(13)

(14)

(15)

目標函數(shù)1旨在最小化總成本，包含所有車輛的運輸配送成本以及懲罰成本，其中(wk-L)+={wk-L,0}。約束條件4和5保證每個需求點都被服務一次。約束條件6保證運輸網絡內的流量平衡，即在任意需求點，車輛進出守恒。約束條件7表示每一輛車都從車輛或配送中心出發(fā)。約束條件8表示任意車輛的服務路徑不存在子回路。約束條件9表示當車輛到達時間超出L時，還將接受βk的單位懲罰成本，其中同時時間信息無法準確獲取，但屬于由約束15定義的不確定集合。約束條件10和11保證車輛剩余的貨物或搭載能力必須滿足該需求點的需要，且該需求信息無法準確獲取，但屬于由約束14定義的不確定集合。約束條件12到13是對決策變量的限制。

基于現(xiàn)有研究成果，模型RDVRP都為0～1混合整數(shù)線性規(guī)劃問題。為保證路徑規(guī)劃方案的魯棒性，可取模型RDVRP的魯棒對應模型，即考慮在最壞情形下的不確定因素取值，此時，約束9以及10和11可改寫為：

(16)

(17)

(18)

基于此，得到的優(yōu)化模型便可計算在最大配送需求以及最長行程時間下的規(guī)劃方案，因此該方案在不確定環(huán)境下具備較高的魯棒性。

2 面向大規(guī)模配送問題的免疫遺傳算法

配送車輛路徑優(yōu)化問題屬于NP-Hard問題，雖然模型RDVRP可通過現(xiàn)有一些軟件直接求解，如Cplex等，但是面對大規(guī)模決策問題時，這些軟件求解效率往往較低[5]。為此，本部分將研究具有較高求解效率的啟發(fā)式算法，以提高魯棒優(yōu)化模型的可行性。

免疫遺傳算法(Immune genetic algorithm, IGA)是免疫算法和遺傳算法的結合體[9-10]。免疫遺傳算法主要包含7個模塊：抗原識別，初始抗體產生，抗體適應度評估，記憶細胞分化，抗體促進和抑制，抗體生產和種群更新。目標函數(shù)被看著抗原，而候選解被看做抗體。可行解與最優(yōu)解間的近似程度是用抗原和抗體間的相關關系來描述的，抗體差異化的計算是保持種群多樣化的一種基本手段。

(1)初始抗體編碼

在基本遺傳算法和免疫遺傳算法中，抗體都需要通過編碼來表示基因型，編碼方法通常包括二進制編碼、實數(shù)編碼等。一般來說，二進制編碼比實數(shù)編碼具有更強的搜索能力，但實數(shù)編碼在變異操作中可以保持更好的種群多樣性，并且不需要解碼，可以有效地提高算法的精度和運算速度。因此，在本文配送車輛路徑優(yōu)化問題研究中，實數(shù)編碼方法將被用來對抗體進行編碼。設置初始變化區(qū)間[m(i),n(i)]，φ(i)表示第i個決策變量在區(qū)間[0，1]中對應的實數(shù)，g(i)表示基因。初始變化區(qū)間和實數(shù)區(qū)間滿足線性變化關系，

φ(i)=m(i)+g(i)(n(i)-m(i))。

通過匹配初始區(qū)間和實數(shù)區(qū)間，可以獲得一系列基因，并且這些基因按順序同問題解決方案(g(1),g(2),g(3),...,g(p))的編碼相關聯(lián)。

(2)多樣性評估

為了有效地克服算法過早收斂的弊端，基于近似向量距離的個體選擇概率方法將被運用到本文。抗原、細胞B和抗體分別表示目標函數(shù)、最優(yōu)解ki和候選解。第M個抗體由非空免疫系統(tǒng)集K和抗體在集合K上的距離組成，其中抗體的向量距離：

(19)

依據公式(19)，抗體密度為：

(20)

因此，個體選擇概率可以表達為：

(21)

集合K中相似抗體數(shù)量越多，抗體i被選中的可能性越低。反之，集合K中同抗體i基因相似的抗體數(shù)越少，抗體i被選中的可能性越高。這種選擇概率使得具有有效進化基因的低適應性個體能夠獲得生殖(再生)的機會。然而，這種個體選擇的概率只同每一個抗體的適應度相關，沒有考慮個體抗體之間的編碼相似性。因此，歐幾里得距離將被引用以應對這一問題?？贵wφ1,φ2,φ3,...,φn和φ1,φ2,φ3,...,φn間的歐幾里得距離可以定義為：

(22)

歐幾里得距離越大，2個抗體之間的相似度越低；d=0表示2個抗體是相同的。在引入歐幾里得距離后，抗體密度的選擇概率可以表示為如下：

(23)

(3)免疫操作

在選擇操作過程中，以P值作為選擇概率進行抗體群體的選擇，并且輪盤賭法被用來確保好的個體可以繼承到下一代。

變異操作是指在一個或多個位點上以一定的概率改變基因的值。變異本身是一種局部隨機搜索機制，與選擇算子相結合的它可以保證免疫遺傳算法的有效性。本文算法將隨機選擇一組個體進行變異操作以產生更好的個體：

Mi,G=Xi,G+H(Xr1,G-Xr2,G)

(24)

其中，Xi,G是從優(yōu)秀個體集里隨機選擇的個體。Xr1,G和Xr2,G是從當前種群中隨機選擇的個體。Mi,G是變異操作后生成的染色體。H是調整因子，其迭代公式如下：

(25)

randk，k={1,2}，服從[0,1]均勻分布。θ1是一個固定參數(shù)，表示調整后的控制參數(shù)的概率。Hu,G和Hl,G都是固定參數(shù)，分別代表控制參數(shù)H的上下界。Hi,G和Hi,G+1表示第i個個體變異過程中的調整因子。

綜上所述，免疫遺傳算法的步驟如圖1所示。

圖1 算法流程圖

3 案例分析

3.1 案例背景

企業(yè)A是本地的大型連鎖超市，其主要業(yè)務是向本地區(qū)分銷配送某些商品。然而，隨著配送業(yè)務量的擴大，配送成本逐漸增加，延遲配送現(xiàn)象時有發(fā)生。因此，有必要研究配送車輛的配送網絡問題。在假設已知環(huán)境下，配送中心與需求點之間的需求、配送時間、最大配送時間等相關數(shù)據分別如表1、表2、表3所示。該問題中共包含40個分銷點配送需求點，其中有5個需求點，如圖2所示。目前擁有5輛型號一致的配送車輛，每輛車的配送上限為5t。

圖2 供應鏈空間分布情況

表1 配送中心/超市到分銷點的平均配送需求量

表2 配送中心/超市到分銷點的平均運輸時間

表3 配送中心/超市到分銷點的最大配送時間

3.2 算法效果分析

基于上述數(shù)據，本文將通過免疫遺傳算法對選擇模型進行求解。所有的數(shù)值實驗均在Windows 10.0系統(tǒng)MATLAB中完成。種群的最大數(shù)值設置為40，最大迭代次數(shù)設置為500，個體交叉的概率為0.75。

由圖3、圖4可以看出，GA效率快于IGA。但是，IGA在解的最優(yōu)性上顯然好于GA。如圖5所示，Cplex所使用的精確算法在在迭代約400次后達到收斂狀態(tài)，即相對于IGA效率較低。為進一步驗證IGA解的可靠性，如表4所示為當問題規(guī)模為50，90，130時各算法性能差異。通過對比可以發(fā)現(xiàn)，IGA在求解時間上的優(yōu)勢非常明顯，解的質量雖然隨著問題規(guī)模的增加下降明顯，但相對于GA來說依然保持著較大優(yōu)勢。

圖3 免疫遺傳算法的平均及最優(yōu)適應度曲線

圖4 免疫遺傳算法與遺傳算法目標函數(shù)收斂對比

圖5 Cplex收斂曲線

此外，通過改變個體交叉概率(0.5、0.7、0.9)，研究其對免疫遺傳算法的影響。圖6表明，在種群規(guī)模為20時，隨著交叉概率的增加，其對應的適應度值和最佳解的質量亦增加。最后，為了驗證不同種群大小對算法表現(xiàn)的影響，本文分別計算了種群數(shù)量為20、30、40、50、60下算法的適應度值，具體見圖7。從圖7可以發(fā)現(xiàn)，當種群規(guī)模是40時，效果是最好的。

圖6 不同交叉概率下免疫遺傳算法的適應度曲線

圖7 不同種群大小下免疫遺傳算法的適應度曲線

3.3 方案效果分析

為驗證魯棒路徑優(yōu)化方案效果，本部分將通過對比一般隨機優(yōu)化模型下得到的方案加以分析。

如圖8、圖9、表4、表5所示，傳統(tǒng)配送路徑方案和魯棒配送路徑方案在局部存在一定差別。特別是如圖中橢圓標注區(qū)域中距離配送中心較遠地帶。在魯棒優(yōu)化中，這些需求點在保證配送成本盡可能低的前提下，相對均為地分配給了配送中心，以保證配送的及時性。而傳統(tǒng)模型對配送及時性未做考慮，因此導致橢圓區(qū)域內的需求點以配送總距離最短分布，此時有些配送中心服務對象較多，有些較少。如圖10、圖11所示，通過對比配送延誤比發(fā)現(xiàn)，魯棒優(yōu)化模型在各個問題規(guī)模下相對傳統(tǒng)模型均較低，且低幅隨著問題規(guī)模的增加而增大。這表明在本問題中，魯棒優(yōu)化模型可以較好的保證各個需求點配送的及時性，能更好的滿足各個點的配送需求。

表4 算法效果對比

表5 模型結果對比

圖8 魯棒優(yōu)化模型所得方案

圖9 傳統(tǒng)風險中性模型所得方案

圖10 不同規(guī)模下配送成本對比

圖11 不同規(guī)模下配送延誤對比

4 結論

本文提出了不確定環(huán)境下隨機因素數(shù)據不完全時的車輛配送路徑魯棒優(yōu)化模型以及求解算法。構建了基于魯棒優(yōu)化的車輛配送路徑規(guī)劃模型以及確定型的魯棒對等式。同時，為了提高該模型在大規(guī)模問題下的可行性，提出了基于免疫遺傳算法的求解算法。通過算例分析發(fā)現(xiàn)，魯棒優(yōu)化模型可顯著提升在不確定環(huán)境下的配送及時率，相比一般隨機優(yōu)化方法，配送延誤可降低28.6%。提出的免疫遺傳算法在算法效率上顯著優(yōu)于一般遺傳算法，且對比CPLEX等精確求解方法具有明顯優(yōu)勢。

然而，路徑規(guī)劃問題屬于典型NP-Hard問題，隨著問題規(guī)模的增加，其求解難度急劇增大，因此，研究面向大規(guī)模問題的魯棒路徑優(yōu)化問題將是下一步的主要工作。

DOI:10.1016/j.ejor.2018.07.039.

DOI:10.1016/j.cor.2018.02.006.