考慮硬時間窗的車輛調度優化

王美薪 劉菲菲 高文文 李忻陽 蘭佳文 丁圣恩

基金項目：2023年沈陽城市建設學院機械工程學院交通運輸專業學生創新創業能力培養項目（10520230201）

*通信作者：劉菲菲（1988-），女，碩士，講師。研究方向為交通運輸。

DOI：10.19981/j.CN23-1581/G3.2024.13.011

摘? 要：該文以第三方汽車物流企業為研究對象進行車輛調度優化，根據實際問題進行問卷調研，對企業某貨物運輸車輛調度方案的現狀進行分析，收集信息輔助驗證硬時間窗的車輛調度優化問題，利用改進后的C-W節約法和Lingo軟件進行車輛調度優化設計，使貨物車輛調度行駛的路徑最短，調度安排更加合理，從而達到降低運輸成本、準時快速高效率運輸的目的，最后將結果進行驗證。

關鍵詞：第三方汽車物流；車輛調度；C-W節約法；Lingo；優化

中圖分類號：U27? ? ? ? ?文獻標志碼：A? ? ? ? ? 文章編號：2095-2945（2024）13-0044-04

Abstract： This paper takes the third-party automobile logistics enterprise as the research object to optimize vehicle scheduling， conducts a questionnaire survey according to practical problems， and analyzes the current situation of a freight transport vehicle scheduling scheme in an enterprise. Then， this paper collects information to assist in verifying the vehicle scheduling optimization problem with hard time window， and carries out vehicle scheduling optimization design by using the improved C-W saving method and Lingo software， so that the path of freight vehicle scheduling is the shortest. The scheduling arrangement is more reasonable， so as to achieve the purpose of reducing transportation costs， realize timely， fast and efficient transportation; and finally the paper verifies the results.

Keywords： third-party automobile logistics; vehicle scheduling; C-W saving method; Lingo; optimization

在諸多運輸車輛安排問題中，有很多都是源于車輛調度沒有及時優化而造成的。車輛調度優化目標是在得到更高的利潤，擴大自身的行業影響力，不斷向前發展。車輛調度優化可以帶來成本的節約及客戶好感度的提升，也就是說企業在進行優化車輛調度的同時，既可以節約成本提高利潤，又可以展現工作水平，進而提高滿意度，擴大企業在行業的影響力，增加企業的更多發展可能。

為求解帶時間窗的車輛調度問題不能只用原本的節約里程算法，原本的算法中不會考慮相關的時間約束，因此需要添加相關約束條件改進C-W節約法，優化后可以解決帶有硬時間窗的車輛調度問題。優化后的算法不僅增加考慮運輸車輛到達的時間約束，還考慮原節約算法中的運輸車輛的裝載量約束問題[1-2]。

1? 原理及步驟

1.1? 原理

本模型的求解目標：行駛的總距離最短。

（１）

由C-W節約算法得到目標點i和目標點j連接在一條線路上的節約值：s（i，j）=di+dj-dij。根據帶時間窗的車輛調度問題的實際情形，下列關系式必須成立：s0=0，ai≤si≤bi。

再對EFj進行定義，其表示當2種線路可以選擇時，運輸車輛在運輸線路安排計算得出的時間節約值，因此EFj=si+Ti+tij-sj。此處的時間節約值可正可負，認為是一種廣義上的節約。當EFj<0時，運輸車輛到達的時間會提前；EFj≥0時，運輸到達的時間會比預定時間延后。當計算EFj時若車輛從P出發到目標點i行駛時間si小于允許到達最早時間ai，需用ai代替si。

為了進一步地對改進后的C-W節約算法進行敘述，定義參數如下：Δ-j表示車輛在線路上j點后面的各任務均不需要等待的j點的到達時間的最大可以提前量；Δ+j表示路上j點后面的任務不違反時間窗約束的j點的到達時間的最大允許推遲量。r代表j目標點及更多目標點。

，? ? ? ? ? （2）

，? ? ? ? ?（3）

