鄧 燁，朱萬(wàn)紅，唐 建

DENG Ye,ZHU Wanhong,TANG Jian

解放軍理工大學(xué) 野戰(zhàn)工程學(xué)院，南京 210001

College of Field Engineering,PLAUniversity of Science and Technology,Nanjing 210001,China

1 引言

現(xiàn)代城市物流配送中存在很多需求不確定的情況，例如運(yùn)鈔車對(duì)銀行網(wǎng)點(diǎn)進(jìn)行存取款服務(wù)，應(yīng)急中心對(duì)災(zāi)害點(diǎn)進(jìn)行應(yīng)急配送等，這些都是要求在需求信息不充分的情況下完成物流配送任務(wù)。如何在保證服務(wù)質(zhì)量的前提下盡量降低配送成本，是物流配送者最為關(guān)心的內(nèi)容，因此隨機(jī)需求的車輛路徑問題（Vehicle Routing Problem with Stochastic Demand，VRPSD）研究得到廣泛關(guān)注[1]。傳統(tǒng)VRPSD問題一般不考慮客戶的時(shí)間窗約束，而在現(xiàn)實(shí)中，是否滿足時(shí)間窗約束往往也是評(píng)價(jià)服務(wù)質(zhì)量的重要標(biāo)準(zhǔn)之一，因此需要加以考慮[2]。同時(shí)，針對(duì)需求超出容量約束時(shí)的傳統(tǒng)補(bǔ)救策略由于偏于保守，往往造成違反客戶時(shí)間窗的風(fēng)險(xiǎn)成本較高，因此需要提出更加敏捷可靠的補(bǔ)救策略。

目前，關(guān)于隨機(jī)需求車輛路徑問題一般是基于先驗(yàn)序列的兩階段優(yōu)化方法[3]，而先驗(yàn)序列的確定一般是基于機(jī)會(huì)約束規(guī)劃（Chance Constrant Programming，CCP）和二元可能性理論進(jìn)行研究[4]?；镜臋C(jī)會(huì)約束規(guī)劃模型以預(yù)設(shè)成功服務(wù)概率作為約束，不考慮服務(wù)失敗情形下的風(fēng)險(xiǎn)成本，適用于需求服從連續(xù)分布情況，可通過確定等價(jià)式轉(zhuǎn)化為確定性模型求解?；径赡苄岳碚撝豢紤]需求是二元、離散情況[5]，根據(jù)服務(wù)的期望成本范圍以及服務(wù)失敗情形下的風(fēng)險(xiǎn)成本來(lái)確定先驗(yàn)路線?？紤]到真實(shí)客戶需求量具有多種可能性，并非簡(jiǎn)單二元結(jié)構(gòu)，因此本文采用機(jī)會(huì)約束規(guī)劃理論求解先驗(yàn)路線，并采用預(yù)優(yōu)化策略[3]進(jìn)行補(bǔ)救調(diào)整，即根據(jù)服務(wù)失敗情況下的總服務(wù)成本確定最優(yōu)的服務(wù)概率和計(jì)劃配送路線，然后再對(duì)不滿足實(shí)際需求的客戶進(jìn)行補(bǔ)救。

針對(duì)服務(wù)失敗（容量超出）的情況，一般按照Teodorovi?提出的補(bǔ)救策略對(duì)客戶進(jìn)行補(bǔ)救[6-8]，其中Yee[9]針對(duì)計(jì)劃路線配送失敗情況下的動(dòng)態(tài)調(diào)度策略進(jìn)行了研究。在現(xiàn)實(shí)中，由于不同配送中心的信息化服務(wù)水平不同，導(dǎo)致應(yīng)對(duì)服務(wù)失敗情況的補(bǔ)救策略有很大差異。在信息化水平較低的配送中，車輛發(fā)現(xiàn)服務(wù)失敗一般是返回中心重新裝載；當(dāng)信息化水平較高時(shí)，一旦發(fā)現(xiàn)超出容量范圍則可以即時(shí)通知中心重新派出新車；而當(dāng)信息化水平最高時(shí)，可以通過一定的預(yù)測(cè)提前判斷容量是否超出并且即時(shí)通知中心派出新車。不同補(bǔ)救策略下的風(fēng)險(xiǎn)成本是明顯不同的，因此，研究不同信息化水平的補(bǔ)救策略如何影響風(fēng)險(xiǎn)成本對(duì)決策者而言具有重要的指導(dǎo)意義。

2 問題描述及數(shù)學(xué)模型

2.1 問題假設(shè)及目標(biāo)

