鄧 燁，朱萬紅，唐 建

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)鈔車對銀行網(wǎng)點(diǎn)進(jìn)行存取款服務(wù)，應(yīng)急中心對災(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問題一般不考慮客戶的時間窗約束，而在現(xiàn)實(shí)中，是否滿足時間窗約束往往也是評價服務(wù)質(zhì)量的重要標(biāo)準(zhǔn)之一，因此需要加以考慮[2]。同時，針對需求超出容量約束時的傳統(tǒng)補(bǔ)救策略由于偏于保守，往往造成違反客戶時間窗的風(fēng)險成本較高，因此需要提出更加敏捷可靠的補(bǔ)救策略。

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

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

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

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

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

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

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

2.2 符號說明

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

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

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

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

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

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

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

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

約束條件：

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

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ù)要求高，計算量很大。尤其是當(dāng)問題規(guī)模也很大的時候，隨機(jī)模擬的計算時間會非常長；（2）計算結(jié)果不穩(wěn)定，即使經(jīng)過大量的仿真，也不能保證得到理論最優(yōu)解。因此，本文假設(shè)需求變量服從獨(dú)立正態(tài)分布，這樣就可以基于不確定原理[13]，將機(jī)會約束式（2）轉(zhuǎn)化為確定等價形式進(jìn)行求解，見式（9）。

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

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

2.4.2 補(bǔ)救策略分析

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

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

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

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

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

3 算法設(shè)計

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

帶有時間窗車輛路徑問題（VRPTW）是一類組合優(yōu)化問題，可行解的數(shù)量會隨著問題的規(guī)模呈指數(shù)增長，是典型的NP-hard問題[14]，本文研究的VRPSDTW問題同樣如此，當(dāng)問題規(guī)模較大時，傳統(tǒng)的精確算法在有限時間內(nèi)已不可能求解，必須設(shè)計智能算法進(jìn)行求解。為了提高算法效率，本文設(shè)計了包括最近鄰初始化算法、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)，每個0后面代表一條配送路線，有多少0，就代表有幾條配送路線。

圖2 染色體編碼案例

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

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

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

3.3 Falkenauer交叉算子

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

圖3 Falkenauer交叉算子示意圖

3.4 多樣化變異算子

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

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

傳統(tǒng)的選擇策略多是直接對子代進(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）對每個序數(shù)對應(yīng)的個體賦給概率值：

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

圖4 六種變異算子示意圖

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

3.6 約束處理方法

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

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

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

4 實(shí)驗與分析

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

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

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

4.1.1 變異操作對比

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

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

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

4.1.2 選擇策略對比

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

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

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

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

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

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

4.1.3 算法綜合性能對比

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 總結(jié)與展望

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

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

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

參考文獻(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ī)集成制造系統(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é)報，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].合肥：中國科學(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]吳天羿，許繼恒，劉建永，等.求解有硬時間窗車輛路徑問題的改進(jìn)遺傳算法[J].系統(tǒng)工程與電子技術(shù)，2014，36（4）：708-713.