速度波動影響下對帶軟時間窗車輛路徑問題研究

魏東慶，趙 旭

（大連海事大學 交通運輸工程學院，遼寧 大連 116026）

1 引言

配送市場競爭的加劇以及客戶對配送時間準確性的要求不斷提高，給配送業務帶來了很大的影響。為了加強配送業務的管理，降低配送成本，提高配送效率，國內外對車輛路徑問題（Vehicle Routing Problem,VRP）做了大量研究。最早是由Dantzig和Ramser[1]于1959年首次提出，傳統的車輛路徑問題可解釋為一組車輛從一個配送中心出發，為多個地理位置分散的顧客點提供運輸服務，使得每個顧客的需求得到滿足，并在業務完成后所有車輛返回原配送中心，同時實現在運輸過程中車輛行駛里程最短、運輸總成本最低、耗費時間最短等目標。

由于要滿足實際生活的需求，應用到現實場景中，VRP模型也更加復雜。帶有時間窗的車輛路徑問題（VRPTW）是VRP的一個重要分支，最早由Solomon[2]于1987年提出，并給出了該問題的經典算例。經典帶時間窗的車輛路徑問題一般包含最早服務時間和最晚服務時間，表示為[ai,bi],分為帶硬時間窗、軟時間窗和模糊時間窗的VRP問題。這些問題具有確定性的假設，如需求、容量、配送中心和時間窗等信息。但實際配送業務中有些信息無法提前準確預知，例如車輛的平均行駛速度。而根據以往經驗可以大致判斷出車輛的平均行駛速度會在某一個區間內波動，由此引起車輛的行駛時間隨機，比如到某個客戶點的時間可能是20到30分鐘，所以研究平均隨機行駛時間的VRPTW問題更符合實際情況。李兵飛[3]等構建了不確定條件下速度時變VRPTW問題模型，并設計了一種改進的雙重進化人工蜂群算法求解該模型。吳瑤，馬祖軍[4]考慮實際配送中路網交通的時變性，建立了以系統總成本最小為目標、帶時間窗的易腐食品生產配送問題優化模型，并設計了一種混合遺傳算法求解。李妍峰[5]等結合交通流量特征研究行駛時間隨機的VRP。Laporte[6]等研究了隨機旅行時間的VRP，建立了三種數學規劃模型并設計了分支裁剪算法進行求解。郭強[7]等在Laporte等的研究基礎上，提出了一個考慮車輛容量有限的隨機旅行時間VRP的機會約束模型，并構造了求解該模型的遺傳算法。候鈴娟，周泓等[8]研究了不確定需求和旅行時間下的車輛路徑問題，并設計了改進遺傳算法進行求解。李鋒，魏瑩[9]等研究了隨機旅行時間的CVRP問題，并設計了混合遺傳算法進行求解。石建力，張錦[10]研究了行駛時間隨機的分批配送車輛路徑問題模型與方法，并且設計了改進的粒子群優化算法進行求解。基于以上分析發現，大多數學者在研究VRPTW問題時都是直接研究時變速度或隨機行駛時間，而不是直接考慮速度波動對配送時間以及整個配送路徑的影響，這樣就會造成數據量過大以及不夠準確，而且還會造成求解困難，降低效率。因此，本文提出了考慮平均行駛速度波動的城市快遞配送車輛路徑問題研究，引入了車輛的平均速度分布函數，根據約束條件建立相應的模型，設計改進遺傳算法進行求解，最后通過具體實例對模型進行驗證。

2 問題描述

基于配送成本最低的城市快遞車輛路徑問題可以描述為：由單一配送中心向多個具有不同需求量的客戶點派遣相同類型的車輛進行配送，考慮車輛固定成本、車輛運輸成本、時間成本（包括車輛早到的時間損失成本和車輛晚到的時間懲罰成本）。

模型的基本假設條件如下：

（1）配送中心只有1個且位置已知，需要配送的物資量充足。

（2）所有配送車輛載重量及各項性能相同。

（3）車輛的起點和終點都在配送中心。

（4）所有客戶位置、需求量及要送達的軟時間窗已知。

（5）每個客戶僅有1輛車為其配送，且所有客戶必須配送到。

（6）除配送外車輛無其它時間方面的需求。

（7）假設車輛都從配送中心出發，配送完成后返回配送中心，不考慮車輛作業時間，早到車輛只計算時間成本，不在客戶點等待。

3 模型建立

3.1 參數設置

本文研究帶有軟時間窗的VRP問題，參數設置如下：

D：配送中心，用自然數0表示；

F(V)：車輛的平均速度分布函數，在此假設服從均勻分布；

V：車輛行駛速度；

Vmax：車輛以往配送時可達到的最大平均行駛速度；

Vmin：車輛以往配送時可到達的最小平均行駛速度；