本文研究的是現(xiàn)代城市物流配送中的隨機(jī)需求且有時(shí)間窗的車輛路徑優(yōu)化問題，目前僅有較少文獻(xiàn)對(duì)含有時(shí)間窗約束的隨機(jī)車輛問題進(jìn)行研究[2，10-11]，為了不失一般性，綜合以上文獻(xiàn)中的基本假設(shè)內(nèi)容，對(duì)本文研究問題進(jìn)行如下假設(shè)：（1）客戶需求量是連續(xù)隨機(jī)變量，服從連續(xù)概率分布且不小于0；（2）客戶具有服務(wù)時(shí)間窗，只有在時(shí)間窗口內(nèi)才可以進(jìn)行服務(wù)，提前到達(dá)的車輛需等待到開始時(shí)刻再進(jìn)行服務(wù)，超出截止時(shí)刻到達(dá)的車輛則認(rèn)為配送失敗，因此具有嚴(yán)格的時(shí)間窗約束，但若由于不滿足隨機(jī)需求量進(jìn)行補(bǔ)救而超出時(shí)間窗的，則僅需對(duì)超出時(shí)間窗的部分給予懲罰；（3）每個(gè)客戶原則上只被服務(wù)一次，除非由于不滿足需求量而進(jìn)行補(bǔ)救；（4）車輛行駛速度假設(shè)為定值1，且路段間的行駛速度恒定不變，車輛的車型相同，車容量相同，不考慮車輛最大行駛距離或最大行駛時(shí)間約束；（5）每輛車服務(wù)完所有客戶后返回配送點(diǎn)，同時(shí)每輛車在完成其所有計(jì)劃客戶后才支付單輛車的報(bào)酬（多次發(fā)車補(bǔ)救也只算為單輛車）。

在這里，假設(shè)客戶需求為非負(fù)的連續(xù)隨機(jī)變量具有一般性，從長(zhǎng)遠(yuǎn)時(shí)間來(lái)看，離散隨機(jī)變量可以看為連續(xù)，而需求為0的隨機(jī)變量代表該客戶不需要服務(wù)；同時(shí)假設(shè)時(shí)間窗約束在預(yù)優(yōu)化階段為嚴(yán)格約束，在補(bǔ)救階段則被松弛（否則均為不可行解），體現(xiàn)了含有時(shí)間窗的隨機(jī)需求模型的特殊性。只有在這些假設(shè)基礎(chǔ)上，才能進(jìn)行模型的構(gòu)建和求解。

基于以上假設(shè)，問題的優(yōu)化目標(biāo)是在滿足客戶容量約束和時(shí)間窗約束的條件下使總服務(wù)成本最少，達(dá)到經(jīng)濟(jì)效益的最大化。這里的總服務(wù)成本是指各車的派出成本與行駛成本之和，即在最小化派出的車輛數(shù)的前提下盡量縮短服務(wù)距離。

2.2 符號(hào)說明

隨機(jī)需求有時(shí)間窗的車輛路徑問題（Vehicle Routing Problem with Stochastic Demand and Time Windows，VRPSDTW）是基本VRPTW模型的一種衍生模型。因此，可以在Desrochers等[12]提出的傳統(tǒng)網(wǎng)絡(luò)流公式體系下進(jìn)行描述。

設(shè)G=(V,D)是一個(gè)完全有向圖，V={v0,v1,…,vn+1}代表所有點(diǎn)的集合，其中v0和vn+1代表1個(gè)配送中心點(diǎn)和1個(gè)虛擬配送中心點(diǎn)，其他點(diǎn)代表客戶，構(gòu)成客戶點(diǎn)集C={v1,v2,…,vn}；每個(gè)客戶點(diǎn)存在一個(gè)隨機(jī)需求qi≥0，并且假設(shè)其服從某一概率分布Ui，還存在服務(wù)時(shí)間si≥0，并且要求在時(shí)間窗[ei,li]內(nèi)得到服務(wù)，配送中心的服務(wù)時(shí)間窗口為[0,Tmax]；任意兩點(diǎn)組合構(gòu)成一條邊，則 D={(vi,vj)|(vi,vj)∨(v0,vi)∨(vi,vn+1),vi,vj∈C,i≠j}代表道路邊集，每一條邊(vi,vj)∈D都有一個(gè)權(quán)重，即距離dij且dij≥0；任一車輛k∈K ，每輛車的最大載重量為Q。

2.3 數(shù)學(xué)模型

為了對(duì)VRPSDTW問題進(jìn)行建模，首先需要定義兩個(gè)決策變量：

（1）二進(jìn)制決策變量：

（2）非負(fù)實(shí)數(shù)決策變量：車輛k服務(wù)完客戶vi（包括配送中心）后的出發(fā)時(shí)間。

最終，可以構(gòu)建VRPSDTW為一個(gè)機(jī)會(huì)約束混合整數(shù)規(guī)劃數(shù)學(xué)模型。

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

約束條件：

其中，式（1）表示最小化總的配送成本，默認(rèn)單輛車的派出成本遠(yuǎn)大于單位距離成本，M設(shè)置為一個(gè)較大的常數(shù)；式（2）表示隨機(jī)容量約束，Pr為概率測(cè)度，α為設(shè)定的滿足容量約束的最低概率值α∈(0,1]，qi為客戶i的隨機(jī)需求量；式（3）表示每個(gè)客戶必須并且只能被訪問一次；式（4）表示任何到達(dá)某一客戶的車必須還從同一個(gè)客戶處離開；式（5）表示每輛車必須從配送中心出發(fā)最后還必須返回中心；式（6）表示每輛車離開中心最多一次，同時(shí)其返回中心也最多一次；式（7）表示對(duì)某點(diǎn)的服務(wù)開始時(shí)間必須介于該點(diǎn)的時(shí)間窗內(nèi)；式（8）表示車輛從上一點(diǎn)出發(fā)到達(dá)下一點(diǎn)的到達(dá)時(shí)間一定不晚于下一點(diǎn)的服務(wù)開始時(shí)間。

