帶軟時間窗的同時取送貨車輛路徑問題研究

李博威，戶佐安，賈葉子，唐詩韻

(西南交通大學 1. 交通運輸與物流學院；2.綜合交通大數(shù)據(jù)應用技術國家工程實驗室，四川 成都 611756；3.廣西交通設計集團有限公司，廣西 南寧 530029)

隨著物流與運輸行業(yè)的蓬勃發(fā)展，基本送達服務已無法滿足大眾需求，而高品質、高效率的配送服務，更為大眾所青睞。如何提升配送、運輸?shù)确矫娴男?，是研究者所面臨的一道難題。面對多元化的運輸需求，傳統(tǒng)配送服務在配送時間、客戶滿意度等方面仍存在較大提升空間。同時，配送人員在配送過程中也會面臨需要沿途裝載取回貨物等情況，對有容量約束的配送車輛來說同樣是新的考驗。因此，考慮同時滿足軟時間窗與同時取送貨需求的研究是迫切且必要的。而如何保證滿足客戶需求的同時，降低物流成本，提升運輸效率，對提升整個行業(yè)服務標準與盈利水平均有較大幫助。

車輛路徑問題(vehicle routing problem, VRP)自1959年由Dantzig等[1]提出后得到廣泛關注。帶時間窗的車輛路徑問題(vehicle routing problem with time windows, VRPTW)也已得到深入研究。自Solomon[2]針對VRPTW給出相對完備的基準算例與求解算法后，此后研究多基于其基準算例進一步展開。而VRP關于同時取送貨問題的研究，由Min[3]提出并在后續(xù)研究中得到廣泛關注。Dethloff[4]進一步將VRPSPD的模型進行完善。后續(xù)研究學者將VRP以上2大研究分支逐步結合，提出帶時間窗的同時取送貨車輛路徑問題(VRPSPDTW)。隨后根據(jù)時間窗的特點，又將研究領域拓展為帶軟、硬時間窗的同時取送貨車輛路徑問題(VRPSPDSTW & VRPSPDHTW)2大類，硬時間窗因其嚴格約束的特點，到達客戶點服務的靈活性較差。Wang等[5]針對VRPSPDHTW建立相應模型，并改進Solomon基準算例，運用遺傳算法對模型進行驗證。王超等[6-9]根據(jù)Wang的研究基礎，從算法改進角度設計多種啟發(fā)式算法進行求解，運用Wang所改進算例對算法進行驗證，并與Wang所求解進行比對，證明算法改進后，求解效率更高，解的質量更好。石建力等[10]從行駛時間與服務時間隨機的角度，考慮更為一般的分批配送情況，研究該情況下集配貨一體化車輛路徑問題，建立相應模型，同樣采用Wang所構建算例，運用改進迭代局部搜索算法驗證模型的有效性。戶佐安等[11]在考慮客戶滿意度條件下，構建基于模糊時間窗與貨損率的滿意度函數(shù)，并以客戶滿意度最大及運輸成本最小為優(yōu)化目標建立相應模型進行求解。而受路況，車況及天氣等因素影響，運輸過程中存在大量不確定因素，因此軟時間窗更符合實際配送情況，對無法在時間窗內準時到達的車輛，滿足其在軟時間窗外服務總時間最小。目前，針對VRPSPDSTW的相關研究較少，關麗霞[12]、祁文祥等[13]考慮軟時間窗下VRPSPD，但其模型中對軟時間窗的刻畫不夠合理。鄧愛民等[14]針對帶軟時間窗的集配貨一體化VRP，運用改進模擬退火算法進行求解，但其模型中對車輛使用固定成本與車輛在途前后時間關系上缺乏準確表述。

本文在總結已有研究成果的基礎上，進一步改進VRPSPDSTW的模型，對線性約束無法準確刻畫車輛起始服務時間與軟時間窗關系的問題，考慮引入非線性約束m ax{A,B}，結合車輛到達時間在軟時間窗內或外的情況，靈活確定車輛起始服務時間，建立能夠完整、準確刻畫各變量間的關系(包括時間變量在運輸全程的前后關系)的模型。

1 VRPSPDSTW的問題描述及數(shù)學模型

1.1 問題描述

