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

(1.武漢科技大學(xué) 機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室，武漢 430081；2.湖北文理學(xué)院 機(jī)械工程學(xué)院，湖北 襄陽 441053)

0 引言

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

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

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

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

1.1 問題描述

為了模型構(gòu)建的科學(xué)性和有效性，本文做出如下假設(shè)：

(1) 每一個(gè)需求點(diǎn)只能被一輛配送車輛所服務(wù)；

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

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

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

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

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

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

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

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

wki:車輛到達(dá)最后需求點(diǎn)的時(shí)間。

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

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

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

(1)

(2)

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

特別地，當(dāng)Z滿足以下條件時(shí)，不確定集合Ut分別可構(gòu)成凸包集合、箱型集合及橢圓形集合等。

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

基于上述定義，便可得到在不確定需求或行程時(shí)間參數(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)

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

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

(16)

(17)

(18)

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

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

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

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

(1)初始抗體編碼

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

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

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

(2)多樣性評(píng)估

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

(19)

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

(20)

因此，個(gè)體選擇概率可以表達(dá)為：

(21)

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

(22)

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

(23)

(3)免疫操作

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

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

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

(24)

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

(25)

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

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

圖1 算法流程圖

3 案例分析

3.1 案例背景

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

圖2 供應(yīng)鏈空間分布情況

表1 配送中心/超市到分銷點(diǎn)的平均配送需求量

表2 配送中心/超市到分銷點(diǎn)的平均運(yùn)輸時(shí)間

表3 配送中心/超市到分銷點(diǎn)的最大配送時(shí)間

3.2 算法效果分析

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

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

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

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

圖5 Cplex收斂曲線

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

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

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

3.3 方案效果分析

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

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

表4 算法效果對(duì)比

表5 模型結(jié)果對(duì)比

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

圖9 傳統(tǒng)風(fēng)險(xiǎn)中性模型所得方案

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

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

4 結(jié)論

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

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

DOI:10.1016/j.ejor.2018.07.039.

DOI:10.1016/j.cor.2018.02.006.