2.4 模型轉(zhuǎn)化與分析

2.4.1 隨機(jī)約束轉(zhuǎn)化

由于本文考慮的模型含有隨機(jī)需求，是一類隨機(jī)約束優(yōu)化模型，一般方法是通過隨機(jī)模擬需求進(jìn)行仿真。該方法具有不受分布類型限制，適用性強(qiáng)的優(yōu)點(diǎn)，但也存在很大缺陷：（1）仿真次數(shù)要求高，計(jì)算量很大。尤其是當(dāng)問題規(guī)模也很大的時(shí)候，隨機(jī)模擬的計(jì)算時(shí)間會(huì)非常長(zhǎng)；（2）計(jì)算結(jié)果不穩(wěn)定，即使經(jīng)過大量的仿真，也不能保證得到理論最優(yōu)解。因此，本文假設(shè)需求變量服從獨(dú)立正態(tài)分布，這樣就可以基于不確定原理[13]，將機(jī)會(huì)約束式（2）轉(zhuǎn)化為確定等價(jià)形式進(jìn)行求解，見式（9）。

其中，Φi(q)為正態(tài)分布N(μi,σi)的分布函數(shù)，(α)為分布函數(shù)的反函數(shù)，即求α分位點(diǎn)處的q值。

這樣轉(zhuǎn)化以后，實(shí)際是將隨機(jī)約束規(guī)劃模型轉(zhuǎn)化成了一般的確定性約束規(guī)劃模型，大大降低了計(jì)算量，同時(shí)可以保證得到理論上的最優(yōu)解。這里，考慮到真實(shí)情況的復(fù)雜性，某段時(shí)期內(nèi)客戶的需求量當(dāng)然不可能完全符合正態(tài)分布，但是根據(jù)中長(zhǎng)期統(tǒng)計(jì)的客觀數(shù)據(jù)，以及中心極限定理，可認(rèn)為需求變量服從獨(dú)立正態(tài)分布并不失其一般性。

2.4.2 補(bǔ)救策略分析

模型在隨機(jī)約束條件或其確定等價(jià)式下算出的最優(yōu)解只能作為計(jì)劃配送方案，而現(xiàn)實(shí)中一旦部分客戶的需求量太大，使得計(jì)劃配送方案中剩余部分客戶的需求無(wú)法滿足，則需要額外進(jìn)行配送補(bǔ)救。而補(bǔ)救策略的不同，額外增加的成本和時(shí)間也不同。本文基于不同的物流信息化水平，給出3種補(bǔ)救調(diào)整策略分別為：

（1）策略1：某輛車按照計(jì)劃路線配送，若在到達(dá)客戶i時(shí)得知其需求超出當(dāng)前剩余貨量，則卸載全部貨量后返回中心重新裝載貨物，然后立刻返回客戶i補(bǔ)充剩余需求，并繼續(xù)按照原計(jì)劃配送路線服務(wù)后續(xù)客戶；若在服務(wù)完客戶i后剩余貨量正好為0，而后面還有客戶，則立刻返回中心重新裝載，然后直接開始服務(wù)后續(xù)客戶。

（2）策略2：某輛車按照計(jì)劃路線配送，若在到達(dá)客戶i時(shí)得知其需求超出當(dāng)前剩余貨量，則立刻通知中心即刻派出新車服務(wù)客戶i及其后續(xù)客戶，原車卸載全部貨量后返回中心；若到達(dá)客戶i時(shí)發(fā)現(xiàn)服務(wù)完后的剩余容量將正好為0，而后面還有客戶，則立刻通知中心即刻派出新車服務(wù)后續(xù)客戶，原車服務(wù)完客戶i后直接返回中心。

（3）策略3：某輛車按照計(jì)劃路線配送，若在到達(dá)客戶i時(shí)發(fā)現(xiàn)在滿足其需求后剩下的載貨量不足以滿足下一個(gè)客戶的計(jì)劃需求量，則立刻通知中心派出新車開始服務(wù)后續(xù)客戶，原車服務(wù)完客戶i之后，直接返回中心；若在到達(dá)客戶i時(shí)發(fā)現(xiàn)當(dāng)前的需求已無(wú)法滿足，則立刻通知中心派出新車到客戶i補(bǔ)充剩余需求，然后按照計(jì)劃路線服務(wù)后續(xù)客戶，原車卸載全部貨量后返回中心。

以上策略均假設(shè)到達(dá)客戶即可知道當(dāng)前準(zhǔn)確需求量，同時(shí)配送中心已經(jīng)準(zhǔn)備好額外用車，不需增加額外裝貨時(shí)間。其中第一種策略是目前被所有相關(guān)文獻(xiàn)采用的補(bǔ)救策略，其后兩種是本文所提出的信息化補(bǔ)救策略。直觀上看，第一種策略信息化水平最低，偏向于保守與經(jīng)濟(jì)，即使發(fā)現(xiàn)容量不滿足，車輛也要等服務(wù)完畢才返回，并且不增加額外車輛，僅增加額外車次；第二種策略信息化水平一般，偏向主動(dòng)與高效，一旦發(fā)現(xiàn)不滿足需求，即刻通知中心派出新車；第三種策略信息化水平最高，最為高效，通過預(yù)測(cè)下一點(diǎn)無(wú)法服務(wù)，在還未服務(wù)下一點(diǎn)時(shí)就通知中心派車，因此能最大程度保證服務(wù)的成功性，但同時(shí)以損失一定經(jīng)濟(jì)效益為代價(jià)，可能會(huì)造成車輛和貨物的浪費(fèi)。這三種策略將在第4章中給出仿真比較。

