基于動態需求的多車型車輛配送路徑優化研究

曹炳汝，王 霞

（江南大學商學院，無錫 214122）

0 引言

車輛路徑問題[1]（Vehicle Routing Problem，VRP）自1959年Dantzing和Ramser提出以來，備受廣大研究者的關注，一直是研究的熱點。假定在進行配送路徑規劃之前，客戶所在位置、客戶指定的服務時間窗、需要提供配送服務的貨物重量、體積、行駛速度、在客戶地點服務的時間等都是確定的，在這種情況下，實施的車輛調度方案一般是固定且不會變化的，這類運輸問題被稱為靜態車輛路徑優化問題。事實上，在物流配送中可能出現新增客戶點、原客戶點的需求增多、減少甚至變為零、交通堵塞或天氣狀況等情況需要重新調整配送路線，這類問題被稱為動態車輛路徑優化問題（Dynamic Vehicle Routing Problem，DVRP）。動態車輛路徑優化問題研究的是動態變化的情況，更加符合實際情況，因而逐漸成為研究的熱點。實際上，大多數物流公司通過歷史調度經驗進行車輛的調度，面對實時變化的客戶需求時，即使借助GPS等先進的系統可能也沒有辦法在短時間內重新規劃路徑以滿足客戶需求量和服務時間要求。在客戶的動態需求下，如何決策使得運輸成本最小化是物流公司亟待解決的問題。

張景玲等[2]為解決如果通過實時調度將動態需求的客戶插入到初始配送路線中，考慮到配送中心擁有多種型號的車輛，建立了基于多車型的動態需求模型，提出了混合量子進化算法進行求解。葛顯龍[3]根據動態車輛路徑問題的產生的原因提出了時間軸概念，根據配送網絡的服務狀態找到關鍵點，建立了動態調度問題模型，并提出了云遺傳算法。Goodson J C等[4]提出了一種基于固定路徑的策略，以此來獲得車輛路徑問題的動態解。葛顯龍等[5]考慮到了配送車輛從多個配送中心出發，建立了多車型動態需求模型，并利用云遺傳算法進行求解。Jabali O等[6]提出了一種基于一般局部路徑生成的三種下界泛函數，并給出了識別違規割集的精確分離過程。Zhang Q和Yan R[7]在隨機研究隨機需求車輛路徑問題及其模型時，將免疫算法和遺傳算法結合，提出了一種混合式的算法。Sarasola B等[8]提出了適用于動態設置的可變鄰域搜索算法（VNS），并發現在需求偏差較小的情況下，基于采樣的動態VNS方法能獲得較好的結果。Zhang J[9]等考慮了帶時間窗的需求隨機的車輛路徑問題，建立了三種概率模型，并提出了預防性再儲備策略。Lingkai L等[10]在需求預測和電池數量分析的基礎上，建立了基于電池交換站的初始模型和實時調度模型。Hernandez F等[11]根據需求是隨機不確定的特點，建立了兩階段模型，第一階段規劃模型，第二階段執行模型，若在執行過程中由于隨機需求的出現，車輛無法滿足客戶的需求，則需要回配送中心進行補貨。Hu C[12]等研究了需求和旅行時間不確定性條件下具有硬時間窗的車輛路徑問題，并設計了一種基于改進的自適應可變鄰域搜索啟發式的兩階段算法。

