時變網絡下多車型同時取送貨車輛路徑優化

趙佳欣，雷 斌，3，王菀瑩

(1.蘭州交通大學 機電技術研究所，甘肅 蘭州 730070；2.甘肅省物流及運輸裝備信息化工程技術研究中心，甘肅 蘭州 730070；3.甘肅省物流與運輸裝備行業技術中心，甘肅 蘭州 730070)

0 引 言

隨著互聯網及電子商務的普及，顧客的物流需求越來越多樣化，從原來的單一送貨或取貨需求演變為兼備二者的物流需求。車輛在進行配送任務時，車輛行駛速度常常會因為道路交通情況改變[1]。在規劃車輛配送路線時，不僅需要考慮客戶需求還需要結合道路交通狀況。針對時變車輛路徑問題，劉思遠等[2]、張景玲等[3]采用分段函數表現車速隨時段變化，劉文琪[4]分段函數的基礎上考慮車輛行駛加速度，范厚明等[5，6]混合時間窗用多個三角函數關系式及多項式表現車速隨時間連續變化關系。目前的研究主要考慮時間對車輛行駛速度的影響，未考慮路段的影響。針對同時取送貨車輛路徑問題，現有研究主要將其與選址問題和不確定環境相結合。陳希瓊等[7，8]結合選址和路徑問題，同時考慮車輛容量和行駛里程約束，通過縮短最優目標值和行駛距離的差值進行尋優。馬艷芳等[9，10]對模糊需求和不確定環境下的同時取送貨問題進行研究。李博威等[11]引入非線性約束對時變網絡下的同時取送貨問題進行研究。大部分的研究成果都默認路網內的客戶關系單一，沒有對多樣的取送貨情況進行刻畫。本文綜合考慮路段和時段對車速的影響、不同客戶的取送貨需求及客戶關系、多種車輛的載重約束，建立時變路網下多車型同時取送貨車輛路徑模型(simultaneous pickup and delivery vehicle routing problem under time-varying road network，SPDVRPTN)。

1 模型建立

1.1 問題描述

假定道路網絡內存在一個配送中心，客戶位置已給定，每個客戶都有取送貨需求，取送貨量已知，當取貨量為0時代表該客戶點只有送貨需求，反之亦然。配送中心共有K輛車可調配，共L種類型，以l(l∈L) 表示車輛類型，每種類型車輛載重為Q1，Q2，…，QL， 即Ql(l∈L)， 車輛數量為K1，K2，…，KL， 即Kl(l∈L)， 每個客戶僅由一輛車進行服務一次。車輛從配送中心出發，在行駛過程中其行駛速度隨路段和時段的改變而改變，且不允許超載，在完成配送后返回配送中心。道路網絡內包含路段a個，將配送中心的服務時段劃分為b個。要求合理規劃車輛行駛路線，使配送總成本達到最小值。總成本包括車輛固定成本、車輛派遣成本以及未滿足客戶時效要求產生的時間懲罰費用。

1.2 參數及變量說明

dij客戶點i到客戶點j的運輸距離

pj客戶點j的取貨量

dj客戶點j的送貨量

A共有a個路段

B將配送中心服務時段劃分為b個

Sb第b個時間段的開始時間

Eb第b個時間段的結束時間

yij車輛k從客戶點i到客戶點j路徑中的送貨量

zij車輛k從客戶點i到客戶點j路徑中的取貨量

QL類型為L的車輛最大載重

tij車輛從客戶i到客戶點j的行駛時間

ej客戶點j的期望最早服務時間

lj客戶點j的期望最晚服務時間

e0送中心的最早服務時間

l0配送中心的最晚服務時間

tj車輛在客戶點j的取送貨時間

wj車輛到達客戶點j的時間

wj0車輛從客戶點j返回配送中心的時間

Pi(ti) 時間窗懲罰函數

1.3 考慮多種取送貨情況

針對同時取送貨問題，從路網內的客戶間關系出發，考慮以下兩種情況：

