單車場無時(shí)間窗甩掛運(yùn)輸車輛調(diào)度的啟發(fā)式算法

張振華，賈淑娟，顧九春

（1.魯東大學(xué) 交通學(xué)院，山東 煙臺 264025；2.魯東大學(xué) 土木工程學(xué)院，山東 煙臺 264025）

1 引言

甩掛運(yùn)輸是指牽引車按照預(yù)定的運(yùn)行計(jì)劃，在貨物裝卸作業(yè)點(diǎn)甩下所拖的掛車，換上其他與牽引車準(zhǔn)牽引總質(zhì)量相匹配的掛車?yán)^續(xù)運(yùn)行的運(yùn)輸組織方式[1]。甩掛集中體現(xiàn)了道路貨運(yùn)業(yè)組織化、規(guī)模化、網(wǎng)絡(luò)化、信息化和標(biāo)準(zhǔn)化發(fā)展水平，是一種集約、高效的運(yùn)輸組織模式。它以有利于促進(jìn)多式聯(lián)運(yùn)、減少牽引車數(shù)量、提高車輛利用率，從而降低能源消耗、保護(hù)環(huán)境等優(yōu)點(diǎn)，在物流園區(qū)、港區(qū)、大型廠區(qū)等局部物流網(wǎng)絡(luò)作業(yè)環(huán)境以及重要干線節(jié)點(diǎn)之間得到廣泛應(yīng)用，有利于促進(jìn)生產(chǎn)與物流的協(xié)調(diào)，是建設(shè)資源節(jié)約型、環(huán)境友好型道路運(yùn)輸市場的有效途徑。

甩掛運(yùn)輸?shù)娘@著特點(diǎn)是貨物裝卸過程與運(yùn)輸過程的分離，因而可以提高牽引車的利用效率。一輛牽引車可以服務(wù)多臺掛車，掛車既可以作為運(yùn)輸工具，也可以作為貨物暫存的工具，貨物裝卸時(shí)間段內(nèi)牽引車可以脫離去轉(zhuǎn)接其他集散任務(wù)，這種牽引車與掛車的動(dòng)態(tài)組合使得甩掛運(yùn)輸較傳統(tǒng)的車輛調(diào)度有不同的特點(diǎn)。國外對卡車拖帶掛車（Truck and Trailer，汽車列車）的甩掛運(yùn)輸車輛調(diào)度（Truck and Trailer Routing Problem，簡稱TTRP）研究文獻(xiàn)較多，并提出了多種算法[2-4]，但對拖車或者牽引車拖帶掛車（Tractor and Trailer）的研究工作相對有限。在所查的文獻(xiàn)中，Juyoung Wy[5]研究了垃圾處理中心、車場和客戶點(diǎn)之間的單掛車甩掛問題，以牽引車數(shù)量最少和牽引車空駛時(shí)間最短為目標(biāo)，提出了一種混合啟發(fā)式算法；Roberto Baldacci[6]將多車場、多處理中心問題作為一個(gè)圖來研究，并提出一種精確算法；Juyoung Wy和A.M.Benjamin[7-8]則研究多車場的時(shí)間窗問題，提出了一種大型搜索算法；Ulrich Derigs[9]參考?xì)W洲對工作時(shí)間的嚴(yán)格限制，對大型機(jī)場貨物中心與其他貨物中心的陸路轉(zhuǎn)運(yùn)甩掛問題進(jìn)行了比較詳細(xì)的研究。