3 算法設(shè)計(jì)

3.1 混合進(jìn)化算法

帶有時(shí)間窗車輛路徑問題（VRPTW）是一類組合優(yōu)化問題，可行解的數(shù)量會(huì)隨著問題的規(guī)模呈指數(shù)增長(zhǎng)，是典型的NP-hard問題[14]，本文研究的VRPSDTW問題同樣如此，當(dāng)問題規(guī)模較大時(shí)，傳統(tǒng)的精確算法在有限時(shí)間內(nèi)已不可能求解，必須設(shè)計(jì)智能算法進(jìn)行求解。為了提高算法效率，本文設(shè)計(jì)了包括最近鄰初始化算法、Falkenauer交叉算子、多樣化變異算子和改進(jìn)選擇策略的混合進(jìn)化算法（Hybrid Evolution Algorithm，HEA），以求實(shí)現(xiàn)算法收斂速度和收斂精度的平衡?；旌线M(jìn)化算法流程見圖1。

圖1 混合進(jìn)化算法流程圖

3.2 編碼與最近鄰初始化

路徑優(yōu)化這一類組合優(yōu)化問題一般采用隨機(jī)排列訪問點(diǎn)的實(shí)數(shù)編碼方法構(gòu)造解。如圖2所示，0代表配送點(diǎn)，其他為客戶點(diǎn)，每個(gè)0后面代表一條配送路線，有多少0，就代表有幾條配送路線。

圖2 染色體編碼案例

然而，由于產(chǎn)生可行解本身就是一個(gè)NP-hard問題，采用隨機(jī)初始化的方法很難在有限時(shí)間內(nèi)得到足夠數(shù)量的種群。因此，參考Solomon[15]的初始化方法，提出一種隨機(jī)參數(shù)最近鄰啟發(fā)式算法初始化種群。首先，需重新定義任意兩點(diǎn)間的距離d′ij：

式中，dij代表行駛時(shí)間（速度為1）；Tij代表下一點(diǎn)開始服務(wù)時(shí)刻與上一點(diǎn)出發(fā)時(shí)刻的差，Tij=bj-(bi+si)，bj=max{ej,bi+si+dij}；Vij代表下一點(diǎn)到達(dá)時(shí)刻與下一點(diǎn)服務(wù)結(jié)束時(shí)刻的差，Vij=lj-(bi+si+dij)；δi為隨機(jī)歸一化系數(shù)，且。隨機(jī)初始化算法首先隨機(jī)生成與種群個(gè)數(shù)相同的多組系數(shù)δi。

算法從配送中心點(diǎn)開始，每次選擇d′ij值最小的點(diǎn)作為下一個(gè)訪問點(diǎn)，當(dāng)不滿足約束條件時(shí)，返回配送中心，重新派出車輛開始選剩下的點(diǎn)直到所有客戶均被訪問完畢，重復(fù)此過程直到生成所有初始種群。

3.3 Falkenauer交叉算子

交叉算子采用Falkenauer[16]提出的經(jīng)典形式。首先從第一個(gè)父代中選擇隨機(jī)數(shù)量的子路徑給子代，然后從第二個(gè)父代中選擇不含有當(dāng)前子代客戶點(diǎn)的子路徑給子代，如果還有客戶未被選中，則按照剩余點(diǎn)在第二個(gè)父代中的順序依次嘗試插入新路徑中，如果無(wú)法插入，則新建一條子路徑。如圖3所示，交叉產(chǎn)生的子代均為可行解，將其放入子代種群popc中。

圖3 Falkenauer交叉算子示意圖

3.4 多樣化變異算子

傳統(tǒng)進(jìn)化算法一般只采用一種變異策略，導(dǎo)致解的鄰域結(jié)構(gòu)比較單一，解的搜索空間狹窄，而采用多樣化變異策略可以顯著彌補(bǔ)這些缺陷。本算法中采用六種變異算子來(lái)對(duì)種群進(jìn)行變異操作，分別為“交換（Exchange）”、“移動(dòng)（Relocate）”、“組合（Combine）”、“分解（Split）”、“轉(zhuǎn)換（Shift）”和“反轉(zhuǎn)（Converse）”。如圖4所示，白色方塊代表真實(shí)配送中心，灰色方塊代表虛擬配送中心。算法依次選擇種群樣本個(gè)體，按照變異概率進(jìn)行變異，每次變異開始后，隨機(jī)選擇一種變異方式執(zhí)行，如果變異成功生成可行解，放入子代種群popm中。

3.5 改進(jìn)選擇策略