當計算連接點i和點j所在的線路時，需檢查是否違反上述時間窗的約束式（2）和式（3）。當EFj<0時，若有|EFj|<Δ-j，車輛在j后面的任務處不需要等待，否則，要等待。當EFj>0時，若有|EFj|≤Δ+j，則j后面的任務的執行不會延遲，否則，要延遲進行。

1.2? 流程結構及步驟

流程結構如圖1所示。

圖1? 流程結構

步驟1：計算所有供貨商（目標點）之間的節約路程，形成節約里程矩陣表，為方便運算列出節約里程降序表，轉入步驟2。

步驟2：若節約矩陣表內的節約值皆為0時，則循環結束，否則轉入步驟3。

步驟3：選擇出其中最大的節約值，并且選出由此相對應的（i，j）。i、j滿足下述3個條件之一的則進入步驟4，否則轉入步驟8。條件為點i和j都未在已連接路線上；點i和j一個不在已連接路線上，另一個在已連接的路線上，且相連于配送中心；點i和j分別位于不同已連接的路線上，且2點相連于配送中心的位置不同。

步驟4：對經過點i和點j線路上的總貨容量進行計算，如果總貨運容量小于單個車輛限制裝載容量Q，則轉入步驟5；如果大于等于車輛裝載限制容量Q，則轉入步驟8。

步驟5：計算EFj，并考慮如下3種情形。

1）若EFj=0，則轉入步驟6。

2）若EFj<0，則計算Δ-j。當|EFj|<Δ-j，則轉入步驟6；如果|EFj|≥Δ-j，轉入步驟8。

3）若EFj>0，則計算Δ+j。當|EFj|≤Δ+j，則轉入步驟6；如果|EFj|>Δ+j，轉入步驟8。

步驟6：再次連接點i和點j，若該線路車輛剩余裝載容量小于剩余未在線路上的各目標點的最小裝載容量時則該條線路結束，并轉步驟7，否則需計算出運輸車輛到達j點的新sj，并且轉步驟8。

步驟7：將節約矩陣表中有關于該條線路上各目標點有關的節約值均轉化為0后轉步驟2。

步驟8：將節約矩陣表中2個目標點相連的節約值轉化為0后轉步驟2[3]。

2? 應用舉例

2.1? 背景信息

某公司本次承接的運輸任務對象為某供應商汽車零部件的貨料箱，由于不同供應商貨料箱尺寸不一致在實際裝載后難以達到滿載，在實際的運輸中會設置實際裝載容量上限，避免因料箱尺寸差異而造成超載。為符合客戶的入場車輛要求，設本次運輸車輛選擇的是裝載容量實際上限為50.6 m3的運輸車，將起始運輸時間設置為0（單位：h），表1為16個點位的基礎信息，表2為各點間距離。

表1? 各點位信息

各目標點之間的行駛時間由行駛路程及平均行駛速度計算得出。

2.2? 路徑結果

標準的C-W節約法思路如下：在2個供應商目標點之間進行循環取貨的總距離小于分別對2個供應商目標點運輸的距離之和，在多種不同可以選擇的運輸路線中，選擇出最大的節約路程數值，來減少總運輸的距離的數值，以達到車輛運輸路線的最佳安排。如圖2所示。

需要根據表1和表2內信息計算得出表3各點間的節約距離矩陣表。

按照上述優化后的C-W節約法的求解步驟運算，得到下述較優的可行解。

由上述C-W節約法的求解步驟可以找尋出下述6條線路。

2.2.1? P—N—C—P

路線的運輸行駛距離：PN+NC+CP=7.5+4.8+2.8=15.1 km。

車輛裝載利用率：（qN+qC）/50.6=（24+21）/50.6≈88.93%。

圖2? 標準C-W節約法思路

以時間0時出發為例，從P點出發到達第一個目標點N的時間為0.187 5 h，在N點服務后到達第二個目標點C的時間為1.307 5 h，到達N、C的時間滿足時間窗口。

2.2.2? P—A—O—B—P