近年來國內(nèi)學(xué)者對甩掛運(yùn)輸也做了許多卓有成效的工作，如高洪濤、李紅啟[10]詳細(xì)討論了甩掛運(yùn)輸市場的需求分析、資源配置組織以及在山東省的應(yīng)用實(shí)踐；李晴[11]從車輛購置與運(yùn)營固定成本效益、車輛運(yùn)用效益、裝卸轉(zhuǎn)運(yùn)與包裝成本效益、運(yùn)輸站場成本效益、人力成本效益及其他效益六個(gè)方面，參照相關(guān)經(jīng)濟(jì)學(xué)理論，量化計(jì)算了甩掛運(yùn)輸?shù)慕?jīng)濟(jì)效益。但真正研究甩掛運(yùn)輸車輛調(diào)度的文獻(xiàn)卻十分有限，胡志華[12]研究了港口集裝箱循環(huán)甩掛問題，引入虛擬任務(wù)建立了集散任務(wù)的時(shí)間優(yōu)先關(guān)系網(wǎng)絡(luò)，并在總作業(yè)時(shí)間最小化的目標(biāo)下，建立了混合整數(shù)規(guī)劃模型并用兩階段方法求解；溫旖旎[13]將甩掛運(yùn)輸?shù)能囕v調(diào)度問題劃分為空返和非空返兩類，并為兩類車輛調(diào)度問題分別建立數(shù)學(xué)模型。在兩類數(shù)學(xué)模型的基礎(chǔ)上，對已有的車輛調(diào)度求解算法進(jìn)行了改進(jìn)，引入貪婪算法，分別為兩類模型設(shè)計(jì)了相應(yīng)求解算法；范寧寧[14]針對煙臺至大連滾裝航線貨物集疏港的現(xiàn)實(shí)情況，對牽引車調(diào)度問題進(jìn)行了條件假設(shè)和變量設(shè)定，建立了數(shù)學(xué)模型，并用Matlab編程語言對模型進(jìn)行求解；梁波[15]根據(jù)大型鋼鐵企業(yè)廠內(nèi)存在運(yùn)輸車輛裝卸停歇時(shí)間長、車輛利用率低、在途車輛多但運(yùn)輸效率低的特點(diǎn)，建立了廠內(nèi)循環(huán)甩掛調(diào)度模型，設(shè)計(jì)了求解模型的禁忌搜索算法，并建立了績效評價(jià)指標(biāo)體系。

傳統(tǒng)車輛調(diào)度大多以車輛或者牽引車行駛距離最短為優(yōu)化目標(biāo)，本文則考慮單車場甩掛運(yùn)輸?shù)奶攸c(diǎn)，依據(jù)牽引車空駛、牽帶空掛車和牽帶重掛車行駛的成本不同，定義了牽引車運(yùn)行成本的概念，將其作為判別調(diào)度方案優(yōu)劣的指標(biāo)。研究了不同類型客戶點(diǎn)的任務(wù)特點(diǎn)及部分牽引任務(wù)起點(diǎn)或終點(diǎn)不確定的單車場無時(shí)間窗車輛甩掛問題，提出了一種啟發(fā)式算法進(jìn)行求解，從而有別于現(xiàn)有文獻(xiàn)的工作，為甩掛運(yùn)輸車輛調(diào)度問題提供了一種新的求解途徑。

2 問題提出

國外對一拖一掛甩掛運(yùn)輸車輛調(diào)度方面的研究工作主要包括兩個(gè)方面：大型垃圾處理運(yùn)輸調(diào)度問題及大型航空公司貨物轉(zhuǎn)運(yùn)的車輛調(diào)度問題。其中第一個(gè)問題可描述為：在有大量垃圾產(chǎn)生的地點(diǎn)（如建筑工地作為客戶點(diǎn)）放置掛車，裝滿后由牽引車運(yùn)往垃圾處理中心，牽引車一次只能運(yùn)一輛掛車，這樣隨著客戶點(diǎn)位置分布、車場位置及垃圾處理中心位置及數(shù)量、有無時(shí)間窗等參數(shù)的變化，就衍生出了一系列車輛調(diào)度問題；第二個(gè)問題出于德國的大型機(jī)場貨物中心與其他貨物中心的陸路轉(zhuǎn)運(yùn)甩掛問題。

