張 笛 鐘 明 陳 龍 梁 軍 葛慧敏 談建祥

1.江蘇大學(xué)汽車工程研究院，鎮(zhèn)江，212000

2.江蘇省鎮(zhèn)江市公安局交通警察支隊(duì)交通指揮控制中心，鎮(zhèn)江，212000

3.鎮(zhèn)江興港國際物流有限公司，鎮(zhèn)江，212000

0 引言

甩掛運(yùn)輸集汽車列車運(yùn)輸與裝卸甩掛作業(yè)技術(shù)于一體，是一種集約、高效的運(yùn)輸組織模式，是道路貨運(yùn)業(yè)組織化、規(guī)?；?、網(wǎng)絡(luò)化、信息化和標(biāo)準(zhǔn)化發(fā)展水平的集中體現(xiàn)，在提高運(yùn)輸效率、降低運(yùn)輸成本、促進(jìn)節(jié)能減排等方面具有非常顯著的優(yōu)勢［1］。甩掛運(yùn)輸車輛調(diào)度問題一直是領(lǐng)域內(nèi)的研究熱點(diǎn)。

為了解決車輛調(diào)度中裝貨和卸貨時掛車運(yùn)輸交換問題，王瑩［2］提出了一種基于半掛車運(yùn)輸節(jié)點(diǎn)之間裝卸調(diào)度算法模型；CHENG等［3］建立了甩掛分離模式下的集裝箱車輛調(diào)度數(shù)學(xué)模型；朱曉蘭等［4］提出了針對裝配企業(yè)采購物流的C-W（Clarke-Wright）節(jié)約算法，并在線路規(guī)劃中插入車輛載重量和容積的雙重約束條件；馬建華等［5］采用C-W節(jié)約算法求解了線路規(guī)劃可能存在的交叉路徑、增加運(yùn)輸里程等情況，并對連接點(diǎn)選擇問題進(jìn)行了優(yōu)化；潘立軍等［6］提出了三類帶時間窗約束的車輛調(diào)度模型。

本文結(jié)合甩掛運(yùn)輸物流的特性，增加了車輛載重和時間窗的約束條件，建立了基于不同載重油耗模型的甩掛運(yùn)輸物流配送模型以及改良的CW節(jié)約算法，并以鎮(zhèn)江興港國際物流有限公司為例，驗(yàn)證了改良C-W節(jié)約算法的實(shí)用性。

1 問題描述

某車輛調(diào)度中心擁有裝載量為Qk（k=1，2，…，m）的汽車列車，在不同的客戶點(diǎn)有若干輛半掛車的運(yùn)輸任務(wù)，已知客戶點(diǎn)i的貨運(yùn)量為qi（i=1，2，…，n），且qi≥ 0，Qk≥ 0，k∈ K,i∈ C,K為所有牽引車的集合，C為所有客戶的集合。求滿足貨運(yùn)要求的費(fèi)用最少的車輛行駛路線。

相關(guān)參數(shù)假設(shè)如下：Eij為運(yùn)輸車從客戶i到客戶j的運(yùn)輸成本；tij為牽引車從客戶i到客戶j的行車時間；tsi為牽引車在客戶i處的停留時間；T0K為牽引車K的出發(fā)時間；TBK為牽引車K的要求返回時間；TEi為客戶i允許的最早開始時間；TLi為客戶i允許的最遲結(jié)束時間；Pk(t0i)為懲罰函數(shù)，用來表示車輛到達(dá)客戶i的時間遲于客戶i的最遲結(jié)束時間對應(yīng)的懲罰成本；t0i為車輛從調(diào)度中心或車場到達(dá)客戶點(diǎn)i的時間。

另外，變量xijk和yik的值為0或1。若牽引車K為客戶i服務(wù)，則yik為1，否則為0，即yik={0,1}，yik表示牽引車分配方案可用布爾矩陣表示；若牽引車 k經(jīng)由客戶 i到客戶 j，則 xijk為 1，否則為 0，即xijk={0,1}，xijk表示牽引車路線安排。