(1)路網內客戶間不存在服務與被服務關系：所有客戶的送貨量等于從配送中心出發的車輛的總載貨量，返回配送中心的車輛載貨總量為所有客戶的總取貨量，此時車輛無固定服務順序。

(2)路網內存在客戶間服務與被服務關系：在特定客戶取到的貨物能夠為路網內其他客戶進行送貨服務。假設存在客戶集m=(1，2，3，…，m) 為客戶集n=(1，2，…，n) 服務，客戶集m的供給能力能夠滿足客戶集n的需求。車輛在配送時需先對客戶集m中的客戶進行服務，再對客戶集n中的客戶進行服務。

綜合考慮以上兩種情況，將路網內的客戶編號為 (1，2，3，…，m，m+1，…，m+n)， 對網絡內流量設定以下約束條件

(1)

(2)

(3)

(4)

(5)

(6)

式(1)和式(2)表示從配送中心出發的載貨量大于等于前m個客戶點的總送貨量并且小于等于總送貨量；式(3)表示總取貨量小于等于返回配送中心的總載貨量；式(4)表示前m個客戶點的取貨量大于等于后n個客戶點的送貨量；式(5)和式(6)保證客戶服務順序符合規定。

1.4 時變網絡下行駛時間計算

本文采用多個分段函數表現不同道路下的速度隨時間變化的曲線，定義出不同路段不同時段的車輛行駛速度集F，如式(7)所示，每個路段下車輛行駛速度隨時段變化

(7)

假設車輛從客戶點i行駛到客戶點j時處于路段a中，此時存在跨時段行駛和不跨時段行駛兩種情況，非跨時段行駛時，行駛時間計算公式如式(8)所示

(8)

跨時段行駛時，按式(9)計算到達下一節點的時間

(9)

若tj仍處于時段[tb-1，tb]， 則根據式(10)計算車輛在下個時段仍需行駛的距離。再根據行駛距離更新行駛時間，計算公式如式(11)所示，當tj≤tb+1時停止計算，否則繼續上述步驟

(10)

(11)

1.5 模型建立

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

ai+ti+tij-M(1-xijk)≤aj

(20)

(21)

tjo≤l0

(22)

式(12)為目標函數，以車輛租賃成本、派遣成本和時間懲罰費用最小為總目標；式(13)保證車輛從配送中心出發去往一條路徑；式(14)表示最多使用k輛車；式(15)為車輛最大容量限制；式(16)和式(17)為取送貨量定義式；式(18)保證車輛在客戶點a完成服務后必須前往下一客戶點；式(19)表示懲罰費用函數；式(20)表示車輛k由客戶點i行駛到下一個客戶點時的到達時間關系；式(21)為流量平衡約束；式(22)保證車輛需在配送中心開放的時段進行服務。

2 改進的自適應遺傳算法設計

遺傳算法(genetic algorithm，GA)作為求解VRP問題的常用算法已被多次驗證其有效性，具有較強的全局搜索能力，但達到一定迭代次數后求解效率低下且易出現早熟。本文涉及問題考慮了包括了時變網絡、多車型、同時取送貨等約束，問題復雜，需要在標準遺傳算法的基礎上進行改進，提高求解效率和精確性。根據本文所建SPDVRPTN模型特點，主要從以下兩個方面進行改進：①自適應遺傳算法(adaptive genetic algorithm)與普通遺傳算法相比能夠通過調整交叉變異概率使在求解次數到達一定規模時引導算法往更優的方向進化[12]，交叉變異概率在算法迭代時根據迭代情況發生自適應改變。②針對遺傳算法容易出現早熟的問題，對算法中的選擇、變異算子進行改進，引導其搜索方向，提高算法搜索能力。改進的自適應遺傳算法通過其自適應機制和改進后的選擇、變異算子提高求解效率和求解精度。

2.1 編碼與初始種群生成