汽車列車甩掛在中國當(dāng)前還難以推廣，而一拖一掛甩掛則有更為現(xiàn)實(shí)的意義。單車場車輛甩掛調(diào)度是指這樣的問題：甩掛碼頭的車場或者甩掛干線兩端節(jié)點(diǎn)車場既是牽引車的存放場，也是空、重掛車的集疏場所，牽引車的任務(wù)是從車場把空、重掛車運(yùn)往客戶點(diǎn)，或者把空、重掛車從客戶點(diǎn)運(yùn)往車場，或者將空掛車從某一客戶點(diǎn)運(yùn)往另一客戶點(diǎn)。這樣并非全部任務(wù)的起點(diǎn)和終點(diǎn)都為固定，即若某客戶需求一輛空掛車，則該輛空掛車既可以從車場運(yùn)入，也可以從其他有多余空掛車的客戶點(diǎn)運(yùn)入；同樣，若某客戶點(diǎn)有空掛車需要運(yùn)出，則既可以運(yùn)往車場也可以運(yùn)往其他有需要的客戶點(diǎn)。

設(shè)牽引車為同一類型，即牽引車可以與任何掛車匹配。牽引任務(wù)可以分為四種類型：

（1）車場重車運(yùn)出任務(wù)。即下船后（或者外部運(yùn)入）的載貨掛車暫存于車場，需要運(yùn)往目的客戶，任務(wù)特點(diǎn)是有確定的起點(diǎn)和終點(diǎn)。

（2）客戶點(diǎn)重車運(yùn)出需求?？蛻酎c(diǎn)有一滿載掛車需要運(yùn)往車場以備裝船或者暫存，其特點(diǎn)也是有確定的起點(diǎn)和終點(diǎn)。如果該客戶點(diǎn)沒有其他運(yùn)入任務(wù)，則牽引車需要空駛到該客戶點(diǎn)執(zhí)行任務(wù)。

（3）客戶點(diǎn)空車運(yùn)入需求?？蛻酎c(diǎn)需要一輛空掛車裝貨，該掛車來源可以是其他客戶點(diǎn)卸貨后的掛車，也可以來自車場，所以該類型任務(wù)的特點(diǎn)是起點(diǎn)不確定。

（4）客戶點(diǎn)空車運(yùn)出需求?？蛻粜盾嚭蟛辉傩枰諕燔?，需要運(yùn)出，可以運(yùn)往其他客戶需求點(diǎn)，也可以運(yùn)往車場，所以該類型任務(wù)的特點(diǎn)是終點(diǎn)不確定。

其他類型如客戶點(diǎn)運(yùn)入一輛重掛車并有一輛重掛車運(yùn)出（重入重出）、運(yùn)入一輛重掛車并有一輛空掛車運(yùn)出（重入空出）、需求一輛空掛車并有一輛重掛車運(yùn)出（空入重出）等可以視為該客戶有兩項(xiàng)任務(wù)。

定義1 任務(wù)鏈Li：指牽引車ci一個(gè)班次執(zhí)行的任務(wù)序列，如L4=l3-l5-l12-l7-l14表示牽引車c4在一個(gè)班次內(nèi)執(zhí)行的各任務(wù)次序，其中虛擬任務(wù)包含于各任務(wù)中。

定義2 虛擬任務(wù)：牽引車為執(zhí)行某一任務(wù)必須空駛一段距離，稱為虛擬任務(wù)。

定義3 運(yùn)行成本：由于牽引車空駛、帶空掛車行駛和帶重掛車行駛所產(chǎn)生的油耗及車輛磨損不同，因此在車輛平均行駛時(shí)間的基礎(chǔ)上乘以一個(gè)區(qū)別不同行駛類型的系數(shù)即為運(yùn)行成本，作為調(diào)運(yùn)方案優(yōu)劣的判別指標(biāo)。牽引車i一個(gè)任務(wù)鏈的運(yùn)行成本用Ci表示。

定義4 鏈內(nèi)交叉：交換任務(wù)鏈Li內(nèi)兩任務(wù)的執(zhí)行順序，如l3-l5-l12-l7-l14→l3-l7-l12-l5-l14。鏈內(nèi)交叉可能引起Ci變化，若減小，則交叉有效，更新相應(yīng)的Li和Ci。

定義5 鏈間交叉：兩條鏈各取一項(xiàng)任務(wù)交叉，如：

檢驗(yàn)兩條鏈運(yùn)行成本之和的變化量，若減小，則交叉有效，更新相應(yīng)兩條鏈的Li和Ci。

3 算法設(shè)計(jì)