為使成本最小以及考慮配送的實(shí)際情況，模型同時滿足以下約束條件［7］：①甩掛運(yùn)輸中牽引車甩掛的是半掛車，而不是零擔(dān)貨物；②裝卸時間只與掛車的數(shù)量有關(guān)，且在運(yùn)輸網(wǎng)絡(luò)中的甩掛是沒有時間延遲的；③甩掛運(yùn)輸?shù)男手慌c汽車列車總的行駛時間和半掛車的裝卸停歇時間有關(guān)，與半掛車的數(shù)量及貨物的體積、質(zhì)量無關(guān)；④所有牽引車路線均起始并終止于調(diào)度中心，一輛車可以服務(wù)多個客戶點(diǎn)；⑤每個客戶點(diǎn)都有一個非負(fù)的貨物需求量；⑥滿載時，需要運(yùn)輸?shù)膾燔嚁?shù)量等于一輛汽車列車允許裝載的最大半掛車數(shù)量的整數(shù)倍，完成所有任務(wù)要多輛運(yùn)輸車輛；非滿載時，需要運(yùn)輸?shù)膾燔嚁?shù)量少于一輛汽車列車允許裝載的半掛車數(shù)量，完成任務(wù)只需要一輛運(yùn)輸車輛。

2 成本模型建立

運(yùn)輸過程中的汽車油耗成本是運(yùn)輸成本的一個重要組成部分，燃油的消耗量受到車輛狀況、行車速度、行駛里程、車輛載重、駕駛習(xí)慣、道路狀況，油品質(zhì)量以及天氣狀況等多種因素的影響，本文探討的油耗成本模型只考慮行駛里程和車輛載重（掛車的數(shù)量），在計(jì)算滿載和非滿載等情況下認(rèn)為風(fēng)阻力不變（行車速度不變），汽車的機(jī)械傳動損失不變，路面情況不變，路面的摩擦損失與壓力成正比，油耗和牽引車加掛車的質(zhì)量之和成正比。這里給出不同載重和不同行駛距離下的車輛油耗模型：

式中，Efij為運(yùn)輸車從客戶i到客戶j的油耗成本；Dij為客戶點(diǎn)i和客戶點(diǎn)j之間的地理距離，百公里；f為每升燃油的價格，元；A為油耗和載重的正相關(guān)系數(shù)；B為常數(shù)；m0為牽引車的質(zhì)量，t；m1為掛車的質(zhì)量，t；aij為需要從客戶點(diǎn)i運(yùn)輸?shù)娇蛻酎c(diǎn)j的掛車數(shù)量，輛。

過路費(fèi)成本是指車輛通過高速公路需要的過路費(fèi)，主要和車輛行駛的距離有關(guān)，此成本模型為

式中，Erij為運(yùn)輸車從客戶i到客戶j的過路費(fèi)成本；H為車輛每行駛百公里的過路費(fèi)用。

裝卸停歇時間成本是指牽引車在客戶處裝卸掛車所產(chǎn)生的時間成本，這一成本只和裝卸掛車的數(shù)量相關(guān)，此成本模型為

式中，Esij為運(yùn)輸車從客戶i到客戶j的裝卸停歇時間成本；D為一輛掛車裝載或者卸載所需要的時間成本。

配送延遲成本Epi指車輛沒在規(guī)定的時間內(nèi)到達(dá)客戶處所需要支付的罰金。此成本模型為

綜上所述，帶有時間窗的甩掛運(yùn)輸車輛配送優(yōu)化模型及約束條件如下：

其中，式（5）為目標(biāo)函數(shù)；式（6）表示一條線路上客戶需求總量不超過車輛的最大載重量；式（7）、式（8）表示每個客戶點(diǎn)只能由一輛車服務(wù)，且這些客戶點(diǎn)是在一條服務(wù)路線上；式（9）表示每輛牽引車的行車路線總耗時不超過預(yù)先確定的數(shù)值，即每輛牽引車需要在規(guī)定時間內(nèi)返回配送中心；式（10）表示對某個客戶點(diǎn)，牽引車到達(dá)時間限制在某一時間段內(nèi)。

3 算法求解

C-W節(jié)約算法是由Clarke和Wright于1964年首次提出的，起初是為解決旅行商問題，因此它不考慮各種約束條件，故無法直接用來求解車輛路徑問題（vehicle road problem，VRP），但可以通過加入檢驗(yàn)車輛載重約束和時間窗約束來完善CW節(jié)約算法，使之能夠求解單類型車輛路徑問題［8］。

在初始路徑0-i-0中，Ef0i是汽車從調(diào)度中心或者車場去往客戶點(diǎn)i過程中產(chǎn)生的油耗成本，Efi0是車輛由客戶點(diǎn)i返回調(diào)度中心過程中所產(chǎn)生的油耗成本，雖然來回過程的運(yùn)輸距離是一樣的，但由于載重量不同，所以Ef0i和Efi0不相等。過路費(fèi)成本只和運(yùn)輸距離成正相關(guān)關(guān)系。裝卸停歇時間成本由于每次裝卸的時間是固定的，因此只和每個客戶點(diǎn)需要裝卸的半掛車數(shù)量相關(guān)。配送延遲成本需要結(jié)合具體情況分析。