傳統(tǒng)的選擇策略多是直接對(duì)子代進(jìn)行選擇，誤差較大，較優(yōu)解易丟失。因此，這里將全局最優(yōu)解、父代種群和子代種群進(jìn)行混合，一起參與下一次的選擇。另外，傳統(tǒng)基于適應(yīng)值進(jìn)行概率賦值的選擇方法在進(jìn)化早期易陷入“早熟”，后期由于適應(yīng)值差異不大易造成收斂速度變慢，而基于適應(yīng)值的排序數(shù)進(jìn)行轉(zhuǎn)化的賦值方法不隨適應(yīng)值大小而變化，只由當(dāng)前序值決定被選概率，因此可以避免局部收斂，提高收斂速度[17]。在此基礎(chǔ)上，本文提出基于Boltzmann序值的概率賦值方法。在機(jī)器學(xué)習(xí)和自適應(yīng)控制等領(lǐng)域，Boltzmann選擇策略（Boltzmann selection policy）被搜索算法所廣泛采用，它模擬了自然界中溫度的非線性下降過程，因此也是模擬退火算法的核心思想。

首先，按照函數(shù)目標(biāo)值由小到大排序（目標(biāo)值越小則越優(yōu)）；然后，按照式（11）、式（12）對(duì)每個(gè)序數(shù)對(duì)應(yīng)的個(gè)體賦給概率值：

式中，Pi代表排在第i位的個(gè)體在輪盤賭中被選擇的概率；n為參與選擇的染色體個(gè)數(shù)；T為當(dāng)前溫度，T0為初始溫度，默認(rèn)T0=100，iter為當(dāng)前迭代次數(shù)。

圖4 六種變異算子示意圖

最后，按照概率值Pi進(jìn)行輪盤賭，有放回地選出與父代種群相等數(shù)量的子代種群pop，作為下一次交叉和變異的種群，同時(shí)記錄最佳個(gè)體，將其與全局最佳比較，如果更優(yōu)，則更新全局最優(yōu)解。

3.6 約束處理方法

一般約束處理方法有以下幾種[18]：懲罰函數(shù)法、修復(fù)法、分離目標(biāo)和約束法等。在本算法中，采用分離目標(biāo)和約束法，因?yàn)樵摲椒ū荛_了懲罰系數(shù)難以選擇的困難，是一種更為有效且通用的約束處理機(jī)制[19]。

在預(yù)優(yōu)化階段，算法執(zhí)行嚴(yán)格的約束條件，即只接受可行解，變異和交叉操作只產(chǎn)生可行解，不可行解直接舍棄，因此每次產(chǎn)生的子代種群數(shù)是不同的，有時(shí)候甚至找不到可行解。但由于本算法中交叉算子每次交叉只產(chǎn)生可行解，同時(shí)多樣化變異算子具有較強(qiáng)的變異能力，因此并不會(huì)出現(xiàn)找不到可行解或可行解都相同的情況。

算法需要處理兩類約束：車輛容量約束和客戶時(shí)間窗約束。對(duì)于車輛容量約束，按照式（9）判斷，根據(jù)設(shè)定的成功服務(wù)概率α可以求得每個(gè)解sol的任一子路徑r′的總計(jì)劃需求量，若有，則解sol滿足容量約束。對(duì)于客戶時(shí)間窗約束，需要判斷到達(dá)時(shí)間是否在當(dāng)前客戶截止服務(wù)時(shí)刻之前。因此，若有Ati≤li,?i∈r′,r′∈sol，則解 sol滿足時(shí)間窗約束，其中，

4 實(shí)驗(yàn)與分析

所有實(shí)驗(yàn)和算法基于Matlab R2016a軟件平臺(tái)進(jìn)行，算法參數(shù)設(shè)置如下：種群數(shù) popsize=100，交叉概率ρc=0.5，變異概率ρm=0.5?？紤]城市物流配送一般需要服務(wù)的客戶數(shù)量相對(duì)較多且問題復(fù)雜性也易隨客戶數(shù)量變化而改變，為了不失一般性，本文以Solomon的VRPTW標(biāo)準(zhǔn)問題集為例，將其轉(zhuǎn)化為具有隨機(jī)需求問題的測(cè)試集進(jìn)行實(shí)驗(yàn)?；緶y(cè)試集可在以下網(wǎng)站下載：http：//w.cba.neu.edu/～msolomon/problems.htm，鑒于篇幅限制，這里僅選擇RC108數(shù)據(jù)為例進(jìn)行實(shí)驗(yàn)?；舅憷齊C108中有100個(gè)客戶，客戶呈隨機(jī)和聚集混合形式分布，車輛載重Q=200。模型按照式（1）計(jì)算函數(shù)適應(yīng)值，其中M=1 000。

4.1 基于確定需求模型的算法改進(jìn)實(shí)驗(yàn)

本文采用的混合進(jìn)化算法主要在兩方面進(jìn)行了改進(jìn)：多樣化變異策略和選擇策略。這兩項(xiàng)策略分別通過擴(kuò)大搜索空間和增加種群多樣性，防止算法陷入局部收斂。為了驗(yàn)證算法改進(jìn)的有效性，設(shè)計(jì)了兩組對(duì)比實(shí)驗(yàn)進(jìn)行說明，一組用于比較變異操作的改進(jìn)效果，一組用于比較選擇操作的改進(jìn)效果。暫時(shí)只考慮確定需求情況，通過分析基本VRPTW模型求解結(jié)果，驗(yàn)證算法的有效性。

4.1.1 變異操作對(duì)比