本文采用整數編碼。隨機生成n條長度為客戶點數的染色體，引入貪婪算法的思想，選擇容量約束最大的車輛按隨機生成的客戶排列順序先進行取送貨，直到其達到容量約束，再選擇容量約束次之的車輛進行服務，直到所有客戶點都被服務完畢。每輛車在開始服務時，在開始服務的客戶點前插入數字0，代表此時車輛從配送中心出發。遺傳算法編碼及解碼如圖1所示。本文建立的SPDVRPTN模型存在固定車輛服務順序即需先對客戶集m服務再對客戶集n服務。將兩個客戶集同時編碼時會因交叉變異產生許多不可行解，導致算法效率降低。因此對兩類客戶采用分段編碼，客戶集m在前，客戶集n在后，二者各自交叉變異互不影響。

圖1 編碼與解碼

2.2 適應度函數與選擇策略

本文建立模型的目標為總成本最小，適應度函數的取值為總成本的倒數。在選擇操作時，本文結合精英保留和輪盤賭策略，保留每次迭代前m個精英個體，將其復制到下一代，非精英個體進行輪盤賭選擇，保留種群中的優秀個體，使其不因交叉變異而丟失，從而提高算法的求解速率。

2.3 交叉與變異操作

2.3.1 自適應策略

本文采用文獻[13]提出的正弦自適應遺傳算法，將交叉概率與當代遺傳中種群適應度值的平均值和最大值相聯系。算法交叉變異概率按式(23)和式(24)計算

(23)

(24)

其中，Pc、Pm為交叉、變異概率，Pc1、Pc2分別為最大最小交叉概率值，Pm1、Pm2為最大最小變異概率值Pc1、Pc2∈[0.4，0.99]，Pm1、Pm2∈[0.001，0.1]，fm為最大適應度值，f′為個體適應度值，fa為種群平均適應度值。

2.3.2 交叉操作

本文采用部分匹配交叉。遺傳算法進行交叉后容易產生無效個體，部分匹配交叉能夠通過建立不同染色體基因之間的映射關系對交叉后的染色體進行修復。這里選用交叉點為2的部分匹配交叉，具體操作如圖2所示。

2.3.3 變異操作

文獻[14]在用禁忌搜索算法進行車輛路徑規劃時運用了一個混合算子，豐富算法的搜索方向，從而避免算法陷入局部最優。本文將該混合算子作為IAGA的變異算子，即在變異時，隨機從以下4種變異方式中選擇一種執行。

(1)進化逆轉算子：染色體在隨機的兩個客戶點間發生斷裂，逆轉其基因順序后再插入，并且逆轉后適應度值有所提高的才接受下來，否則逆轉無效，如圖3所示。

圖3 進化逆轉算子

(2)1-opt交換搜索算子：隨機截取一個基因插入到染色體中的另一個位置，如圖4所示。

圖4 1-opt交換搜索算子

(3)2-opt交換搜索算子：隨機選擇兩個基因交換其位置，如圖5所示。

圖5 2-opt交換搜索算子

(4)3-opt交換搜索算子：隨機選擇3個基因從前往后依次調換位置，如圖6所示。

圖6 3-opt交換搜索算子

3 仿真實驗

3.1 仿真數據與參數設置

本文采用solomn100數據集中的c101進行改造。假設路網內有一個編號為0的配送中心和25個客戶點，配送中心及客戶點坐標采用原數據。客戶間存在服務與被服務關系，車輛在客戶編號為1-13的客戶處取貨后，為后續編號為14-25的客戶送貨，算例構建時需保證客戶接受服務的時間在配送中心的服務時間窗內，編號為1-13的客戶其取貨量大于編號14-25客戶的送貨量，確保供大于需，詳細信息見表1。時間窗的開始時間以早上8點為計算的零時刻，配送中心時段為早8點至下午14點，共6個小時，360分鐘。以客戶1舉例，其時間窗為152-199，即早上10點32分至11點19分。車輛參數見表2，客戶的時間懲罰系p1=3，p2=5， 將不同時段不同路段下的行駛速度用多個分段函數表示，并整理為表3。

表1 客戶信息

表2 車輛參數

表3 不同路段時段下的車輛行駛速度集/(km/h)

進行實驗時從3個維度驗證模型和算法有效性：①將IAGA算法用于求解本文SPDVRPTN模型，驗證算法的有效性；②將IAGA算法與其它智能算法在不同客戶規模下的求解結果對比，驗證本文設計算法的優越性；③將本文的多車型配送與單車型配送成本對比，驗證多車型配送的優越性。