在多車型車輛調度研究中，葛顯龍等[13]在前人的研究基礎下提出了多車型車輛路徑優化問題的車型分配原則，并將實載率納入運輸成本的考慮范圍。楊珍花，平仲，湯洋，et al[14]在冷藏車多車型混合配送調度優化研究中考慮冷鏈配送貨物對時間的要求提出了時間窗外的懲罰成本表達式。Cruz J等[15]在具有時間窗和多乘積的多車型車輛路徑問題的研究中，提出了序貫蟻群系統-禁忌搜索算法，引入了兩種信息表跟蹤策略。Penna P H V等[16]將多倉庫、分批交付、站點依賴性、開放路線、時間窗口等屬性與多車型相結合，并提出了一種混合元啟發式算法進行求解。Zhang D等[17]在研究多車型車輛路徑問題時，考慮了二維負載約束，并將人工蜂群算法和人工免疫算法相結合，提出了一種混合式算法，有效避免了出現局部最優解的情況。Farid G S和Abdolhadi Z[18]利用非均勻性的概念，考慮了時間窗和多車型因素，建立了多目標函數，根據客戶的優先服務問題，提出了非支配排序遺傳算法。Yu Y[19]等考慮多車型車輛可用于減少碳排放的特性，提出了一種改進的支路價格算法求解帶有時間窗的異質車隊綠色車輛路徑優化問題。Bevilaqua A[20]等研究了兩級固定車隊異質車輛路徑問題，提出了一種基于局部搜索的LIN-Kernighan啟發式算法。

基于前述研究成本，建立了基于動態需求的多車型車輛路徑兩階段優化模型，研究了在出現動態的客戶需求時如何合理的安排配送線路使得運輸成本最低，考慮了多車型以及時間窗對車輛配送線路的影響，基于問題的HP-hard特性，本文采用了遺傳算法進行運算求解配送線路。最后通過JLD公司實際配送案例進行研究，證明模型有效的降低了JLD公司的運輸成本并減少了配送車輛數量。

1 問題描述和模型的基本假設

1.1 問題描述

基于動態需求的多車型車輛路徑優化問題可以描述為：配送中心存在不同車型的車輛，根據客戶的訂單需求情況，車輛根據調度指示從配送中心出發，依次為客戶需求點提供配送服務，完成配送任務后，需要回到配送中心。車輛為客戶配送服務的過程中，客戶需求是動態變化的。需要解決的問題是：如何在以運輸成本最小為目標的前提下，通過智能調度完滿足客戶動態變化的需求。

1.2 模型的基本假設

1）物流配送過程是單純的送貨過程，配送的是同一類型的產品，配送車輛在完成任務后需要回到配送中心；

2）客戶的需求都是不可拆分的，每個客戶的需求只能由一輛車為其服務，不可拆分成兩輛及兩輛以上的車輛為其服務；

3）假設車輛在行駛過程中勻速行駛，不考慮交通堵塞及天氣環境的影響；

4）車輛到達客戶點立刻可以對其進行服務，無等待時間。

2 模型構建

基于上述的問題描述和假設條件，對符號定義如下：

N={0，1，2，…，n}：配送中心與n個客戶點集合；

0，n+1：配送中心；

dij：任意兩個客戶點之間的距離；

M：配送中心的車輛數；

K：配送中心的車型數；

Qk：車型為k的車輛容量；

Fk：第k種車型車輛的發車成本（包括折舊費用和司機工資薪酬）；

qi：客戶i的需求量；

[ei，li]：客戶i要求車輛達到的時間窗，i∈N；

ek1：第k種類型車輛空載時的單位距離油耗成本；

ek2：第k種類型車輛在滿載時的單位距離的油耗成本；

pijmk：車型為k的車輛從客戶i處到客戶j處的實際裝載率；

vk：車型為k的車輛行駛速度；

wijmk：車型為k的車輛m從客戶i處到客戶j處的實際運輸量；

si：配送車輛在客戶i處的服務時間；

ti：車輛達到節點i的時間點，i∈N；

c（tim）：配送車輛m在客戶i需要承擔的懲罰成本，ai是配送車輛早于客戶點i要求的最早到達時間的單位時間懲罰成本，bi是車輛晚于客戶要求的最晚到達時間的單位懲罰時間成本，bi＞＞ai且（其中ai與bi可用來反應客戶的重要程度，客戶越重要，ai與bi的設置就越大）：

S：支路消去約束集。

2.1 初始送路徑規劃模型

目標函數如下：