Tk：車輛k離開配送中心的時間；

Tik：車輛k到達客戶點i的時間；

g(Tik)：車輛k到達客戶點i的時間概率分布函數；

minTik：車輛正常行駛預計到達節點i的最早達到時間；

maxTik：車輛正常行駛預計到達節點i的最晚到達時間；

Δc：車輛使用的固定成本；

ce：車輛早到單位時間損失成本；

cl：車輛晚到單位時間懲罰成本；

cv：車輛的單位距離運輸成本；

djk：車輛k從配送中心到客戶點j的總行駛距離；

Wi(Tik)：車輛到達客戶點i的時間損失或懲罰成本；

xijk：決策變量，當節點i到j由車輛k配送時，xijk=1,否則為0；

yik：決策變量，當客戶點i由車輛k配送時，yik=1，否則為0。

3.2 模型建立

基于上述分析，建立以配送成本最低的路徑規劃模型，車輛固定成本、車輛運輸成本、時間成本分別記為 Z1，Z2，Z3，其中：

求解積分表達式，得到新的時間成本表達式為：

所以，目標函數及約束如下：

其中，式（1）表示車輛固定成本；式（2）表示車輛的運輸成本；式（3）表示車輛的時間損失和懲罰成本；式（4）表示配送總成本最低的目標函數；式（5）表示車輛的載重量約束；式子（6）表示每個客戶都會被服務到；式（7）、（8）表示每個客戶不會被重復訪問；式（9）表示消除子回路約束；式（10）表示車輛從配送中心出發，配送完成后返回配送中心,且每輛車只有一條線路；式（11）表示進出平衡約束；式（12）表示車輛從配送中心到j點時所行駛的距離；式（13）表示車輛k到達客戶點i的時間表達式；式（14）、（15）為模型中的自變量。

4 模型求解

本文采用遺傳算法求解，并結合模型特點對遺傳算法進行改進，具體步驟如下：

4.1 染色體編碼

染色體編碼方式的好壞在很大程度上會影響遺傳算法的運算效率和運算結果，因此選擇合適的編碼方式對于遺傳算法的實現非常重要。

本文采用較為直觀的染色體編碼方式進行編碼，具體編碼方式如下：對n個需要配送的客戶點依次進行編號，分別用自然數1,2,...,n表示，配送中心用自然數0表示，m為確定的車輛數。采用自然數編碼方式的染色體可表示為{0,C1,...,0,C2,...,C3,0,...Cn,0}。其中，Ci表示第i個客戶點。整個染色體編碼串的長度為n+m+1。在染色體中兩個0之間代表一條子路徑，即配送車輛從配送中心出發完成對最后客戶點的配送任務后返回配送中心。例如，染色體編碼串{0,1,2,3,0,4,5,6,0,7,8,9,0}表示有3輛車負責對9個客戶點進行配送任務，共有3條子路徑，具體安排如下：

子路徑1：0→1→2→3→0

子路徑2：0→4→5→6→0

子路徑3：0→7→8→9→0

4.2 初始種群的選取

對于帶時間窗的VRP問題，初始解的質量對算法迭代效率有重要影響，本文采用基于最小成本的最鄰近算法生成初始解，在此基礎上引入車輛載重限制，構造高質量的初始解。具體操作如下：

（1）路徑初始點為配送中心0，路徑的第一個客戶點是客戶中心集合{1,2,...,30}隨機取得的5個客戶點中成本最小的客戶點j，計算前一個配送中心0到當前j路徑累加的客戶需求Q1；

（2）客戶中心集合{1,2,...,30}移除j；

（3）判斷需求Q1是否超過車輛最大載重量，如果是，則路徑移除該點，客戶中心集合{1,2,...,30}加入該點j，并且配送中心0到當前j路徑隨機一個0插入前面序列，否則繼續進行；

（4）以此類推隨機選擇5個客戶點中的最小成本的點作為下一個客戶中心。

4.3 適應度函數的設定

適應度函數是評價個體優劣的重要指標，可以區分群體中個體優劣并作出取舍。適應度函數值越大的個體就說明適應環境的能力越強，表明其越優，反之則越差。遺傳算法的適應度函數可由目標函數轉換而來，由于本文配送的目標函數是配送總成本最低，因此可以選擇目標函數的倒數來作為種群個體的適應度函數fitness。當配送成本越低即目標函數值越小時，適應度函數值fitness也就越大，表明其適應性越好，被遺傳到下一代的概率也就越大。

式（16）中的Zi為染色體i對應的目標函數值。

4.4 停止準則

本文采用最大迭代次數停止準則，若迭代次數達到所設定的最大迭代次數則停止迭代，輸出運算結果。

4.5 遺傳操作

