王美薪 劉菲菲 高文文 李忻陽(yáng) 蘭佳文 丁圣恩

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

*通信作者：劉菲菲（1988-），女，碩士，講師。研究方向?yàn)榻煌ㄟ\(yùn)輸。

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

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

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

中圖分類號(hào)：U27? ? ? ? ?文獻(xiàn)標(biāo)志碼：A? ? ? ? ? 文章編號(hào)：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

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

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

1? 原理及步驟

1.1? 原理

本模型的求解目標(biāo)：行駛的總距離最短。

（１）

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

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

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

，? ? ? ? ? （2）

，? ? ? ? ?（3）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2? 應(yīng)用舉例

2.1? 背景信息

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

表1? 各點(diǎn)位信息

各目標(biāo)點(diǎn)之間的行駛時(shí)間由行駛路程及平均行駛速度計(jì)算得出。

2.2? 路徑結(jié)果

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

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

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

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

2.2.1? P—N—C—P

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

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

圖2? 標(biāo)準(zhǔn)C-W節(jié)約法思路

以時(shí)間0時(shí)出發(fā)為例，從P點(diǎn)出發(fā)到達(dá)第一個(gè)目標(biāo)點(diǎn)N的時(shí)間為0.187 5 h，在N點(diǎn)服務(wù)后到達(dá)第二個(gè)目標(biāo)點(diǎn)C的時(shí)間為1.307 5 h，到達(dá)N、C的時(shí)間滿足時(shí)間窗口。

2.2.2? P—A—O—B—P

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

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

以時(shí)間0時(shí)出發(fā)為例，從P點(diǎn)出發(fā)到達(dá)第一個(gè)目標(biāo)點(diǎn)A的時(shí)間為0.067 5 h，在A點(diǎn)服務(wù)后到達(dá)第二個(gè)目標(biāo)點(diǎn)O的時(shí)間為0.93 h，在O點(diǎn)服務(wù)后到達(dá)第三個(gè)目標(biāo)點(diǎn)B的時(shí)間為2.537 5 h，到達(dá)A、O、B的時(shí)間滿足各目標(biāo)點(diǎn)時(shí)間窗口。

2.2.3? P—F—H—I—P

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

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

以時(shí)間0時(shí)出發(fā)為例，從P點(diǎn)出發(fā)到達(dá)第一個(gè)目標(biāo)點(diǎn)F的時(shí)間為0.06 h，在F點(diǎn)服務(wù)后到達(dá)第二個(gè)目標(biāo)點(diǎn)H的時(shí)間為1.072 5 h，在H點(diǎn)服務(wù)后到達(dá)第三個(gè)目標(biāo)點(diǎn)I的時(shí)間為2.582 5 h，到達(dá)F、H、I的時(shí)間滿足各目標(biāo)點(diǎn)時(shí)間窗口。

2.2.4? P—D—J—K—P

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

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

以時(shí)間0時(shí)出發(fā)為例，從P點(diǎn)出發(fā)到達(dá)第一個(gè)目標(biāo)點(diǎn)D的時(shí)間為0.057 5 h，在D點(diǎn)服務(wù)后到達(dá)第二個(gè)目標(biāo)點(diǎn)J的時(shí)間為1.07 h，在J點(diǎn)服務(wù)后到達(dá)第三個(gè)目標(biāo)點(diǎn)K的時(shí)間為1.945 h，到達(dá)D、J、K的時(shí)間滿足各目標(biāo)點(diǎn)時(shí)間窗口。

2.2.5? P—L—M—P

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

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

以時(shí)間0時(shí)出發(fā)為例，從P點(diǎn)出發(fā)到達(dá)第一個(gè)目標(biāo)點(diǎn)L的時(shí)間為0.06 h，在L點(diǎn)服務(wù)后到達(dá)第二個(gè)目標(biāo)點(diǎn)M的時(shí)間為0.827 5 h，到達(dá)L、M的時(shí)間滿足各目標(biāo)點(diǎn)時(shí)間窗口。

2.2.6? P—G—E—P

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

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

以時(shí)間0時(shí)出發(fā)為例，從P點(diǎn)出發(fā)到達(dá)第一個(gè)目標(biāo)點(diǎn)G的時(shí)間為0.065 h，在G點(diǎn)服務(wù)后到達(dá)第二個(gè)目標(biāo)點(diǎn)E的時(shí)間為0.827 h，到達(dá)G、E的時(shí)間滿足各目標(biāo)點(diǎn)時(shí)間窗口。

本次運(yùn)輸方案的總行駛里程為50 km，車(chē)輛的平均裝載量為80.03%。

3? 結(jié)論

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

參考文獻(xiàn)：

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

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

[3] 《運(yùn)籌學(xué)》教材編寫(xiě)組.運(yùn)籌學(xué)（本科版）[M].4版.北京：清華大學(xué)出版社，2013：343-360.