式(4)總配送成本最小，第一項表示車輛發動的固定成本，第二項時是油耗成本，第三項是車輛早到或者晚到的懲罰成本；式(5)表示車型為k的車輛m從客戶i到客戶j的實際載重率；式(6)表示車型為k的車輛運輸貨物總量不得大于車輛本身的最大載重量；式(7)客戶i只能由某一輛車提供配送服務，不得拆分成兩輛或兩輛以上的車輛提供配送服務；式(8)、式(9)表示車輛為客戶服務結束，必須要從該客戶點駛出，保證駛入車輛等于駛出車輛；式(10)表示配送車輛必須從配送中心出發，在完成配送任務之后必須返回配送中心；式(11)表示車型為k的車輛m從客戶i處到客戶j的運輸量要大于客戶j的需求量；式(12)表示車型為k的車輛m從客戶i處出發，到達客戶j的時間；式(13)表示車輛從配送中心出發時是滿載狀態；式(14)表示支路消除約束，即避免不完整的行駛線路。

2.2 實時優化階段模型

本文采用定時的批量處理策略，將工作日劃分為若干個時間段，每個時間節點設為關鍵時間點，現假設關鍵時間點為Th，在這個時間段里總計出現了H個新的新客戶需求信息，其中包括了初始客戶的需求量增加至超過配送車輛的剩余裝載量的部分。此時，設初始階段已經服務結束h個客戶，初始階段已經派出車輛Mv（Mv≤M），派出的車型數為Ka，由于初始配送已經開始配送服務，調度中心無法直接安排調度，則假設初始配送車輛在關鍵時間點的位置為虛擬的配送中心。Qkm為派出的車型為k的車輛m的剩余載重量，在Th時刻，未服務的客戶數為n-h+H。設還需派出車輛為p輛（m=Mv+1，Mv+2，…，Mv+p），車型總量為Kb。客戶編號為：h，h+1，…，n-h+H（Y=n-h+H）。

則實時優化階段的數學模型如下：

式(15)是表示的是目標函數：總配送成本最低，第一項表示實時階段車輛從配送中心出發的固定成本，第二項表示實時調度的車輛運輸的油耗成本，第三項表示初始配送車輛繼續行駛花費的油耗成本，第四項表示車輛延遲或者早到服務點的懲罰成本；式(16)表示車型為k的車輛m從客戶i行駛至客戶j的實際載重率；式(17)表示各位于配送路中的車輛的剩余裝載量可以滿足剩余需要配送客戶點的需求量之和；式(18)表示客戶i的需求只能由一輛車完成，即客戶點i的需求不可拆分為兩輛或兩輛以上車輛配送；式(19)和式(20)表示變量之間的關系，即車輛為客戶服務結束，必須從該客戶點駛出；式(21)表示在為下一個客戶服務之前就可以確定車輛的剩余載重量客戶滿足這個客戶的需求；式(22)表示到達連續服務的兩個客戶的遞推時間；式(23)表示實時派車時車輛從配送中心滿載出發狀態；式(24)表示支路消去約束，即避免構成不完整線路的行車路線。

3 動態需求路徑優化求解算法

由于遺傳算法具有在搜索過程中不易陷入局部最優、搜索速度快、運行時間短的優點，故本文采用遺傳算法進行運算。在初始階段，采用遺傳算法得到初始配送階段車輛配送的具體線路；在實時優化階段，在關鍵時間點，對動態變化的需求信息進行統計，將其轉化為靜態的車輛路徑問題進行求解，采用遺傳算法進行運算，得到實時階段車輛配送線路。以下是遺傳算法的算法設計：

步驟1：染色體編碼

運用將已經編號的客戶點依次排列的方法，根據車輛的裝載約束條件，按照一定順序將客戶點安排到車輛的配送路徑中；

步驟2：種群初始化

完成染色體變化后，隨機產生若干初始個體的種群；

步驟3：適應度函數

本文模型中的目標函數是運輸成本最小，適應度值選取運輸成本與超載成本之和，超載成本是裝載量違反約束的重量與懲罰系數的乘積，只有當超載成本≤0時，才能得到可行解。運輸成本與超載成本之和越小，適應度值就越小。