4.5.1 選擇算子。種群個體的選擇是建立在種群個體適應度評價的基礎上的，以一定的概率從種群中選擇若干個個體作為父代染色體，遵循優勝劣汰的原則。常用的方法有輪盤賭選擇、隨機競爭選擇、精英選擇、期望值方法、排序選擇法、比例選擇方法等。目前選擇算子常用基于適應度比例輪盤賭選擇法。輪盤賭方法是利用種群中的個體適應度函數值占總最大值的比例來決定選擇概率的放回式隨機采樣方法。其原理類似于多盤操作原理：將輪盤劃分為若干個區域，根據每一個區域面積的大小來標注所占的比值，當旋轉的輪盤停止時，指針所指示的區域就是所選擇的適應度值對應的個體，如圖1所示。

圖1 輪盤賭選擇法

輪盤賭選擇法可以保證種群多樣性但同時隨機性較大，難以保證算法收斂。本文結合模型分析，在輪盤賭算子的基礎上引入最優保存策略，防止適應度高的個體因為隨機的原因不被選中，避免適應度高的個體被后續的遺傳操作改變，使群體向最優化方向進化，提高收斂能力。具體選擇操作為：

（1）計算個體的適應度fi，將每一代具有最大適應度的個體直接進行保存；

（2）計算每個個體被遺傳到下一代中的概率：

（3）計算個體的累計概率：

（4）在[0,1]之間隨機產生一個均勻分布的數值t，若t＜a1,則選擇個體1進入子代種群，若ak-1＜t≤ak,選擇個體k進入子代總群。

（5）重復步驟（4），直到子代種群選擇完畢生成新一代種群，并將適應度最低的個體用父代適應度最高的染色體進行替換。

4.5.2 交叉算子。交叉操作是指兩個父代個體之間某個或某些基因位進行交換，從而生成新個體的操作。交叉操作能夠改變父代個體中的基因，是產生新個體的主要來源。在交叉操作中，種群內部染色體之間通過交叉生成新一代染色體，能在最大范圍內搜索最優解。另一方面，具有優良基因的個體需要保留，避免交叉操作破壞優良的基因。因此，本文交叉算子采用適合自然數編碼的部分映射交叉法（Partial-Mapped Crossover,PMX），具體步驟為：

（1）隨機選擇一對染色體（父代）中幾個基因的起止位置（兩染色體被選位置相同）：

（3）做沖突檢測，根據交換的兩組基因建立一個映射關系，如下所示，以1-6-3這一映射關系為例，可以看到第二步結果中子代1存在兩個基因1，這時將其通過映射關系轉變為基因3，以此類推至沒有沖突為止，最后所有沖突的基因都會經過映射，確保形成的新一代子基因無沖突。

PMX與傳統的單點交叉或多點交叉相比，在一定程度上保持了種群的多樣性，降低了算法在求解過程中易陷入局部最優解的可能，并且使算法的搜索機制較好的遍歷所有的客戶點，以尋求最優解。

4.5.3 變異算子。變異算子指的是染色體中某一位或者某幾位的基因值發生改變，轉變為其它等位基因，從而產生新的個體。變異算子能夠微調交叉算子生成新的個體，從而改善算法的局部搜索能力，增加種群的多樣性，并可以防止算法出現過早收斂。傳統的變異算子有邊界變異、均勻變異、高斯變異等。邊界變異適用于最優點或接近可行解問題，而所謂的均勻變異是滿足一定區間內均勻分布的隨機數，并以一個較小的概率來替代個體編碼中某一個基因座上的原個體基因值，該方法主要適用于算法的初級運行階段；高斯變異適用于在原個體附近的某個范圍區間進行重點搜索。本文根據自然數編碼的特點，設計的變異算子具體操作如下：

（1）首先隨機產生一個0到1之間的隨機數r；（2）判斷隨機數r是否小于等于Pm；

（3）若滿足條件（2），隨機產生兩個基因變異位；

（4）交換兩個變異位置的基因。

示例如下：

4.5.4 關鍵參數設計。在遺傳算法中，交叉概率和變異概率的選擇一定程度上會影響算法的性能，直接影響算法的收斂性。交叉概率越大，新個體產生的速度就越快。然而，交叉概率過大時遺傳模式被破壞的可能性也越大，使得具有高適應度的個體結構很快就會被破壞；如果交叉概率過小，會使搜索過程非常緩慢，甚至停滯不前。對于變異概率來說，如果其取值過小，就不易產生新的個體結構，如果其取值過大，遺傳算法就變成了純粹的隨機搜索算法。對于不同的優化問題，需要反復試驗來確定交叉概率和變異概率，一般很難找到適應于每個問題的最佳值。