在本文混合進(jìn)化算法基礎(chǔ)上，分別設(shè)置單種變異算子和隨機(jī)多樣化變異算子進(jìn)行對(duì)照，設(shè)置迭代數(shù)IterMax=200，最優(yōu)適應(yīng)值對(duì)應(yīng)的路徑總長(zhǎng)度收斂結(jié)果見圖5。

圖5 變異算子改進(jìn)結(jié)果對(duì)比圖

可見，單獨(dú)采用一種算子的收斂效果遠(yuǎn)沒有綜合采用六種算子的效果好，通過不同算子的組合，可以搜索到單個(gè)變異算子不可能搜索到的鄰域解，使發(fā)現(xiàn)較優(yōu)解的概率大大提高。

4.1.2 選擇策略對(duì)比

在采用多樣化變異算子的基礎(chǔ)上，分別比較基于適應(yīng)值的隨機(jī)通用采樣（Stochastic Universal Sampling）[20]、基于指數(shù)序值的輪盤賭和基于本文提出的Boltzmann序值的輪盤賭三種選擇算子，設(shè)置迭代數(shù)IterMax=1 000，結(jié)果見圖6。

圖6 選擇算子改進(jìn)結(jié)果對(duì)比圖

可見，Boltzmann序值算子很好結(jié)合了隨機(jī)通用采樣算子和指數(shù)序值算子的優(yōu)勢(shì)，在前期收斂較快，在后期也有較強(qiáng)的尋優(yōu)性能。

同時(shí)，在采用Boltzmann序值輪盤賭算子的基礎(chǔ)上，對(duì)三種不同保留策略的收斂情況進(jìn)行比較，分別為：（a）子代、精英解混合選擇策略；（b）子代、父代混合選擇策略；（c）子代、父代和精英解混合策略，結(jié)果見圖7。

圖7 保留策略改進(jìn)結(jié)果對(duì)比圖

可見，c策略雖然在前期收斂速度并不快，但后期尋優(yōu)性能明顯優(yōu)于前兩者，這是因?yàn)閏策略的種群多樣性優(yōu)勢(shì)主要在后期搜索中才能明顯表現(xiàn)，可以較好防止收斂于一個(gè)局部最優(yōu)解。

4.1.3 算法綜合性能對(duì)比

為進(jìn)一步說明所提算法的優(yōu)越性，本文將本算法HEA與文獻(xiàn)[21]中所提的改進(jìn)遺傳算法IGA進(jìn)行對(duì)比。隨機(jī)抽取Solomon算例中6個(gè)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，迭代次數(shù)設(shè)置為1 000，每個(gè)數(shù)據(jù)重復(fù)實(shí)驗(yàn)10次，記錄10次實(shí)驗(yàn)最優(yōu)解的平均值A(chǔ)vg和其中的最優(yōu)值Best，并將其與目前已知最優(yōu)解BestSoFar進(jìn)行對(duì)比。結(jié)果見表1，其中“/”之前代表路程長(zhǎng)度，之后代表車輛數(shù)。

由表1可見，本算法的整體收斂結(jié)果較改進(jìn)遺傳算法IGA更優(yōu)且穩(wěn)定，與已知最優(yōu)解的差距更小，說明本算法綜合性能較優(yōu)。

表1 算法綜合性能對(duì)比結(jié)果表

4.2 基于隨機(jī)需求模型的優(yōu)化實(shí)驗(yàn)及參數(shù)敏感性分析

設(shè)定不同概率α對(duì)模型優(yōu)化結(jié)果會(huì)產(chǎn)生很大影響，α設(shè)置越大，完成計(jì)劃的成本越高。α=0.5時(shí)，相當(dāng)于計(jì)劃滿足所有客戶的期望需求，則其路徑優(yōu)化結(jié)果見圖8。最優(yōu)解收斂迭代曲線見圖9，其中黑色實(shí)線表示迭代最優(yōu)解對(duì)應(yīng)的路程，虛線代表種群平均路程，Vn代表最優(yōu)解對(duì)應(yīng)的車數(shù)。求得的計(jì)劃配送最優(yōu)路線結(jié)果見表2。則計(jì)劃配送成本為1 156.56+11M=12 156.56。

圖8 α=0.5時(shí)最優(yōu)計(jì)劃配送路線圖

圖9 α=0.5時(shí)最優(yōu)解收斂圖

表2 α=0.5時(shí)計(jì)劃配送最優(yōu)路線結(jié)果表

為分析計(jì)劃配送總成本對(duì)成功服務(wù)概率α的敏感性，再分別設(shè)置α的值為0.2、0.4、0.6、0.8，則得到對(duì)應(yīng)的計(jì)劃配送成本結(jié)果見表3。

表3 計(jì)劃配送成本結(jié)果表

可見，隨著成功服務(wù)概率α值的逐漸增加，計(jì)劃總路程、計(jì)劃車數(shù)以及計(jì)劃總成本也隨之增加。這顯然是合理的，因?yàn)殡S著成功服務(wù)概率的增加，每個(gè)客戶的計(jì)劃需求量都被設(shè)為一個(gè)較大的值，這樣導(dǎo)致需要更多的車和路程去完成配送。但是，雖然服務(wù)成功率增加了，物資不必要的浪費(fèi)也在同樣增加，因此需要結(jié)合下一步的仿真結(jié)果，確定最合理的服務(wù)概率α。