步驟4：選擇操作

本文采用的是輪盤賭規則，計算當前個體的適應度值，通過比較，選擇比較優的個體進行下一代。借鑒冪律概率選擇[21]的方式，質量越好的個體的概率越大，被選擇的機會越大。對適應度值進行排列，選出最差的適應度值，通過式(25)得出種群個體的等級：

其中Xi表示當前種群個體，Xw表示表示最差的適應度值，β表示放大系數，通過放大系數緩解極端情況出現。個體被選擇的概率為，適應度值越小，在整個種群中所占的比例就越大，進入下一代的概率就越大。

步驟5：交叉操作

交叉方式包括單點交叉、多點交叉、算數交叉、均勻交叉等，本文采用算術交叉的方法進行交叉操作，即將兩個種群個體利用線性組合的方式進行交叉，得到兩個新的個體。1）確定個體線性交叉的系數?；2）根據式(26)進行交叉操作形成兩個新的個體。

步驟6：變異操作

在某條染色體上任取幾個點，將其所在位置進行逆轉，從而得到一個新的染色體；

步驟7：新舊種群合并

采用精英保留策略，即將父代種群與生成的交叉個體和變異個體進行合并。

4 實證分析

以WX市JLD物流公司的配送數據作為案例進行研究，JLD物流公司的運輸領域包括航海運輸、航空運輸和陸地運輸，陸運業務包括長途、短駁、城際運輸三大模塊，本文的研究對象是短駁組的運輸情況。目前短駁組最大的問題是在根據客戶需求進行了車輛調度的情況下，出現了動態客戶需求時，如何實時調度車輛滿足客戶配送需求的同時達到運輸成本最小，故收集了JLD物流公司短駁組2019年某日的需求數據，配送中心的坐標為（120.277757，31.489746），初始客戶需求信息如表1所示。JLD公司對客戶進行了ABC分類，A類客戶是最重要的客戶，ai=15元/小時，bi=50元/小時，C類客戶是最不重要的客戶，ai=5元/小時，bi=30元/小時，B類客戶的ai=10，bi=40元/小時，短駁組共有三種類型的車輛，車輛的相關參數如表2所示。JLD配送中心自有車輛共有9輛車，其中有4輛5t型號的車，3輛8t型號的車，2輛20t型號的車。假設車輛在行駛過程中是勻速行駛，不考慮天氣和交通堵塞的情況，v=30km/h。車輛每天7點從配送中心出發為客戶配送貨物。由于配送中心無法預知動態客戶的需求信息，因此在制定配送線路時，為了能對動態需求作出快速響應，假設車輛從配送中心出發時是滿載狀態，用有效裝在率來衡量車輛配送路徑優化的效果。

表1 初始客戶需求信息

表1（續）

表2 配送中心使用的車型參數

以Th=9.5作為關鍵點，匯總在9.5h之前出現的動態需求信息。新的客戶需求信息如表3所示。

表3 新的客戶需求信息

利用遺傳算法對初始配送路徑規劃模型進行運算，結果如下：運算時間為103.472647秒，迭代次數為1072時得到最優解，最小運輸成本為3956.5062元。具體運輸線路如表4所示，算法的進化過程如圖1所示，初始配送方案如圖2所示。

圖1 遺傳算法進化過程圖

圖2 初始配送方案

表4 初始配送路徑優化結果

利用遺傳算法對實時配送路徑規劃模型進行運算，結果如下：運算時間為46.740466秒，迭代次數為311次時得到最優解，最小運輸成本為4877.393元。優化結果如表5所示，算法的進化過程如圖3所示，實時配送方案如圖4所示。

表5 實時配送路徑優化結果

圖3 實時優化階段遺傳算法進化過程圖

圖4 實時配送方案

由上述結果可以發現：

