隨機需求有時間窗的路徑優(yōu)化及補救策略研究

鄧 燁，朱萬紅，唐 建

DENG Ye,ZHU Wanhong,TANG Jian

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

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

1 引言

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

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

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

2 問題描述及數學模型

2.1 問題假設及目標

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

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

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

2.2 符號說明

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

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

2.3 數學模型

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

（1）二進制決策變量：

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

最終，可以構建VRPSDTW為一個機會約束混合整數規(guī)劃數學模型。

目標函數：

約束條件：

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

2.4 模型轉化與分析

2.4.1 隨機約束轉化

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

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

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

2.4.2 補救策略分析

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

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

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

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

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

3 算法設計

3.1 混合進化算法

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

圖1 混合進化算法流程圖

3.2 編碼與最近鄰初始化

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

圖2 染色體編碼案例

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

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

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

3.3 Falkenauer交叉算子

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

圖3 Falkenauer交叉算子示意圖

3.4 多樣化變異算子

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

3.5 改進選擇策略

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

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

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

圖4 六種變異算子示意圖

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

3.6 約束處理方法

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

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

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

4 實驗與分析

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

4.1 基于確定需求模型的算法改進實驗

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

4.1.1 變異操作對比

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

圖5 變異算子改進結果對比圖

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

4.1.2 選擇策略對比

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

圖6 選擇算子改進結果對比圖

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

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

圖7 保留策略改進結果對比圖

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

4.1.3 算法綜合性能對比

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

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

表1 算法綜合性能對比結果表

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

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

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

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

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

為分析計劃配送總成本對成功服務概率α的敏感性，再分別設置α的值為0.2、0.4、0.6、0.8，則得到對應的計劃配送成本結果見表3。

表3 計劃配送成本結果表

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

4.3 補救策略仿真實驗及分析

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

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

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

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

表7 不同α時總成本優(yōu)化結果表

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

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

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

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

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

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

5 總結與展望

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

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

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

參考文獻：

[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]李川.基于混合量子進化算法的隨機車輛路徑問題的研究[D].杭州：浙江工業(yè)大學，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]陸琳，譚清美.一類隨機需求VRP的混合粒子群算法研究[J].系統(tǒng)工程與電子技術，2006，28（2）：244-247.

[8]趙燕偉，李川，張景玲，等.一種新的求解多目標隨機需求車輛路徑問題的算法[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].天津理工大學學報，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)化和多目標優(yōu)化的進化算法研究[D].合肥：中國科學技術大學，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].系統(tǒng)工程與電子技術，2014，36（4）：708-713.