旅行時間不確定下的車輛路徑問題研究

武小平，寇藝檳，樊相宇

（西安郵電大學 現(xiàn)代郵政學院 郵政研究院，西安 710061）

0 引言

近年來電子商務的興起，網(wǎng)購的人數(shù)和線上訂單量不斷增加，線下需要將貨物安全及時的送達客戶必須有物流配送的支持。而現(xiàn)實配送過程中路況復雜，交通狀況、節(jié)點客戶需求變化、車輛故障等情況的發(fā)生難以預測，從而使得配送狀況存在不穩(wěn)定性，在這種情況下，配送員到達節(jié)點的時間難以把握，使得配送需求點的時間窗無法完全滿足，從而降低客戶滿意度，同時這些不確定狀況也會使決策者在配送路徑規(guī)劃時面臨干擾。因此有必要研究不確定狀況下的配送路徑優(yōu)化問題，從而盡可能的降低成本并滿足客戶需求。

在實際配送過程遇到的不確定環(huán)境主要有兩類，一是交通狀況，天氣，車輛故障等因素導致的時間不確定，二是需求的不確定，包括需求節(jié)點的增減，需求量的變化等，目前針對這兩類不確定因素下的配送路徑選擇優(yōu)化問題已取得一定進展。張婷[1]研究了信息在配送過程中動態(tài)變化的城市配送車輛路徑優(yōu)化問題，通過引入虛擬變量，將動態(tài)問題轉化為靜態(tài)問題，最后用遺傳算法尋找出最優(yōu)配送路徑。李妍峰[2]等研究了在實時交通信息下的車輛路徑優(yōu)化問題，其中考慮了偶發(fā)性交通擁堵，設計了在路徑關鍵點更新路線的機制。張文博[3]針對需求點及時間窗變動下的車輛路徑問題，以配送成本最小化和服務準時性為優(yōu)化目標，提出初始階段和動態(tài)優(yōu)化階段的兩階段優(yōu)化策略，結合遺傳算法和模擬退火算法尋找出最優(yōu)路徑方案。王海軍[4]在應急物流的背景下，考慮應急物流需求量及運輸時間的不確定，利用機會約束的理論建立了配送選址-路徑問題的隨機規(guī)劃模型，并利用遺傳算法進行求解，最終得出配送路徑。王淑云[5]探討了需求變動下的冷鏈物流帶時間窗車輛路徑優(yōu)化問題，比較了需求確定性模型和需求隨機性模型下路徑和成本的差異，根據(jù)需求變動的幅度選擇合適的模型來指導決策，并給出降低需求不確定的對策。

上述學者大多采用概率論，動態(tài)規(guī)劃法來處理配送過程中遇到的配送時間不確定，需求點變化，需求量增減等不確定信息，但是現(xiàn)實中這類不確定事件的發(fā)生缺乏足夠的樣本數(shù)據(jù)來預測其發(fā)生的可能性，需要借助經(jīng)驗或專家意見來估計事件發(fā)生的把握程度。基于這種情況，Liu B[6]在2007年提出了不確定理論，可以借助該理論來描述在沒有歷史數(shù)據(jù)或實驗數(shù)據(jù)作為參考而只能依靠來自專家經(jīng)驗數(shù)據(jù)的非精確信息。Liu B[7～9]在2009年把不確定理論應用于實際，提出應用該理論可以解決的一些實際問題。自此，利用不確定理論解決現(xiàn)實中存在的不確定問題得到了眾多學者的關注，已有學者應用該理論解決不確定環(huán)境下的網(wǎng)絡優(yōu)化問題。Zhang B等[10]建立了中國郵路問題的不確定規(guī)劃模型。Gao Y[11]研究了不確定條件下的最短路徑問題。吳攀峰[12]等研究了以超市日需求量和車輛行駛時間為不確定變量下的超市物流配送問題，建立不確定機會約束模型，對模型進行轉化并設計算法進行求解，最終找出路徑。

本文主要研究以旅行時間作為不確定變量的帶時間窗配送路徑優(yōu)化問題，以配送成本優(yōu)化目標并建立不確定規(guī)劃模型，利用不確定理論，將網(wǎng)絡中不確定變量進行轉化，再運用遺傳算法對模型進行求解。

1 問題描述及數(shù)學符號說明

1.1 問題描述

不確定旅行時間下的車輛路徑優(yōu)化問題可描述為：一個配送中心負責多個配送需求點的物流服務，每個配送點都有時間窗要求，該配送中心有多輛車且每輛車都有載貨量的限制，每一輛車都從這一配送中心出發(fā)，服務完所有配送點后回到該配送中心，每輛車所經(jīng)歷的配送點的物流需求總和不能超過該車輛的載貨量限制，同時每個需求點只能被一個車輛所訪問，最終使得所有配送網(wǎng)點的需求都被滿足。由于在實際配送過程中會受到交通，天氣狀況等因素的影響，使得車輛在節(jié)點之間的旅行時間是不確定的，同時到達配送點的時間也是不確定的，本文就基于時間的不確定因素，考慮如何安排車輛配送路線，使得所有車輛在時間窗內(nèi)將貨物送到客戶手中并使得配送成本較低。