用改良節(jié)約算法解決該問題的步驟如下：

（1）首先計(jì)算客戶i和客戶j之間線路的費(fèi)用節(jié)約值s(i,j)，形成集合N，并按照從大到小對s(i,j)進(jìn)行排序，s(i,j)分為油耗費(fèi)用節(jié)約值sf(i,j)和過路費(fèi)用節(jié)約值sr(i,j)，即s(i,j)=sf(i,j)+sr(i,j),而

其中，Ef0j為在初始路徑0-j-0中汽車從調(diào)度中心或者車場去往客戶點(diǎn)j過程中產(chǎn)生的油耗成本；Efj0是車輛由客戶點(diǎn)j回調(diào)度中心過程中所產(chǎn)生的油耗成本。在調(diào)度后的路徑0-i-j-0中，為汽車從調(diào)度中心到客戶點(diǎn)i過程中所產(chǎn)生的油耗成本；Efij為從客戶點(diǎn)i到客戶點(diǎn)j的油耗成本為客戶點(diǎn)j回到調(diào)度中心的過程中產(chǎn)生的油耗成本。但由于車輛從j點(diǎn)返回配送中心時，車輛都處于空載狀態(tài)，所以Efj0=，因此：

再將油耗成本模型公式代入式（12），得

式中，D0i、D0j分別為調(diào)度中心和客戶點(diǎn)i、j的地理距離；a0i和a0j分別為調(diào)度中心運(yùn)輸?shù)娇蛻酎c(diǎn)i和j的掛車數(shù)量。

過路費(fèi)用節(jié)約值

式中，Eroi、Erj0分別為車輛路徑0-i和j-0的過路費(fèi)成本。

將過路費(fèi)成本模型公式代入式（14），得式

中，Dj0為車輛從客戶點(diǎn)j到調(diào)度中心的距離。

綜上可得

（2）若N為空，則終止疊代，否則考察N中的第一項(xiàng)s(i,j)是否滿足下列條件之一：①點(diǎn)i和j均不在已構(gòu)成的線路上；②點(diǎn)i和j在已構(gòu)成的線路上，但不與車輛調(diào)度中心相連；③點(diǎn)i和j位于已構(gòu)成的不同線路上，且均不與車輛調(diào)度中心相連，一個是起點(diǎn)，一個是終點(diǎn)。如滿足此條件則轉(zhuǎn)步驟（3），否則轉(zhuǎn)步驟（6）。

（4）計(jì)算連接點(diǎn)i和j所在的線路后，車輛到達(dá)j點(diǎn)的時間比原路線上車輛到達(dá)j點(diǎn)的時間的變化量為：Δtj=t0i+tsi+tij-t0j。t0i為車輛從調(diào)度中心或者車場到達(dá)客戶點(diǎn)i的時間，t0j為車輛從調(diào)度中心或者車場到達(dá)客戶點(diǎn)j的時間。①若Δtj=0，則轉(zhuǎn)步驟（5）；②若Δtj＜0，則計(jì)算?j-，當(dāng)Δtj≤ ?j-時，轉(zhuǎn)步驟（5），否則轉(zhuǎn)步驟（6）；③若Δtj＞0，則計(jì)算?j+，當(dāng)Δtj≤?j+時，轉(zhuǎn)步驟（5），否則轉(zhuǎn)步驟（6）。其中，?j-為線路上j點(diǎn)后面的各個客戶處均不需要等待的到達(dá)j點(diǎn)時間的最大允許提前量；?j+為線路上j點(diǎn)后面的各個客戶不違反時間約束的到達(dá)j點(diǎn)時間的最大允許推遲量。

（5）連接點(diǎn)i和點(diǎn)j，計(jì)算牽引車到達(dá)各個客戶點(diǎn)時的新時間。

（6）令N=N-s(i,j)，轉(zhuǎn)步驟（2）。

以上是針對單個車輛調(diào)度中心的車輛優(yōu)化調(diào)度問題的求解，多調(diào)度中心的車輛調(diào)度問題可以轉(zhuǎn)化為單個調(diào)度中心問題來處理，首先確定每個調(diào)度中心需完成的任務(wù)，然后再求解多個調(diào)度中心的車輛調(diào)度問題。

4 應(yīng)用研究

如圖1所示，地點(diǎn)A是鎮(zhèn)江興港國際物流有限公司的配送中心，地點(diǎn)1～9是主要裝卸點(diǎn)。根據(jù)調(diào)查，得到各裝卸點(diǎn)之間的距離以及各個裝卸點(diǎn)與配送中心之間的距離，見圖1。

