基于改良C-W節(jié)約算法的甩掛運(yùn)輸車輛調(diào)度模型

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

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

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

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

0 引言

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

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

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

1 問(wèn)題描述

某車輛調(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的行車時(shí)間；tsi為牽引車在客戶i處的停留時(shí)間；T0K為牽引車K的出發(fā)時(shí)間；TBK為牽引車K的要求返回時(shí)間；TEi為客戶i允許的最早開(kāi)始時(shí)間；TLi為客戶i允許的最遲結(jié)束時(shí)間；Pk(t0i)為懲罰函數(shù)，用來(lái)表示車輛到達(dá)客戶i的時(shí)間遲于客戶i的最遲結(jié)束時(shí)間對(duì)應(yīng)的懲罰成本；t0i為車輛從調(diào)度中心或車場(chǎng)到達(dá)客戶點(diǎn)i的時(shí)間。

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

2 成本模型建立

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

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

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

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

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

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

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

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

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

3 算法求解

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

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

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

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

其中，Ef0j為在初始路徑0-j-0中汽車從調(diào)度中心或者車場(chǎng)去往客戶點(diǎn)j過(guò)程中產(chǎn)生的油耗成本；Efj0是車輛由客戶點(diǎn)j回調(diào)度中心過(guò)程中所產(chǎn)生的油耗成本。在調(diào)度后的路徑0-i-j-0中，為汽車從調(diào)度中心到客戶點(diǎn)i過(guò)程中所產(chǎn)生的油耗成本；Efij為從客戶點(diǎn)i到客戶點(diǎn)j的油耗成本為客戶點(diǎn)j回到調(diào)度中心的過(guò)程中產(chǎn)生的油耗成本。但由于車輛從j點(diǎn)返回配送中心時(shí)，車輛都處于空載狀態(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ù)量。

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

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

將過(guò)路費(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)度中心相連，一個(gè)是起點(diǎn)，一個(gè)是終點(diǎn)。如滿足此條件則轉(zhuǎn)步驟（3），否則轉(zhuǎn)步驟（6）。

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

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

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

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

4 應(yīng)用研究

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

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

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

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

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

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

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

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

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

表3 調(diào)度后各個(gè)裝卸點(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)送貨物至各個(gè)裝卸點(diǎn)的成本表如表5所示。各個(gè)裝卸點(diǎn)的運(yùn)輸總成本為5 850.34元。通過(guò)改良的節(jié)約算法再次調(diào)度各個(gè)線路的費(fèi)用節(jié)約值如下。

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

線路1（A-7-6-A）的費(fèi)用節(jié)約值為602.3元，時(shí)間為4.025 h；線路2（A-3-4-5-A）的費(fèi)用節(jié)約值為528.7元，時(shí)間為3.475 h；線路3（A-1-2-A）的費(fèi)用節(jié)約值為255.3元，時(shí)間為2.075 h；線路4（A-8-9-A）的費(fèi)用節(jié)約值為77元，時(shí)間為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)輸過(guò)程中的車輛調(diào)度問(wèn)題。

5 結(jié)論

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