1.2 數(shù)學符號說明

上述問題描述的數(shù)學語言表達：V=（V0，V1，…，Vn）為配送網(wǎng)絡中所有節(jié)點的集合，其中V0表示配送中心，V＇=（V1，V2，…，Vn）表示n個配送需求點的集合，i，j表示配送網(wǎng)絡中節(jié)點的下標，ωij={i，j=0，1，2，…，n}表示節(jié)點i到j的不確定旅行時間，其不確定分布記為Φij，旅行時間的期望置信度設為α，tij（i，j=0，1，2，…，n）表示在期望置信度下的節(jié)點i到j的旅行時間，dij={i，j=0，1，2，…，n}表示節(jié)點i到j的距離，c表示車輛單位距離的運輸成本，qi（i=0，1，2，…，n）表示配送點的需求量，[ai，bi]表示配送點顧客需求的時間窗，其中ai表示顧客期望的最早送達時間，bi表示顧客所能容忍的最晚送達時間，ts表示在配送需求點處理一件貨物的平均服務時間，tj表示車輛到達配送節(jié)點的時間，則tj=ti+qits+tij。配送中心有m輛車，k表示車輛，那么k＇={ki|i=1，2，…，m}表示配送車輛的集合，每輛車的載貨量都相同且用Q表示。

利用罰函數(shù)的思想來處理時間窗約束，若車輛到達配送點的時間早于時間ai，則會延長配送時間，若車輛到達配送點的時間晚于bi，則顧客需要等待，客戶滿意度降低，因此早到和晚到的單位懲罰成本分別為e1和e2，且e2大于e1。

xik表示車輛k為配送點Vi服務，yijk表示車輛k從節(jié)點Vi行駛到Vj，兩者都為決策變量，xik=1，說明車輛k服務于配送點Vi，否則Xik=0；yijk=1（i≠j），說明車輛k從節(jié)點Vi行駛到Vj，否則yijk=0。

2 模型建立

2.1 不確定理論知識

Liu B[5]提出不確定理論，給出不確定測度、不確定分布、逆不確定分布的定義。

定義1：設T是一個非空集合，L是T上的σ代數(shù)，L中的每個元素Λ稱為事件，如果一個從L到實數(shù)集R的集函數(shù)滿足以下公理：

公理1：規(guī)范性，對于全集T，有M{T}=1；

公理2：對偶性，對于任意的事件Λ，有M{Λ}+M{ΛC}=1；

公理3：次可加性，對于可數(shù)的事件序列{Λ}，有M{∑Λi}≤∑M{Λi}；

則稱M為不確定測度，可知0≤M{Λ}≤1。

定義2：對于不確定變量ζ，它的不確定分布定義為Φ(α)=M{ζ≤α)，其中α?R，它的反函數(shù)即為不確定分布的逆分布，記為Φ-1(α)。

2.2 模型建立

約束條件中配送點之間的旅行時間是一個不確定變量，各個不確定旅行時間之間是相互獨立的，且決策必須在不確定變量實現(xiàn)之前作出，可以用不確定規(guī)劃來解決，給不確定變量一個期望的置信度，從而根據(jù)變量的分布狀況來指導決策。建立的模型如下：

目標函數(shù)式(1)表示總成本最小，包括車輛的運輸成本和違反時間窗的懲罰成本，式(2)表示車輛在節(jié)點之間旅行時間的分布狀況，約束式(3)表示車輛守恒限制，即m個車輛都是從配送中心出發(fā)并最終回到配送中心，約束式(4)表示車的載貨量限制，式(5)表示每個配送點經(jīng)過且只經(jīng)過一次，顧客節(jié)點不能被重復訪問，式(6)表示節(jié)點時間窗限制，式(7)、式(8)表示決策變量的取值。

根據(jù)不確定分布的定義2，約束條件式(2)可轉化為：

進一步利用不確定變量逆分布的定義3，式(9)可轉化為：

3 模型求解步驟

本文模型中含有不確定變量，需要對模型進行求解，首先需要估計不確定變量所服從的分布狀況，進而利用不確定理論得出其逆不確定分布，可以引用Liu B[7]提出的99表算法來求解逆分布。為了簡化，本文假設不確定旅行時間服從正態(tài)不確定分布。

步驟1：不確定旅行時間服從正態(tài)不確定分布

盡管現(xiàn)實中節(jié)點之間的旅行時間是不確定的，但可以根據(jù)經(jīng)驗或專家意見預測出其大致趨勢，一般而言，所選擇路徑的可信度越強，所要花費的旅行時間就越長，即旅行時間與置信度呈遞增關系。假設旅行時間服從正態(tài)不確定分布，正態(tài)不確定分布的函數(shù)及逆分布如下：

1）正態(tài)不確定分布

若不確定變量ξ具有如下正態(tài)不確定分布函數(shù)：