設路網內有1個配送中心，內設K輛配送車輛；路網內有N個客戶點，每一客戶點均有不同取送貨需求，且各客戶點對服務時間有要求，要求服務時間段外進行服務的總時間最小。第k(0≤k≤K)輛車由配送中心始發(fā)為各客戶點服務，完成服務后須返回配送中心。車輛有容量約束，在全程服務過程中，不允許超出容量限制；且配送中心對車輛返回時間有相應要求，滿足所有車輛超出返回時間窗的總時間最??；各客戶點有且僅有1輛車進行服務；要求車輛總成本最小。

1.2 模型假設

模型假設條件如下。

1) 路網內僅有1個配送中心，若干客戶點，且配送中心及各客戶點坐標已知；

2) 車輛全程勻速行駛，且行駛速率為1；

3) 取送貨服務的貨物品類無差異；

4) 各客戶點取送貨服務時間相同，不考慮作業(yè)不同復雜程度；

5) 各客戶點有軟時間窗要求，滿足所有車輛在軟時間窗外服務總時間最小；

6) 車輛由配送中心始發(fā)，完成取送服務后，須返回配送中心；

7) 各客戶點有且僅有1輛車進行服務，且取送貨服務一次性完成，不考慮分批取送；

8) 車輛容量限制。在全程服務過程中，不允許超出容量限制。

1.3 模型變量說明

VRPSPDSTW模型相關變量說明如表1所示。

表1 模型變量說明Table 1 Model variable description

1.4 模型建立

在結合文獻[5-9]總結的混合整數(shù)規(guī)劃(mixed integer programming, MIP)模型基礎上，對軟時間窗約束著重刻畫，明確車輛在途前后時間關系，將全程各節(jié)點時間關系進行完整表述，構建VRPSPDSTW的混合整數(shù)非線性規(guī)劃(mixed integer nonlinear programming, MINLP)模型。其中，變量集合定義如下。

1) 路網內客戶點集V={1,2,···,n}；

2) 路網內配送中心與客戶點集V0=V∪{0}；

3) 車輛集K={1,2,···,m}。

運輸全程需針對多個目標進行優(yōu)化，包括全程車輛行駛路徑最短、全程使用車輛數(shù)最少、車輛全程違反軟時間窗所產生的總等待時間最少、車輛全程違反軟時間窗所產生的總遲到時間最少和客戶滿意度最高5個優(yōu)化目標。各優(yōu)化目標的目標函數(shù)為

1) 全程車輛行駛路徑最短

2) 全程使用車輛數(shù)最少

3) 車輛全程違反軟時間窗所產生的總等待時間最少

4) 車輛全程違反軟時間窗所產生的總遲到時間最少

5) 客戶滿意度以在軟時間窗外總違反時間最少來表示，軟時間窗外總違反時間越少，說明車輛最大限度滿足客戶的時間窗要求，因此客戶滿意度最高。

5個優(yōu)化目標間相互制約，且存在較為明顯的互斥關系，如保證全程使用車輛數(shù)最少時，無法同時確保車輛行駛路徑最短，或將產生較長行駛距離。對于本文建立的多目標優(yōu)化模型，為保證全程運輸系統(tǒng)最優(yōu)，考慮采用理想點法進行處理，以各單目標最優(yōu)值作為其理想值，將多目標條件下，各目標函數(shù)值與其理想值間差值的絕對值作為評價函數(shù)，滿足各評價函數(shù)之和最小，將多目標優(yōu)化轉為單目標優(yōu)化，求出該單目標優(yōu)化的全局最優(yōu)解，作為原多目標優(yōu)化的有效解。轉化后的目標函數(shù)為

其中，式(7)、(8)確保各客戶點僅由1輛車進行取送貨，且取送貨服務僅進行1次；式(9)為流量守恒方程，確保車輛進入客戶點r完成取送貨服務后，須駛出并前往其他客戶點；式(10)為車輛由配送中心始發(fā)，前往各客戶點完成取送貨服務后，須返回配送中心；式(11)為車輛使用數(shù)約束；式(12)為車輛由配送中心始發(fā)，前往各客戶點進行取送貨服務；式(13)為車輛完成取送貨服務后，須返回配送中心；式(14)、(15)為車輛從配送中心始發(fā)的初始載貨量及其約束；式(16)、(17)為車輛返回配送中心的載貨量及其約束；式(18)、(19)、(20)為車輛由配送中心前往初始客戶點、完成初始客戶點后各客戶點間及完成客戶點取送貨服務后返回配送中心的車輛在途載貨量關系；式(21)、(22)、(23)為車輛由配送中心前往初始客戶點、完成初始客戶點后各客戶點間及完成客戶點取送貨服務后返回配送中心的時間關系；式(24)為消除運輸網絡子回路；式(25)為0 ?1變量