程序采用matlabR2017編程實現，運行環境為主頻2.7 GHz的Intel Core i7處理器。算法參數設置如下：種群大小為200，迭代次數為500，算法代溝為0.9，交叉變異概率為Pc1=[0.5，0.8]，Pc2=[0.4，0.6]，Pm1=[0.03，0.05]，Pm2=[0.02，0.1]。

3.2 求解結果分析

利用本文設計的改進的自適應遺傳算法求解，得到最優成本配送方案。求解結果共有6條配送路徑，調用車輛6臺，其中類型一4臺，類型二和類型三分別1臺，各子路徑距離與費用見表4。配送路線如圖7所示，算法迭代過程如圖8所示。可以看出，算法隨著迭代次數的增加呈現快速收斂，求得最優解為6438.2元，車輛行駛總距離為413 km。算法共運行20次，平均運行時間為81.3 s。說明設計的算法對模型有較好的求解效果且具有良好的收斂性。

表4 最優成本配送方案

圖7 最優配送方案路線

圖8 自適應遺傳算法迭代趨勢

3.3 單車型和多車型對比

為驗證多車型配送對目標成本的影響，針對此算例進行單車型與多車型配送求解結果的對比分析，車輛參數參照上文。Pt表示時間窗懲罰成本，Cr表示車輛固定費用，Ct表示車輛派遣成本，C表示總成本，GAP表示單車型配送各項成本與多車型配送各項成本的相對誤差。

由表5知，多車型配送相比于單車型配送在降低成本方面具有更大優勢。單獨使用車型一時，由于車輛容量小，導致使用車輛數大大增加。單獨使用車型二時，配送成本升高了8.6%，單獨使用類型三的車輛進行派送時，其配送成本最高。綜合來看，多車型配送成本最低，驗證了本文所建多車型模型的有效性。

表5 單車型與多車型配送成本對比

3.4 智能算法對比分析

本文將IAGA與文獻[15]中的改進蟻群算法(improved ant colony algorithm，IACO)及遺傳算法(GA)的在不同客戶規模下的最小目標值(Best)、平均目標值(Avg)、計算時間(t)、標準差(Dev)對比，以驗證本文算法的有效性。GAP代表本文設計的IAGA算法與IACO、GA最小目標值的偏差。IACO的參數設置：螞蟻數m=30， 信息素強度q0=20，α=2，β=3， 信息素濃度相對重要性為1。GA參數設置：種群大小200，pc=0.8，pm=0.8。 算法分別運行20次，最大迭代次數為500次。

IAGA求解結果見表6。IACO與IAGA求解結果對比見表7。可以看出，IAGA在保持良好求解精度的同時有效縮短了求解時間，提升求解效率，算法穩定性較好。GA與IAGA求解結果對比見表8。易發現本文設計的IAGA算法相比傳統遺傳算法在求解精度和魯棒性方面都有明顯提升，算法性能增強。但因為提升了算法復雜度，隨著客戶規模的擴大，求解時間有所增加。總的來說，本文設計的IAGA算法在求解本文研究問題時具有較好的精確性和魯棒性，求解效率較高。

表6 IAGA求解結果

表8 IAGA與GA求解結果對比

4 結束語

為提升配送服務質量，需結合現實環境中影響車輛配送的因素進行路線安排。本文綜合考慮了路段和時段對車速的影響，定義出不同路段不同時段下的車輛行駛速度，結合客戶的取送貨需求，站在客戶關系角度出發，考慮多種取送貨情況和車型多樣性，建立時變網絡下同時取送貨車輛的車輛路徑優化模型。根據模型特點，設計改進的自適應遺傳算法進行求解。研究結果表明：本文考慮的多車型配送能夠有效降低配送成本，設計的改進自適應遺傳算法具有較好的性能，建立的模型考慮車速變化和不同取送貨情況，約束復雜，求解難度增加，但更符合實際。期望本文能為企業提升配送質量，節約配送成本提供參考。