路線的運輸行駛距離：PA+AO+OB+BP=2.7+4.5+4.3+2.3=13.8 km。

車輛裝載利用率：（qA+qO+qB）/50.6=（17+20+13）/50.6≈98.81%。

以時間0時出發為例，從P點出發到達第一個目標點A的時間為0.067 5 h，在A點服務后到達第二個目標點O的時間為0.93 h，在O點服務后到達第三個目標點B的時間為2.537 5 h，到達A、O、B的時間滿足各目標點時間窗口。

2.2.3? P—F—H—I—P

路線的運輸行駛距離：PF+FH+HI+IP=2.4+0.5+0.4+2.3=5.6 km。

車輛裝載利用率：（qF+qH+qI）/50.6=（14+22+13）/50.6≈96.83%。

以時間0時出發為例，從P點出發到達第一個目標點F的時間為0.06 h，在F點服務后到達第二個目標點H的時間為1.072 5 h，在H點服務后到達第三個目標點I的時間為2.582 5 h，到達F、H、I的時間滿足各目標點時間窗口。

2.2.4? P—D—J—K—P

路線的運輸行駛距離：PD+DJ+JK+KP=2.3+0.5+0.5+1.7=5 km。

車輛裝載利用率：（qD+qJ+qK）/50.6=（22+16+12）/50.6≈98.81%。

以時間0時出發為例，從P點出發到達第一個目標點D的時間為0.057 5 h，在D點服務后到達第二個目標點J的時間為1.07 h，在J點服務后到達第三個目標點K的時間為1.945 h，到達D、J、K的時間滿足各目標點時間窗口。

2.2.5? P—L—M—P

路線的運輸行駛距離：PL+LM+MP=2.4+0.7+1.7=4.8 km。

車輛裝載利用率：（qL+qC）/50.6=（25+21）/50.6≈90.90%。

以時間0時出發為例，從P點出發到達第一個目標點L的時間為0.06 h，在L點服務后到達第二個目標點M的時間為0.827 5 h，到達L、M的時間滿足各目標點時間窗口。

2.2.6? P—G—E—P

路線的運輸行駛距離：PG+GE+EP=2.6+0.8+2.3=5.7 km。

車輛裝載利用率：（qG+qE）/50.6=（12+15）/50.6≈53.35%。

以時間0時出發為例，從P點出發到達第一個目標點G的時間為0.065 h，在G點服務后到達第二個目標點E的時間為0.827 h，到達G、E的時間滿足各目標點時間窗口。

本次運輸方案的總行駛里程為50 km，車輛的平均裝載量為80.03%。

3? 結論

在本次設計的內容中，路徑規劃是硬時間窗車輛調度優化中的一個重要環節。考慮到實時路況信息，通過合理規劃車輛路徑，可以最大限度地減少行駛距離和時間，盡管在貨物車輛調度安排優化中已經得到了相關的可執行解，但這只是片面地考慮部分影響條件的結果，在調度過程中，需要綜合考慮多種因素，并采取相應的策略和方法，以確保車輛的安全和效率。在進行貨物車輛調度規劃本身就是一個極其復雜多變的過程，同時硬時間窗車輛調度優化也是一個復雜而重要的任務，需要通過合理的路徑規劃、優先級設置、任務分配和時間調整，以及信息共享與協同，其直接關系到交通運輸業的效率和客戶滿意度，可以有效地優化車輛的調度，并提高服務質量和效率，經過不斷優化調整后得到新的車輛調度安排方案，優化車輛之間的配對關系，減少車輛之間的沖突和交叉。在之后的研究中要考慮得更加縝密，使研究結果趨于完善。

參考文獻：

[1] 李娟.市場定位下第三方汽車物流企業發展戰略研究[J].中國集體經濟，2015（13）：31-32.

[2] 程超，向令保，柏周朋，等.第三方汽車物流發展模式及對策[J].中國水運（下半月），2016，1６（９）：８４－86，221.

[3] 《運籌學》教材編寫組.運籌學（本科版）[M].4版.北京：清華大學出版社，2013：343-360.