則稱ξ為正態(tài)不確定變量，其逆不確定分布如下：

步驟2：計算逆分布的值

步驟3：遺傳算法設計

目前針對此類問題模型的求解主要采用啟發(fā)式算法，而遺傳算法是啟發(fā)式算法的一種，是借鑒生物界適者生存，優(yōu)勝劣汰的遺傳機制演化而來的隨機搜索方法，具有較快的運算速度和更好的全局尋優(yōu)能力。

1）染色體編碼

采用自然數(shù)編碼，配送需求點編號為1，2，…，n，將其從小到大進行排列生成一條配送點染色體，再對每個配送點隨機安排一輛車，生成一條車輛染色體。以3個車輛（編號為1～3）9個配送點（編號為1～9）為例，隨機生成的一個可行解如圖1所示。

圖1 3個車輛9個配送點的染色體編碼示例

由圖1可知，車輛1的配送路徑為：1-4-6，車輛2的路徑為：2-3-7，車輛3的路徑為：5-8-9。

2）生成初始種群

初始種群的規(guī)模為S，其中包括了N條染色體。把n個配送點進行排列，首先給車輛一分配其所要服務的配送點，同時考慮車的載貨量要大于其所服務配送點的需求之和，從而生成車輛一的配送路徑，剔除掉車輛一所服務的配送點后，在剩下的配送點里按照同樣的方法得出車輛二的配送路徑，直到所有的配送點都被服務，從而得到第一條車輛染色體，再重復以上操作生成N條染色體構成初始種群。

3）選擇

遺傳算法中利用適應度函數(shù)來評估一個個體解的好壞，本文希望找到成本最小的路徑，為了將其轉化為最大值問題，因此選取目標函數(shù)的倒數(shù)作為適應度函數(shù)。根據(jù)適應度函數(shù)計算出每個個體的適應度，采用精英法，選取適應值最大的個體直接保留到下一代，再利用輪盤賭法選擇其他的父代染色體進入下一代。

4）交叉

兩個待交叉的不同的染色體根據(jù)交叉概率按某種方式交換其部分基因，Pc記為交叉概率，對于選擇的兩個車輛染色體A1和B1，隨機產(chǎn)生兩個交叉點，將兩個交叉點之間的基因移動另一個染色體的頭部，再將編號相同的基因刪掉，即交叉完產(chǎn)生新的染色體A2和B2。

5）變異

變異操作能夠保證種群的多樣性，避免過早收斂，Pm記為變異概率，采用互換算子，即在一條染色體上隨機選取兩個非零變異位置，將其基因進行交換。

6）算法終止

經(jīng)過一次迭代后，產(chǎn)生新的種群作為下次迭代的父代，隨著遺傳算法的進行，種族的基因差異會趨于一致，并且滿足迭代次數(shù)，此時算法終止，否則回到選擇操作繼續(xù)迭代。

表1 節(jié)點之間旅行時間

4 算例分析

4.1 算例描述

某一配送中心（編號為0）負責15個客戶節(jié)點的配送任務，節(jié)點之間的旅行時間服從正態(tài)不確定分布tij～N（dij/50，0.2），取置信度α=0.95，得到節(jié)點之間的旅行時間如表1所示，配送中心有6輛車，車的載貨量都為100，配送點服務一件需求的平均時間是2分鐘，車輛單位距離運輸成本c=5元/km，各配送點的信息如表2所示，配送節(jié)點之間的距離采用歐式距離。

表2 配送節(jié)點信息

表2 （續(xù)）

4.2 結果分析

利用MATLAB遺傳工具箱進行仿真，設置種群規(guī)模S=100，迭代次數(shù)為300次，交叉概率Pc=0.8，變異概

表3 最優(yōu)路徑結果分析

率Pm=0.1，算例計算20次，對運行結果統(tǒng)計分析可得，平均運行時間501.15s，總配送成本的平均值為8040.05元，平均行駛距離1551.85km。目標值收斂趨勢如圖2所示，在迭代前期，曲線下降較快，遺傳算法的搜索速度較快，隨著迭代次數(shù)的增加，曲線逐漸趨于平穩(wěn)，最優(yōu)解逐漸收斂，在迭代100次以后，曲線穩(wěn)定到某一固定水平，進而得到最優(yōu)解。

圖2 目標值收斂趨勢圖

最優(yōu)的配送路徑及結果分析如下。

圖3 最優(yōu)配送路徑圖

車輛的最優(yōu)路徑如表3所示，此時總配送成本為7579.8元，總配送距離為1434.4km。

5 結論

在不確定理論的框架下，研究了旅行時間不確定因素下的帶時間窗的車輛路徑選擇問題，建立了以配送成本最小為優(yōu)化目標的不確定規(guī)劃模型，并運用遺傳算法進行求解，最后給出數(shù)值例子，通過計算機仿真，從而找到最優(yōu)的配送路徑。實際的配送過程中會有多種不確定情況，進一步研究還可以考慮需求點變動，需求量增減等多種不確定情形下的路徑優(yōu)化問題，使之更接近實際。