2 VRPSPDSTW多目標優(yōu)化求解算法分析

本文所構建的VRPSPDSTW模型屬MINLP，變量類型包含0-1變量與連續(xù)變量，約束條件包括線性約束與非線性約束，屬NP-Hard類非凸優(yōu)化問題。針對中小規(guī)模的此類優(yōu)化問題，可考慮采用精確算法進行求解，因此，設計相應求解算法，采用LINGO 17.0對模型進行精確求解，具體求解算法如下圖1所示。

3 算例分析

本文采用Wang等[8]改進的Solomon關于VRPTW的經典基準算例對上述模型及算法的有效性進行驗證。選取其中5、10個客戶點規(guī)模的6組算例，其客戶點位置生成方式為隨機分布和聚類分布混合。

根據(jù)以上假設條件及算例數(shù)據(jù)，合理規(guī)劃車輛使用與行駛路線，滿足評價函數(shù)目標值最小。每組算例具體車輛使用與行駛路線如圖2和圖3所示，各項指標如表2和3所示。

從上述求解結果可知，針對客戶點規(guī)模為5和10的6組算例，均已找到符合模型的有效解，且滿足在單目標優(yōu)化下取得全局最優(yōu)，驗證了模型及算法的有效性。且無論對時間窗較緊或較為寬松的算例，所建模型均表現(xiàn)出良好的適應性，將違反時間窗的總時間限制在最小限度，進而取得較高的客戶滿意度(＞94%)，證明該模型同時具有較強的魯棒性。通過引入理想點法對目標函數(shù)進行重構，平衡了多目標優(yōu)化中不同尺度目標間的關系，并求得對應問題的全局最優(yōu)解。

圖1 VRPSPDSTW多目標優(yōu)化求解算法流程圖Figure 1 Flow diagram of multi-objective optimization algorithm for VRPSPDSTW

圖2 RCdp0501、RCdp0504、RCdp0507車輛行駛路線圖Figure 2 Maps of vehicle route for RCdp0501, RCdp0504, RCdp0507

圖3 RCdp1001、RCdp1004、RCdp1007車輛行駛路線圖Figure 3 Maps of vehicle route for RCdp1001, RCdp1004, RCdp1007

表2 LINGO 17.0針對RCdp0501、RCdp0504、RCdp0507求解結果Table 2 Solving solutions of RCdp0501, RCdp0504, RCdp0507 by LINGO 17.0

表3 LINGO 17.0針對RCdp1001、RCdp1004、RCdp1007求解結果Table 3 Solving solutions of RCdp1001, RCdp1004, RCdp1007 by LINGO 17.0

4 結論

本文針對VRPSPDSTW，構建相應MINLP模型，根據(jù)車輛在途過程中，到達不同客戶點前后時間關系進行標定，同時對軟時間窗表現(xiàn)形式與篩選過程實現(xiàn)準確刻畫，并與車輛在途前后時間關系進行融合，將軟時間窗條件下，車輛集配貨一體化全過程通過數(shù)學模型進行完整刻畫。通過設計相應多目標優(yōu)化求解算法，并運用LINGO 17.0全局求解程序，求得6組算例的全局最優(yōu)解，最大限度滿足各客戶點對時間窗的要求，確保車輛行駛路徑最短與車輛使用數(shù)最少，同時獲得較高的客戶滿意度，從而驗證了模型及算法的有效性。

此外，本文所研究問題屬NP-Hard問題，當客戶點數(shù)量規(guī)模較大時，LINGO的精確算法往往在多項式時間內無法求得全局最優(yōu)解。因此，對于VRPSPDSTW，今后研究考慮針對問題及模型自身特點，設計相應啟發(fā)式算法搜索近似最優(yōu)解，結合大規(guī)模算例進行驗證，測試算法的求解效率與求解精度。同時，在研究過程中發(fā)現(xiàn)，由于軟時間窗的特殊性，為滿足下一客戶點對軟時間窗的要求，規(guī)避違反軟時間窗所產生的不利影響，車輛均在完成服務后在上一客戶點有較長停留時間。這雖能滿足客戶點對軟時間窗的要求，但不利于運輸企業(yè)加速車輛周轉，造成運輸效率低下、運營成本上升，對企業(yè)長期發(fā)展產生不利影響。因此，加快路網內車輛周轉，縮短車輛在各客戶點的停留時間可作為下一步研究方向。