設(shè)牽引車和掛車均為甩掛公司所有，若某客戶點(diǎn)有空掛車運(yùn)出，則可以運(yùn)往任何需要的客戶點(diǎn)或車場；若某客戶點(diǎn)需要空掛車，則可將任何節(jié)點(diǎn)包括車場的空閑掛車運(yùn)入；所有的運(yùn)輸任務(wù)在開始時(shí)都已經(jīng)確定；班次開始時(shí)所有牽引車和多余空掛車均存放于車場，班次結(jié)束時(shí)牽引車需要回到車場。

3.1 參數(shù)設(shè)定

B：行駛時(shí)間矩陣，即參考各節(jié)點(diǎn)（含車場）間的距離矩陣，忽略空、重車行駛速度差別及甩掛和上掛時(shí)間，換算為相應(yīng)的平均行駛時(shí)間矩陣，元素為buv；

m：牽引車數(shù)量，牽引車i用ci表示；

lj'=1,2,3,4：表示任務(wù)的類型，任務(wù)類型1、2的起點(diǎn)和終點(diǎn)為已知，任務(wù)類型3的終點(diǎn)已知起點(diǎn)待定，任務(wù)類型4的起點(diǎn)已知，終點(diǎn)待定；

si：牽引車i的位置參數(shù)，位于車場或客戶點(diǎn)位置，是一個(gè)動(dòng)態(tài)變量；

Si：牽引車i一個(gè)班次經(jīng)過的所有節(jié)點(diǎn)順序序列，起點(diǎn)和終點(diǎn)都是車場；

ti：牽引車i的總運(yùn)行時(shí)間，應(yīng)有ti≤Tmax，即一個(gè)班次牽引車的總運(yùn)行時(shí)間應(yīng)該不大于某一預(yù)先設(shè)定的值；

3.2 初始調(diào)運(yùn)方案

初始調(diào)運(yùn)方案即安排初始任務(wù)鏈，其做法是一次取一輛牽引車，從所有任務(wù)中選出起點(diǎn)距牽引車當(dāng)前位置最近的任務(wù)加入該牽引車的任務(wù)鏈。其中任務(wù)類型3的起點(diǎn)應(yīng)包含所有任務(wù)類型4和車場。若牽引任務(wù)是空掛車，則其目的地為任務(wù)類型3的終點(diǎn)或車場中最近者。任務(wù)鏈的約束是牽引車必須在班次結(jié)束時(shí)間回到車場，因此當(dāng)任務(wù)鏈不能再加入新任務(wù)時(shí)，取下一輛牽引車開始新的任務(wù)鏈，見算法1。

算法1：初始方案

｛lj''=0 (j=1,2,...,n)/給所有任務(wù)狀態(tài)變量附初值0/

ti=0,Li=?,Si=1,si=1(i=1,2,···,m)/給所有牽引車附初值空集/

for i=1,2,···,m/牽引車中循環(huán)/

If lj''=1(j=1,2,···,n)終止運(yùn)算，輸出 Li,Si，ti,Ci(i=1,2,···,m')/如果所有的任務(wù)已經(jīng)執(zhí)行，則終止運(yùn)算，輸出結(jié)果，其中m'為任務(wù)鏈數(shù)量/

否則在lj''=0的任務(wù)中循環(huán)直到?jīng)]有任務(wù)可以加入Li

將任務(wù)lj給牽引車ci執(zhí)行，更新任務(wù)的狀態(tài)變量以及牽引車位置、位置序列和總運(yùn)行時(shí)間/｝

在初始方案中，牽引車的下一任務(wù)始終按就近選擇，這在一定程度上保證了初始方案的可接受性，但卻不能保證所有牽引車的總行駛成本是否有進(jìn)一步降低的可能。由于牽引車空駛以及牽帶空掛車和重掛車行駛的運(yùn)行成本不同，因此必須對初始方案進(jìn)行優(yōu)化，目標(biāo)為保證所有牽引車總運(yùn)行成本盡量低。

3.3 鏈內(nèi)優(yōu)化

鏈內(nèi)優(yōu)化即為鏈內(nèi)交叉。隨機(jī)交換任務(wù)鏈中兩項(xiàng)任務(wù)的執(zhí)行順序，檢驗(yàn)牽引車運(yùn)行成本的變化，如果使運(yùn)行成本降低，則交換有效，更新任務(wù)鏈。