圖1 配送中心與裝卸點(diǎn)之間的分布示意圖（km）Fig.1 Distribution center and the distance between the loading and unloading point diagram（km）

據(jù)英國交通部對車輛油耗與載重間關(guān)系的研究數(shù)據(jù)可知［9］，車輛的油耗與載重間存在較強(qiáng)的線性正相關(guān)特性，可以簡化為線性關(guān)系：

式中，F(xiàn)為每百公里油耗成本；M為整車質(zhì)量。

一般情況下，牽引車會使用0號柴油，價格為6.36元/L，定義牽引車的質(zhì)量為10 t，每輛掛車的質(zhì)量為15 t，車輛的過路費(fèi)為160元/百公里，每輛半掛車平均裝卸停歇時間為0.6 h，時間成本40元/h，牽引車的時間懲罰系數(shù)為0.6，每輛牽引車最多可拖帶4輛掛車，牽引車的平均速度為80 km/h，所允許最長的運(yùn)輸總時間為6 h。

車輛調(diào)度開始前，各個裝卸點(diǎn)需運(yùn)輸?shù)膾燔嚁?shù)量如表1所示。

表1 各個裝卸點(diǎn)需運(yùn)輸?shù)膾燔嚁?shù)量Tab.1 The number of trailers to be transported at each loading and unloading point

運(yùn)用上文的甩掛運(yùn)輸調(diào)度算法對這次車輛調(diào)度進(jìn)行優(yōu)化。進(jìn)行初步調(diào)度需要牽引車的數(shù)量如表2所示，調(diào)度后各個裝卸點(diǎn)剩余掛車數(shù)量如表3所示，費(fèi)用節(jié)約值如表4所示。

根據(jù)改良的節(jié)約算法對所需牽引車進(jìn)行調(diào)度的行駛路線如圖2所示。

表2 初步調(diào)度需要的牽引車數(shù)Tab.2 The number of truckers required after initial dispatch

表3 調(diào)度后各個裝卸點(diǎn)剩余的掛車數(shù)量Tab.3 Number of trailers remaining at each loading point after dispatch

表4 費(fèi)用節(jié)約值（元）Tab.4 The cost savings（￥）

圖2 調(diào)度路線示意圖（km）Fig.2 Scheduling route diagram（km）

初步調(diào)度后不使用調(diào)度算法運(yùn)送貨物至各個裝卸點(diǎn)的成本表如表5所示。各個裝卸點(diǎn)的運(yùn)輸總成本為5 850.34元。通過改良的節(jié)約算法再次調(diào)度各個線路的費(fèi)用節(jié)約值如下。

表5 原裝卸成本Tab.5 Original shipping and delivery cost

線路1（A-7-6-A）的費(fèi)用節(jié)約值為602.3元，時間為4.025 h；線路2（A-3-4-5-A）的費(fèi)用節(jié)約值為528.7元，時間為3.475 h；線路3（A-1-2-A）的費(fèi)用節(jié)約值為255.3元，時間為2.075 h；線路4（A-8-9-A）的費(fèi)用節(jié)約值為77元，時間為3.425 h；各條路線的費(fèi)用節(jié)約總值為1 463.3元。使用改良節(jié)約算法進(jìn)行車輛調(diào)度運(yùn)輸總成本減少了1 463.3元，降低了25.01%。

算例證明本文所創(chuàng)建的節(jié)約算法可以降低甩掛運(yùn)輸?shù)倪\(yùn)輸成本，并且有效地解決了運(yùn)輸過程中的車輛調(diào)度問題。

5 結(jié)論

本文基于不同載重下的油耗模型以甩掛運(yùn)輸車輛最優(yōu)運(yùn)輸路徑為研究對象建立了一種改良型C-W節(jié)約算法，構(gòu)建了基于油耗模型的甩掛運(yùn)輸物流配送優(yōu)化路徑模型，模型以包括油耗成本、過路費(fèi)成本、裝卸停歇時間成本以及延時懲罰成本在內(nèi)的總成本最小為目標(biāo)函數(shù)，以車輛載重和時間窗作為約束。在算法上，構(gòu)建了改良型的C-W節(jié)約算法，并用該算法找出了一個9客戶算例的最優(yōu)路徑。最后通過在算例中比較調(diào)度前后的運(yùn)輸成本，證明了節(jié)約算法可以降低甩掛運(yùn)輸?shù)倪\(yùn)輸成本，從而得出建立基于不同載重油耗模型的甩掛運(yùn)輸物流配送路徑優(yōu)化模型的必要性。