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

基金項目：2023年沈陽城市建設(shè)學院機械工程學院交通運輸專業(yè)學生創(chuàng)新創(chuàng)業(yè)能力培養(yǎng)項目（10520230201）

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

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

摘? 要：該文以第三方汽車物流企業(yè)為研究對象進行車輛調(diào)度優(yōu)化，根據(jù)實際問題進行問卷調(diào)研，對企業(yè)某貨物運輸車輛調(diào)度方案的現(xiàn)狀進行分析，收集信息輔助驗證硬時間窗的車輛調(diào)度優(yōu)化問題，利用改進后的C-W節(jié)約法和Lingo軟件進行車輛調(diào)度優(yōu)化設(shè)計，使貨物車輛調(diào)度行駛的路徑最短，調(diào)度安排更加合理，從而達到降低運輸成本、準時快速高效率運輸?shù)哪康模詈髮⒔Y(jié)果進行驗證。

關(guān)鍵詞：第三方汽車物流；車輛調(diào)度；C-W節(jié)約法；Lingo；優(yōu)化

中圖分類號：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

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

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

1? 原理及步驟

1.1? 原理

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

（１）

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

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

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

，? ? ? ? ? （2）

，? ? ? ? ?（3）

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

1.2? 流程結(jié)構(gòu)及步驟

流程結(jié)構(gòu)如圖1所示。

圖1? 流程結(jié)構(gòu)

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

步驟2：若節(jié)約矩陣表內(nèi)的節(jié)約值皆為0時，則循環(huán)結(jié)束，否則轉(zhuǎn)入步驟3。

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

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

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

1）若EFj=0，則轉(zhuǎn)入步驟6。

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

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

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

步驟7：將節(jié)約矩陣表中有關(guān)于該條線路上各目標點有關(guān)的節(jié)約值均轉(zhuǎn)化為0后轉(zhuǎn)步驟2。

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

2? 應(yīng)用舉例

2.1? 背景信息

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

表1? 各點位信息

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

2.2? 路徑結(jié)果

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

需要根據(jù)表1和表2內(nèi)信息計算得出表3各點間的節(jié)約距離矩陣表。

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

由上述C-W節(jié)約法的求解步驟可以找尋出下述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節(jié)約法思路

以時間0時出發(fā)為例，從P點出發(fā)到達第一個目標點N的時間為0.187 5 h，在N點服務(wù)后到達第二個目標點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時出發(fā)為例，從P點出發(fā)到達第一個目標點A的時間為0.067 5 h，在A點服務(wù)后到達第二個目標點O的時間為0.93 h，在O點服務(wù)后到達第三個目標點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時出發(fā)為例，從P點出發(fā)到達第一個目標點F的時間為0.06 h，在F點服務(wù)后到達第二個目標點H的時間為1.072 5 h，在H點服務(wù)后到達第三個目標點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時出發(fā)為例，從P點出發(fā)到達第一個目標點D的時間為0.057 5 h，在D點服務(wù)后到達第二個目標點J的時間為1.07 h，在J點服務(wù)后到達第三個目標點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時出發(fā)為例，從P點出發(fā)到達第一個目標點L的時間為0.06 h，在L點服務(wù)后到達第二個目標點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時出發(fā)為例，從P點出發(fā)到達第一個目標點G的時間為0.065 h，在G點服務(wù)后到達第二個目標點E的時間為0.827 h，到達G、E的時間滿足各目標點時間窗口。

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

3? 結(jié)論

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

參考文獻：

[1] 李娟.市場定位下第三方汽車物流企業(yè)發(fā)展戰(zhàn)略研究[J].中國集體經(jīng)濟，2015（13）：31-32.

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

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