4.3 補(bǔ)救策略仿真實(shí)驗(yàn)及分析

如前文2.4.2節(jié)所述，按計(jì)劃配送方案進(jìn)行配送時(shí)總會(huì)遇到需求量超出的情況，此時(shí)服務(wù)失敗，需要對(duì)不滿足需求的客戶進(jìn)行補(bǔ)救。分別針對(duì)前文所述三種補(bǔ)救策略進(jìn)行仿真實(shí)驗(yàn)。假設(shè)給定概率完成服務(wù)概率α=0.5，以表1中的優(yōu)化結(jié)果作為計(jì)劃配送路線，仿真次數(shù)Simnum=5 000次，仿真結(jié)果見表4～表6。其中，overN表示每段子路徑超出容量的平均次數(shù)，overV表示每段子路徑多派出的平均車次數(shù)，overL表示每段子路徑多行駛的平均路程，overAt表示每段子路徑中到達(dá)客戶時(shí)刻的總延遲時(shí)間平均值，overWn表示每段子路徑超出截止時(shí)間窗的平均客戶個(gè)數(shù)，overWt表示每段子路徑違反時(shí)間窗的總時(shí)間平均值。最后一個(gè)指標(biāo)overC表示每段子路徑違反時(shí)間窗的懲罰成本，按照下式計(jì)算：

表4 策略1的仿真結(jié)果統(tǒng)計(jì)表

表5 策略2的仿真結(jié)果統(tǒng)計(jì)表

表6 策略3的仿真結(jié)果統(tǒng)計(jì)表

表7 不同α?xí)r總成本優(yōu)化結(jié)果表

其中，Ati為車輛到達(dá)客戶i的時(shí)刻，Mt為單位時(shí)間的違約懲罰費(fèi)用，本文設(shè)Mt=10。

觀察表4～表6可以看出，雖然超出計(jì)劃配送量的次數(shù)overN和新增車次overV相同（均為2.98次），但是策略2較策略1在延遲時(shí)間overAt、違反時(shí)間約束次數(shù)overWn和違反時(shí)間overWt三個(gè)指標(biāo)上均有較大降低，因此其更加適應(yīng)部隊(duì)客戶對(duì)時(shí)效性的要求，在及時(shí)響應(yīng)客戶隨機(jī)需求的同時(shí)滿足時(shí)間窗約束，因此可靠性也更強(qiáng)；而策略3中對(duì)應(yīng)的后三項(xiàng)指標(biāo)又有明顯降低，因此其時(shí)效性和可靠性最強(qiáng)。同時(shí)，雖然策略3的overN和overV與策略1、2相同，但在超出路程overL指標(biāo)上反而較小，說明策略3不但在提高時(shí)效性方面優(yōu)于前兩者，在提高經(jīng)濟(jì)性方面也有一定優(yōu)勢(shì)。

但要注意的是，由于設(shè)置容量方差值較小(σi=2)，導(dǎo)致每個(gè)子路徑最多需要新派一次車，所以并沒有出現(xiàn)前文所述車輛浪費(fèi)的現(xiàn)象，當(dāng)設(shè)置方差為較大數(shù)值，例如 σi=30時(shí)，用來(lái)代表單次超出容量需增加的車次數(shù)，則策略1η1=1.015，策略2η2=1.015，策略3η3=1.042，η3較大，可見策略3確實(shí)存在車輛浪費(fèi)的現(xiàn)象。但考慮到時(shí)間和路程的節(jié)約量較多，而客戶需求量方差不會(huì)太大的實(shí)際情況，采用提前預(yù)測(cè)、實(shí)時(shí)反饋、即時(shí)發(fā)車的第三種補(bǔ)救策略在城市物流配送中顯然更具優(yōu)勢(shì)。

同時(shí)觀察最后一項(xiàng)指標(biāo)懲罰成本overC，發(fā)現(xiàn)策略3也是懲罰成本最低的方案。但是，除了計(jì)劃成本和懲罰成本之外，由于采用補(bǔ)救措施而增加的路程成本也需算進(jìn)總成本中。而由于原計(jì)劃的客戶并沒有完全服務(wù)完，新增的車也只是服務(wù)了一部分客戶，因此可認(rèn)為每條路線增加的車次成本可以忽略。同時(shí)根據(jù)4.2節(jié)參數(shù)敏感性分析結(jié)果，總成本還與服務(wù)成功概率α有關(guān)。因此，總成本應(yīng)按下式計(jì)算：

則當(dāng)設(shè)置 α 的值分別為0.2、0.4、0.5、0.6、0.8時(shí)計(jì)算得到的總成本見表7。

可知，當(dāng)按照計(jì)劃服務(wù)成功概率α=0.6時(shí)的計(jì)劃路線配送，且采用策略3作為補(bǔ)救策略時(shí)的配送總成本最小，為12 444。

5 總結(jié)與展望