算法2：鏈內(nèi)交叉

｛設(shè)任務(wù)鏈Li中有qi個(gè)任務(wù)，最大迭代次數(shù)g1

產(chǎn)生隨機(jī)數(shù)e∈[1,qi]，f∈[1,qi]

假設(shè)交換任務(wù)鏈中第e個(gè)和第f個(gè)任務(wù)，計(jì)算Ci和ti

交換有效，更新 Li,Si，Ci，

輸出 Li,Si，Ci(i=1,2···m')｝

3.4 全局優(yōu)化

全局優(yōu)化包括三方面內(nèi)容：其一是任務(wù)鏈合并，檢驗(yàn)是否可減少任務(wù)鏈或牽引車數(shù)量，其二是空車調(diào)運(yùn)優(yōu)化，即隨機(jī)交換任務(wù)類型3的起點(diǎn)或者任務(wù)類型4的終點(diǎn)；其三是鏈間交叉，隨機(jī)交換任意選取的兩條鏈上的兩項(xiàng)任務(wù)，檢驗(yàn)兩條任務(wù)鏈運(yùn)行成本的變化，見算法3。

算法3：全局優(yōu)化

｛/牽引車數(shù)量優(yōu)化/

調(diào)用算法2，鏈內(nèi)優(yōu)化；

對每一條任務(wù)鏈中每一項(xiàng)任務(wù)，試探性插入其他任務(wù)鏈逐個(gè)位置，若插入后該任務(wù)鏈運(yùn)行時(shí)間不超過Tmax，則插入有效；

更新所有任務(wù)鏈，更新后任務(wù)鏈重新編號，設(shè)數(shù)量m''；

調(diào)用算法3，對新任務(wù)鏈進(jìn)行鏈內(nèi)優(yōu)化；

以下為迭代算法，設(shè)最大迭代次數(shù)g2

/空車調(diào)運(yùn)交叉/

S3為任務(wù)類型3的終點(diǎn)集合，S4為任務(wù)類型3的起點(diǎn)及車場集合

S3中隨機(jī)選出 e3'，S4中隨機(jī)選出 s4'，配對e3'與 s4'，若配對所涉及的兩條任務(wù)鏈運(yùn)行時(shí)間均不超過Tmax且運(yùn)行成本之和減小，則交換有效，更新相應(yīng)兩條鏈的L和S。

/鏈間交叉/

產(chǎn)生隨機(jī)數(shù)z1∈[1,m'']，z2∈[1,m'']

假設(shè)交換任務(wù)鏈Lz1中第項(xiàng)和Lz2中第項(xiàng)

4 仿真算例

設(shè)有9個(gè)客戶點(diǎn)（編號2-10）和車場（編號1）共計(jì)10個(gè)節(jié)點(diǎn)，16項(xiàng)任務(wù)，10輛牽引車，，Tmax=480 min，g1=100，g2=500，節(jié)點(diǎn)間平均行駛時(shí)間（min）矩陣及計(jì)算過程見表1-表5。

表2 各項(xiàng)任務(wù)的類型和起點(diǎn)終點(diǎn)

表3 空車調(diào)運(yùn)初始方案

表4 任務(wù)鏈初始方案

表5 最終調(diào)運(yùn)方案

從計(jì)算過程和結(jié)果看出，由于考慮了就近原則，初始方案運(yùn)行成本比較滿意。經(jīng)過算法優(yōu)化后，牽引車數(shù)量減少1輛，任務(wù)鏈變化較大且運(yùn)行成本降低較明顯，從而驗(yàn)證了算法的有效性和可行性。

5 結(jié)束語

單車場甩掛運(yùn)輸?shù)闹饕攸c(diǎn)是重車運(yùn)輸只能在車場與客戶點(diǎn)之間進(jìn)行，而空掛車則可以就近方便配置，同時(shí)車場既作為車輛的存放場所，也是每個(gè)班次的交接班場所，牽引車一個(gè)班次的開始和結(jié)束均在車場。文中將任務(wù)類型分為四種，是為了突出這種運(yùn)輸類型的特點(diǎn)。雖然仿真算例中按就近原則給出的初始方案可行性較高，且經(jīng)過優(yōu)化計(jì)算后的調(diào)度方案效果進(jìn)一步提高，但初始方案和優(yōu)化算法中仍有進(jìn)一步改進(jìn)的余地。