1）兩階段模型可以快速的對新的客戶需求做出響應，在實時優化階段，增加了一輛5t車輛和一輛8t車輛提供配送服務。5t的車輛為客戶36、14、27提供配送服務，有效裝載量為4.9t，有效裝載率為98%。8t的車輛為新增客戶37、35、32、38、33、31提供配送服務，有效裝載量為7.85t，有效裝載率為98.125%；

2）兩階段模型可以在一定程度上提高有效裝載率。車型為8t的車輛5在初始配送階段的有效轉載量為7.7t，在實時優化階段的有效裝載量為7.85t，有效裝載率增加了1.875%；車型為20t的車輛8在初始配送階段的有效裝載量為19.003t，在實施優化階段的有效裝載量為19.503t，有效裝載率提高了2.5%；

3）兩階段模型可以在一定程度上減少因早于或晚于時間窗到達的懲罰成本。車型為8t的車輛5在實時優化階段根據新增客戶點調整配送線路，懲罰成本從21.5037元減少為0元。總懲罰成本從初始配送階段的181.8875元減少實時優化階段至177.6673元，減少了4.2202元。

在實際配送中，JLD采用的是專人專車專線路的原則，每個司機專門負責一輛車，責任到人，根據歷史成本數據可以發現專人專車的原則有效的緩解了車輛的損壞率以及減少了車輛的維修成本。采用專線路的原則是因為客戶對JLD的配送要求很高，規定了在客戶廠區內的行駛線路以及速度等，并且考慮了司機與客戶倉庫員工熟悉程度會影響到裝卸搬運的效率。然而通過分析大量數據，在實際操作過程中，采用專線路原則的必要性不強，同時導致了車輛的裝載率非常低，以及自有車輛的使用效率也很低。實際調度過程中JLD派出了9輛自有車輛，同時安排了6輛外包車輛進行了配送。動態需求路徑方案與JLD實際配送方案的對比如表6所示。

表6 方案對比

由表6可以發現，利用動態需求的多車型車輛路徑優化模型，JLD的9輛自有車輛完全可以滿足客戶的配送需求，只需要8輛車輛即可滿足配送需求，比實際調度結果節約了7輛車，不需要外包車輛進行配送，配送車輛數優化了46.667%，運輸成本節約了1853.297元，優化了27.53%。基于動態需求的多車型模型為JLD減少了配送車輛數并降低了運輸成本。兩階段模型根據運輸成本最小化進行路徑優化，改變了JDL公司專線路的原則。

5 結語

論文針對路徑優化問題中客戶需求是動態變化的、配送中心擁有多種型號的車輛以及客戶提出了需在時間窗提供配送服務等特點，展開了一系列研究。首先根據客戶的需求是動態變化的特征，建立了兩階段的模型，通過關鍵點將動態變化的需求轉化為靜態問題，在初始配送路徑階段，運用了遺傳算法進行了求解分析，得出了初始階段的車輛配送線路；在實時優化階段，運用了遺傳算法進行了分析求解，得出了在出現新的客戶需求時的配送路徑方案；其次，針對不同車型的車輛在運輸過程中油耗成本會不同的特點，考慮了運輸成本會與配送車輛的實際裝載率、運輸距離成本之間的關系，改變以往只以運輸距離最小化為目標函數的情況，更加客觀全面的描述了不同車型對配送線路的影響；接下來，考慮了時間窗對配送線路的影響，遲到或早到都會產生懲罰成本；最后，通過JLD公司這一實際案例驗證模型的優化效果，改變了JLD原有的專線路原則，重新規劃運輸線路，發現兩階段模型的優越性，可以快速的對動態需求作出高效的響應、提高有效裝載率、減少懲罰成本，并將得出的結果與JLD實際配送情況進行對比分析，發現通過建立動態需求的多車型模型解決了JLD短駁組目前最大的配送難題，可以根據動態客戶需求信息實時更新配送線路，同時起到了降低運輸成本和減少配送車輛數的作用，對長途組、城際配送組的配送也有一定的借鑒意義。未來將結合交通流進行研究，不再假設車輛為勻速行駛，分析交通流對車輛配送線路的影響。