本文結(jié)合現(xiàn)代城市物流配送中客戶需求隨機(jī)且有時(shí)間窗的車輛路徑問題（VRPSDTW）。構(gòu)建了機(jī)會(huì)約束混合整數(shù)規(guī)劃模型，設(shè)計(jì)了具有多種改進(jìn)策略的混合進(jìn)化算法求解該模型，并對(duì)服務(wù)失敗后的三種補(bǔ)救策略進(jìn)行隨機(jī)仿真分析，仿真實(shí)驗(yàn)表明，采用提前預(yù)測(cè)是否超出、實(shí)時(shí)反饋信息給中心、即時(shí)派出新車訪問下一點(diǎn)的補(bǔ)救策略可以最大程度保證滿足客戶時(shí)間約束，同時(shí)還具有降低配送路程的經(jīng)濟(jì)優(yōu)勢(shì)。最后通過綜合計(jì)劃成本和服務(wù)失敗的風(fēng)險(xiǎn)成本，確定了最為經(jīng)濟(jì)的計(jì)劃服務(wù)成功概率和配送策略。

總的來(lái)看，本文有以下幾處創(chuàng)新：（1）首次提出了兩種新的信息化補(bǔ)救策略，并對(duì)三種策略影響總成本的規(guī)律進(jìn)行了深入研究；（2）考慮了時(shí)間窗約束，并給出相應(yīng)的懲罰成本和總成本計(jì)算方法；（3）提出多樣化變異策略和混合選擇的Boltzmann序值選擇策略，從而提高了算法性能。

當(dāng)然，隨著客戶對(duì)服務(wù)質(zhì)量要求的提高以及隨機(jī)需求的歷史數(shù)據(jù)不易獲得的現(xiàn)實(shí)情況，更多研究者開始考慮當(dāng)所有不確定需求均可滿足的魯棒優(yōu)化問題。其重點(diǎn)和難點(diǎn)是如何定義魯棒性和不確定集合，這也是本文未來(lái)研究的重要方向。

參考文獻(xiàn)：

[1]Weyland D.Stochastic vehicle routing from theory to practice[D].Switzerland：University of Lugano，2013.

[2]Lei H，Laporte G，Guo B.The capacitated vehicle routing problem with stochastic demands and time windows[J].Computers&Operations Research，2011，38（12）：1775-1783.

[3]李川.基于混合量子進(jìn)化算法的隨機(jī)車輛路徑問題的研究[D].杭州：浙江工業(yè)大學(xué)，2012.

[4]Jr W S，Golden B L.Stochastic vehicle routing：A comprehensive approach[J].European Journal of Operational Research，1983，14（4）：371-385.

[5]Bertsimas D J.A vehicle routing problem with stochastic demand[J].Operations Research，1992，40（3）：574-585.

[6]Teodorovi? D，Pavkovi? G.A simulated annealing technique approach to the vehicle routing problem in the case of stochastic demand[J].Transportation Planning&Technology，1992，16（4）：261-273.

[7]陸琳，譚清美.一類隨機(jī)需求VRP的混合粒子群算法研究[J].系統(tǒng)工程與電子技術(shù)，2006，28（2）：244-247.

[8]趙燕偉，李川，張景玲，等.一種新的求解多目標(biāo)隨機(jī)需求車輛路徑問題的算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2012，18（3）：523-530.

[9]Yee J R，Golden B L.A note on determining operating strategies for probabilistic vehicle routing[J].Naval Research Logistics Quarterly，1980，27（1）：159-163.

[10]Erera A L，Morales J C，Savelsbergh M.The vehicle routing problem with stochastic demand and duration constraints[J].Transportation Science，2010，44（4）：474-492.

[11]Mirmohammadsadeghi S，Ahmed S.Memetic heuristic approach for solving truck and trailer routing problems with stochastic demands and time windows[J].Networks and Spatial Economics，2015，15（4）：1093-1115.

[12]Desrochers M，Lenstra J K，Savelsbergh M W P，et al.Vehicle routing with time windows：Optimization and approximation[C]//Proceedings of the Vehicle Routing：Methods&Studies，F(xiàn)，1987.

[13]Liu B.Uncertainty theory[J].Studies in Computational Intelligence，2015，154（3）：1-79.

[14]Lenstra J K，Kan A H G R.Complexity of vehicle routing and scheduling problems[J].Networks，1981，11（2）：221-227.

[15]Solomon M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations Research，1987，35（2）：254-265.

[16]Falkenauer E.A hybrid grouping genetic algorithm for bin packing[J].Journal of Heuristics，1996，2（1）：5-30.

[17]李晨，寧紅云.改進(jìn)的遺傳算法選擇算子[J].天津理工大學(xué)學(xué)報(bào)，2008，24（6）：1-4.

[18]Coello C A C.Theoretical and numerical constraint-handling techniques used with evolutionary algorithms：A survey of the state of the art[J].Computer Methods in Applied Mechanics and Engineering，2002，191（11）：1245-1287.

[19]張敏.約束優(yōu)化和多目標(biāo)優(yōu)化的進(jìn)化算法研究[D].合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2008.

[20]Pencheva T，Atanassov K，Shannon A.Modelling of a roulette wheel selection operator in genetic algorithms using generalized nets[J].International Journal Bioautomation，2009，13（4）：101-105.

[21]吳天羿，許繼恒，劉建永，等.求解有硬時(shí)間窗車輛路徑問題的改進(jìn)遺傳算法[J].系統(tǒng)工程與電子技術(shù)，2014，36（4）：708-713.