現(xiàn)有文獻(xiàn)對甩掛運(yùn)輸車輛調(diào)度方案優(yōu)劣的判別標(biāo)準(zhǔn)是牽引車行駛路線最短，且所有牽引任務(wù)的起點(diǎn)和終點(diǎn)均固定。本文考慮到牽引車在不同載重狀態(tài)下包括油耗、磨損在內(nèi)的成本顯然不同，因此定義了牽引車運(yùn)行成本作為評判調(diào)度方案的準(zhǔn)則。另外，空掛車需求任務(wù)的起點(diǎn)和多余空掛車運(yùn)出任務(wù)的終點(diǎn)都未必是車場，使得這種車輛調(diào)度計(jì)算的復(fù)雜性增加。

[1]孫輝泰,賀亦軍.甩掛運(yùn)輸是我國發(fā)展綠色貨運(yùn)的必然選擇[J].物流科技,2012,(1):107-108.

[2]Gerdessen J C.Vchicle Routing Problem with Trailers[J].European Journal of Operational Research,1996,93(1):135-147.

[3]Scheuerer S.A Tabu Search Heuristic for the Truck and Trailer Routing Problem[J].Computers and Operations Research,2006,33(4):894-909.

[4]Lin S W,Yu V F,Chou S Y.Solving the Truck and Trailer Routing Problem Based on a Simulated Annealing Heuristic[J].Computers and Operations Research,2009,36(5):1683-1692.

[5]Juyoung Wy,Byung-InKim.A hybrid Metaheuristic Approach for the Rollon rolloff Vehicle Routing Problem[J].Computers and Operations Research,2013,40:1947-1952.

[6]Roberto Baldacci,Lawrence Bodin,Aristide Mingozzi.The Multiple Disposal Facilities and Multiple Inventory Locations Rollon-rolloff Vehicle Routing Problem[J].Computers and Operations Research,2006,33:2667-2702.

[7]Juyoung Wy,Byung-In Kim,Seongbae Kim.The Rollon-rolloff Waste Collection Vehicle Routing Problem with Time Windows[J].European Journal of Operational Research,2013,224:466-476.

[8]A M Benjamin,J E Beasley.Metaheuristics for the Waste Collection Vehicle Routing Problem with Time Windows,Driver Rest Period and Multiple Disposal Facilities[J].Computers and Operations Research,2010,37:2270-2280.

[9]Ulrich Derigs,René Kurowsky,Ulrich Vogel.Solving a Real-worldVehicle Routing Problem with Multiple Use of Tractors and Trailers and EU-regulations for Drivers Arising in Air Cargo Road Feeder Services[J].European Journal of Operational Research,2011,213:309-319.

[10]高洪濤,李紅啟.道路甩掛運(yùn)輸組織技術(shù)及其應(yīng)用實(shí)踐[M].北京:中國物資出版社,2012.

[11]李晴.甩掛運(yùn)輸經(jīng)濟(jì)效益的定量計(jì)算[J].物流工程與管理,2011,33(8):19-22.

[12]胡志華,曹楊,王云霞.集裝箱集散的空重箱循環(huán)甩掛調(diào)度方法[J].武漢理工大學(xué)學(xué)報(bào),2012,34(10):68-73.

[13]溫旖旎.甩掛運(yùn)輸?shù)倪\(yùn)作模式設(shè)計(jì)及其車輛調(diào)度問題研究[D].廣州:華南理工大學(xué),2012.

[14]范寧寧.煙大滾裝甩掛運(yùn)輸牽引車調(diào)度優(yōu)化研究[D].大連:大連海事大學(xué),2012.

[15]梁波.大型鋼鐵企業(yè)廠內(nèi)車輛循環(huán)甩掛運(yùn)輸模式研究[D].長沙:中南大學(xué),2009.