Srinvivas[11]等提出了一種自適應遺傳算法，交叉和變異概率能夠隨適應度改變而自動改變。當種群各個體適應度趨于一致或者趨于局部最優時，增大交叉和變異概率。當群體適應度比較分散時，對適應度較高的個體，降低其交叉概率和變異概率，使該個體得以保護進入下一代。而對于低于平均適應度的個體，會由于相對較高的交叉和變異概率而被淘汰。自適應遺傳算法中交叉概率Pc和變異概率Pm的計算公式如下：

其中，fmax表示群體中最大適應度值；favg表示群體平均適應度值；fi表示要交叉的兩個個體中適應度值較大的；fj'表示要變異個體的適應度值，k1＜ k2，k3＜ k4。

算法流程圖如圖2所示。

5 算例分析

5.1 數據準備

為了驗證本文所建立的模型及設計算法的有效性，本文選擇了路徑規劃領域的Solomon測試集中的部分數據作為測試算例，并根據本文需求對其進行一定的數據調整和補充。算例如下：某時間段內需要配送的客戶數為30個，配送中心獲知的客戶信息表見表1，客戶編號為1,2,…,30，0表示配送中心。配送中心最多提供5臺車執行配送任務，每臺車最大承載量為300，具體信息見表1。

根據客戶的坐標信息，利用Excel繪制出了各節點的散點圖，其中帶陰影圓形標記部分為配送中心，如圖3所示。

圖2 改進遺傳算法流程圖

圖3 節點坐標散點圖

表1 客戶及配送點信息匯總

5.2 實驗環境與參數設置

根據本文設計的求解算法，在windows10系統計算機（Intel(R)Core(TM)i5 1.80GHz,內存4GB）上基于java仿真軟件進行操作，通過編程實現對模型的求解。改進遺傳算法實驗參數設定：種群規模80，最大迭代次數600，交叉概率pc上界0.85，下界0.52；變異概率上界0.2，下界0.02；在以上算例基礎上，對本文與配送成本相關參數進行設定，見表2。

表2 相關參數

5.3 測試結果與分析

獲取客戶的信息后，利用本文提出的改進遺傳算法對模型進行運算，得到的最優解為：===＞0,16,14,19,7,26,24,20,25,18,0===＞0,21,8,1,29,28,17,27,9,12,22,23,0===＞0,3,30,11,4,13,5,10,15,2,6,0。 總 配 送成本為1 552，車輛軌跡如圖4所示。

圖4 配送軌跡圖

配送車輛訪問各客戶點的順序描述如下：

路徑1：配送中心-客戶16-客戶14-客戶19-客戶7-客戶26-客戶24-客戶20-客戶25-客戶18,-配送中心；

路徑2：配送中心-客戶21-客戶8-客戶1-客戶29-客戶28-客戶17-客戶27-客戶9-客戶12-客戶22-客戶23-配送中心；

路徑3：配送中心-客戶3-客戶30-客戶11-客戶4-客戶13-客戶5-客戶10-客戶15-客戶2-客戶6-配送中心。

為了更好地了解算法的求解性能，在進行車輛配送路徑求解的過程中繪制了目標函數結果優化迭代圖，通過觀察算法求得的最優解的迭代次數對算法設計的有效性進行衡量。可以看到，在第450代時最優解已趨近收斂，如圖5所示。

5.4 影響評估

為了與車速恒定時的配送成本作比較，本文選取了運算過程中成本最低的10條路徑配送成本為基數，將10次成本的平均值作為配送成本，見表3。

圖5 最優解進化圖

表3 速度波動配送成本

假設車速波動非常小，近似為恒定，為17.5，其余數據均不變，利用本文所設計的遺傳算法進行求解，得到的最優路線為：0,6,13,5,10,2,3,8,30,11,1,4,29,28,27,22,0===＞0,9,17,25,24,7,14,18,20,12,21,26,23,15,19,16,0,最低配送成本為1 479，依然選取運算過程中成本最低的10條路徑配送成本作為基數，并求平均值，見表4。

從測試結果中的數據可以看出，在其他參數不變的條件下，當車速近似為恒定值17.5，車輛數為2，10條最低線路配送平均成本為1 526.5；當車速在區間[15,20]服從均勻分布波動時，車輛數為3，平均配送成本為1 614.9，相差約5.4%。

6 結語

本文針對帶時間窗的城市快遞配送車輛路徑問題，考慮了車輛實際行駛時平均速度存在一定波動的情況，建立了以總配送成本最低為目標函數的模型，并根據模型特點設計改進遺傳算法進行求解。通過對算例分析可知，車輛的行駛速度波動會對車輛的配送成本和線路產生一定的影響，研究成果可以為實際配送路徑規劃提供指導。為簡化計算，本文將速度波動形式設為平均分布，但是車輛實際行駛速度波動情況及分布函數需要根據以往經驗及數學理論進行判斷，有待進一步研究。