李紅啟，常馨玉，朱曉寧，盧　越

(1.北京航空航天大學(xué)　交通科學(xué)與工程學(xué)院，北京　100191；2.北京交通大學(xué)　交通運輸學(xué)院，北京　100044；

3.北京華運交通咨詢開發(fā)公司，北京　100038)

?

城際干線甩掛運輸?shù)墓窢恳囌{(diào)度問題及其求解

李紅啟1，常馨玉1，朱曉寧2，盧越3

(1.北京航空航天大學(xué)交通科學(xué)與工程學(xué)院，北京100191；2.北京交通大學(xué)交通運輸學(xué)院，北京100044；

3.北京華運交通咨詢開發(fā)公司，北京100038)

摘要：針對城際干線甩掛運輸過程所涉及的公路牽引車調(diào)度，以整車運輸和“多對多”式運輸需求為基本特征，兼顧駕駛員與牽引車連續(xù)工作時間的約束，并以貨運噸公里CO2排放量為目標(biāo)函數(shù)，提出了城際干線運輸中的牽引車調(diào)度問題。構(gòu)建了LTDP問題的整數(shù)規(guī)劃模型, 設(shè)計了基于模擬退火的求解算法主流程，輔以可選用的、針對主流程運算結(jié)果的后處理操作，以進一步提升滿意解。該算法被運用于山東省城際干線甩掛運輸網(wǎng)絡(luò)實踐算例求解。運算結(jié)果表明：本文所構(gòu)建的整數(shù)規(guī)劃模型及其啟發(fā)式求解方法是可行和有效的，干線甩掛運輸模式具有良好的節(jié)能減排效果。

關(guān)鍵詞：運輸經(jīng)濟；牽引車調(diào)度；模擬退火；甩掛運輸；干線

0引言

甩掛運輸被廣泛應(yīng)用于道路運輸領(lǐng)域，其本質(zhì)上是一種基于道路貨運車輛調(diào)度的貨運運力資源配置模式[1]。經(jīng)濟發(fā)達國家在20世紀(jì)60年代就已盛行汽車列車甩掛運輸，該運輸組織形式被推廣應(yīng)用于城際干線運輸、城市配送以及多式聯(lián)運領(lǐng)域。國外甩掛運輸所用的汽車列車組合方式多種多樣，如：卡車拖掛全掛車、牽引車拖掛半掛車、牽引車拖掛半掛車與全掛車等。我國甩掛運輸?shù)陌l(fā)展相對滯后、且目前只允許企業(yè)使用牽引車拖掛半掛車開展甩掛運輸。自2009年交通運輸部等部委聯(lián)合發(fā)布《關(guān)于促進甩掛運輸發(fā)展的通知》以來，物流運輸企業(yè)開展甩掛運輸不僅在體制上面臨的制約越來越少，而且可以獲得多種扶持。

由于可用車型多樣，國外甩掛運輸模式廣泛應(yīng)用于城際干線運輸和城市配送等領(lǐng)域。現(xiàn)階段我國企業(yè)能夠用于開展甩掛運輸?shù)能囆吞攸c決定了城際干線運輸是甩掛運輸模式的主要應(yīng)用領(lǐng)域。城際干線運輸以網(wǎng)絡(luò)化、規(guī)?；卣鞒蔀轶w現(xiàn)甩掛運輸技術(shù)經(jīng)濟優(yōu)勢的依托條件，且城際干線運輸?shù)呢浳锝涣髁看?、運距長，便于實現(xiàn)甩掛運輸貨源組織的規(guī)?；?，這有利于發(fā)揮甩掛運輸?shù)恼囘\輸優(yōu)勢。對于物流運輸企業(yè)而言，在貨源組織和車輛裝備條件都得以保證時，干線甩掛運輸組織工作的重點就是甩掛運輸車輛調(diào)度。

企業(yè)在由傳統(tǒng)卡車運輸模式向甩掛運輸模式轉(zhuǎn)變過程中，需要將其面向單體卡車的調(diào)度方式轉(zhuǎn)變?yōu)槊嫦蚱嚵熊嚨恼{(diào)度模式。同單體卡車相比，汽車列車的動力部分和載貨部分可自由分離與結(jié)合，這就增加了甩掛運輸車輛調(diào)度工作的復(fù)雜性。從調(diào)度作業(yè)對象看，甩掛運輸車輛調(diào)度包括牽引車調(diào)度、載貨半掛車調(diào)度、空半掛車調(diào)度和汽車列車調(diào)度等。企業(yè)實踐中的甩掛運輸車輛調(diào)度往往是綜合化的調(diào)度問題，即上述車輛調(diào)度類型的組合形式。

本文定位于牽引車調(diào)度這一甩掛運輸車輛調(diào)度工作中最為核心的問題，建立公路牽引車調(diào)度問題數(shù)學(xué)模型，設(shè)計求解算法，并開展?fàn)恳囌{(diào)度問題實踐算例的求解與分析。

1既有研究概述

相對于卡車，汽車列車能夠通過動力部分和載貨部分的自由分離和結(jié)合開展甩掛運輸，從而獲得更高的車輛使用效率[2-3]。學(xué)術(shù)界普遍認為汽車列車的調(diào)度問題很復(fù)雜，是NP難題，部分學(xué)者認為傳統(tǒng)車輛調(diào)度問題(Vehicle Routing Problem，VRP)只是汽車列車調(diào)度問題的一個特例[4]。迄今國內(nèi)外學(xué)術(shù)界在該類問題方面的研究成果主要體現(xiàn)為3類(其基本特征對比見表1)：

(1)對于卡車與全掛車組合而成的汽車列車調(diào)

表1　VRP,TTRP,RRVRP和TSRP的一般特征對比

度問題，有關(guān)研究一般稱其為TTRP問題(Truck and Trailer Routing Problem)。TTRP問題可敘述為：一些客戶點既可以由汽車列車服務(wù)，也可以由單獨的卡車服務(wù)，而有些客戶點僅能由卡車提供貨運服務(wù)；設(shè)定卡車和掛車數(shù)量已知、路徑上客戶點的運量滿足車輛載運能力約束；求解目標(biāo)是尋找成本最低的車輛路徑集，路徑是閉合的，每個客戶點都只被提供1次貨運服務(wù)。TTRP問題的研究成果以文獻[4-5]等為代表。

(2)迄今學(xué)術(shù)界針對牽引車和半掛車組合的調(diào)度問題的研究工作主要體現(xiàn)為RRVRP問題(Rollon-rolloff Vehicle Routing Problem)。RRVRP問題源于城市垃圾運輸活動，垃圾運輸車將空車廂送到垃圾收集點，車廂裝滿垃圾后，由垃圾運輸車將重車廂運到垃圾集中處理站進行卸車和后續(xù)處理。垃圾運輸車的作業(yè)方式與牽引車加半掛車的汽車列車作業(yè)方式類似。該問題的研究成果以文獻[6-7]等為代表。

(3)另一類針對牽引車和半掛車組合的優(yōu)化運用問題被稱為TSRP問題(Tractor and Semi-trailer Routing Problem)。迄今學(xué)術(shù)界針對TSRP問題的研究背景主要有兩種：短途(配送)運輸和中長途(干線)運輸。TSRP問題的短途運輸應(yīng)用背景包括廠內(nèi)運輸、局部性運輸，如：梁波[8]研究了以大型鋼鐵企業(yè)內(nèi)部物資運輸為背景的TSRP問題；范寧寧[9]建立了以集疏運運營成本最小化為目標(biāo)的數(shù)學(xué)模型來研究煙大滾裝甩掛牽引車調(diào)度問題；張磊磊[10]以LPG煉油廠為牽引車場站、將牽引車加半掛車的汽車列車應(yīng)用于LPG運輸。鑒于該類汽車列車從事運輸活動的規(guī)模經(jīng)濟優(yōu)勢，TSRP問題的干線運輸應(yīng)用前景更被看好。城際干線運輸網(wǎng)絡(luò)的幾乎所有節(jié)點間均可能存在貨運需求，這種節(jié)點間的運輸需求呈現(xiàn)為“多對多”的關(guān)系，與VRP問題的節(jié)點間運輸需求“一對多”的關(guān)系[11]明顯不同。H. Li等[12-13]在城際干線運輸網(wǎng)絡(luò)上界定出TSRP問題。

2數(shù)學(xué)模型與算例設(shè)計

2.1問題特點與數(shù)學(xué)模型

區(qū)別于既有研究工作所提出的TTRP問題和RRVRP問題，本文瞄準(zhǔn)物流運輸企業(yè)運用汽車列車進行甩掛運輸過程中所面對的牽引車調(diào)度這一核心問題，提出城際干線運輸中的牽引車調(diào)度問題(Line-haul Tractor Dispatching Problem，LTDP)。LTDP問題有以下基本特點：

(1)整車運輸

甩掛運輸?shù)幕緝?yōu)勢來源于牽引車和半掛車之間可用很短時間進行分離和結(jié)合作業(yè)，這便于以整個半掛車及其所載貨物作為裝卸和中轉(zhuǎn)單元，從而大大壓縮牽引車在場站內(nèi)因等待裝卸作業(yè)所需的停留時間。LTDP問題可以以半掛車為運輸作業(yè)單位。

(2)“多對多”問題

運輸網(wǎng)絡(luò)由節(jié)點V(包括1個中心場站v0和n個半掛車集散點vi(i=1,2,…,n))和邊A(A={(i,j)|i≠j,i,j=0，1，2，…,n})組成。中心場站是指可以存放大量牽引車、規(guī)模較大、在運輸網(wǎng)絡(luò)中處于樞紐地位的場站；半掛車集散點是指需要貨運服務(wù)并進行半掛車甩掛作業(yè)的節(jié)點，其運輸需求和保有的半掛車數(shù)量均不同。

(3)駕駛員與牽引車連續(xù)工作時間

在甩掛運輸模式中，牽引車的利用率是焦點，而牽引車連續(xù)工作時間與駕駛員工作時間之間聯(lián)系密切。由于人體持續(xù)工作耐力、車輛行駛過程安全要求等因素，駕駛員的法定工作時間是有硬性要求的，如在美國，卡車駕駛員連續(xù)行車時間不能超過10 h，在充分休息8 h的條件下，可在崗15 h(包括用于等待貨物裝卸、車輛維修保養(yǎng)等的停留時間)[14]。牽引車連續(xù)工作時間極大影響著LTDP問題路徑方案的路徑長度。

(4)考慮甩掛運輸節(jié)能減排效果的目標(biāo)函數(shù)

甩掛運輸競爭優(yōu)勢的發(fā)揮依賴于車輛裝備和組織管理技術(shù)，在相應(yīng)的市場條件和軟硬件裝備條件下，甩掛運輸?shù)募夹g(shù)經(jīng)濟特點得以發(fā)揮，由此帶來的效果是道路貨運效率的提升,這意味著以更少的投入獲得更多的產(chǎn)出。道路貨運的投入因素體現(xiàn)為固定成本投入和變動成本投入，其中油耗量是占比較大的一種變動成本；道路貨運的產(chǎn)出因素體現(xiàn)為道路貨運活動所實現(xiàn)的貨物周轉(zhuǎn)量。為同時表征甩掛運輸車輛調(diào)度模式的運輸效率和節(jié)能減排效果，選取“噸公里CO2排放量”作為目標(biāo)函數(shù)。該指標(biāo)越高，說明道路貨運的效率越低，節(jié)能減排效果越差。

與VRP問題和TTRP問題目標(biāo)函數(shù)通常采用的總運距或變動成本等規(guī)模類指標(biāo)不同，噸公里CO2排放量是表征貨運行業(yè)CO2排放效果的基本指標(biāo)[15]，屬于效率類指標(biāo)。在我國甩掛運輸試點工作中，各企業(yè)甩掛運輸試點方案的評價指標(biāo)之一就是CO2排放量，本文選用該指標(biāo)可使研究結(jié)果盡可能貼近我國甩掛運輸企業(yè)實踐。此外，該指標(biāo)是一種相對指標(biāo)，便于進行不同算例計算結(jié)果的橫向比較。

(1)

(2)

(3)

(4)

(5)

(6)

約束條件(1)要求貨運需求滿足率處于一定范圍內(nèi)，約束條件(2)～(4)確保路徑閉合與度平衡，約束條件(5)與(6)為路徑長度約束。

2.2算例

既有相關(guān)研究工作提供了若干基準(zhǔn)算例及其最優(yōu)解，本文依據(jù)目前可獲得的這些算例的最優(yōu)方案，估算最優(yōu)方案下各個算例的噸公里CO2排放量。采用以下基準(zhǔn)算例作為參考：(1)Christofides等[16]提供的14個VRP問題基準(zhǔn)算例。(2)Fisher等[17]提供的6個有容量約束的車輛調(diào)度問題(Capacitated Vehicle Routing Problem,CVRP)問題基準(zhǔn)算例，Christofides等[18]提供的13個CVRP基準(zhǔn)算例，Russell等[19]提供的4個CVRP問題基準(zhǔn)算例，以及Christofides等[16]提供的4個CVRP問題基準(zhǔn)算例，共27個CVRP問題基準(zhǔn)算例。由于不同學(xué)者采用不同求解方法所獲得的某基準(zhǔn)算例的最優(yōu)解不同，某基準(zhǔn)算例可能有多個估算結(jié)果(圖1給出了33個估算結(jié)果)。(3)Chao[4]提供的21個TTRP問題基準(zhǔn)算例。值得注意的是，上述基準(zhǔn)算例一般采用總運距作為目標(biāo)函數(shù)，所以其最優(yōu)方案極有可能與以噸公里CO2排放量為目標(biāo)函數(shù)的最優(yōu)方案有明顯不同。從估算結(jié)果看(圖1)，上述算例最優(yōu)方案的噸公里CO2排放量主要分布在60～140 g/(t·km)之間，且其平均值較為接近。此外，上述算例最優(yōu)方案的總運距波動范圍則在100～1 900 km之間?？梢?，以總運距作為對比指標(biāo)時不適宜各類算例求解結(jié)果之間的橫向比較。

圖1　既有相關(guān)研究中各類基準(zhǔn)算例最優(yōu)解的噸公里CO2排放量估計Fig.1　Estimation of CO2 emissions per ton kilometer of different benchmark instances in existing related researches　　注：各類算例的編號是本文擬定的，每個編號的算例對應(yīng)于本文所采用的某基準(zhǔn)算例。

能夠確定城市節(jié)點間貨運需求量是設(shè)計LTDP問題實踐算例的基本條件。本文參照文獻[20]提供的城際干線運量估算數(shù)據(jù)，以山東省17個地級城市為網(wǎng)絡(luò)節(jié)點，以高速公路為網(wǎng)絡(luò)的邊，抽象設(shè)計若干LTDP問題實踐算例。在這些算例中，以17個地市中的某城市作為中心場站、其他16個地市作為客戶點，可得到17個不同的算例，這些算例的不同求解結(jié)果也反映了不同城市作為中心場站的優(yōu)勢。根據(jù)這些地市之間的貨物交流量，設(shè)定某一開展甩掛運輸業(yè)務(wù)的企業(yè)市場占有率，合理擬定半掛車額定載重及其實載率，可確定山東省城際干線甩掛運輸網(wǎng)絡(luò)每天需滿足的以半掛車數(shù)為單位的貨物交流需求。表2為本文所用算例的山東省地市節(jié)點間的載貨半掛車交流量。

3求解算法

借鑒既有VRP和TTRP問題求解算法的研究成果，采用模擬退火(SA)算法求解LTRP問題，SA算法被既有研究工作證明是可以成功解決汽車列車調(diào)度問題的一類啟發(fā)式算法[6,21]。

3.1算法主流程

LTDP問題數(shù)學(xué)模型的約束條件(5)與(6)為構(gòu)造可行的牽引車運行路線的基本依據(jù)。在對算例進行試算時，采用“牽引車數(shù)量=貨運需求總量/a”，式中a為經(jīng)驗值。在重復(fù)SA優(yōu)化過程中增加牽引車數(shù)，使得貨運需求滿足率持續(xù)提高，可確定合適的牽引車數(shù)。

牽引車數(shù)量是求解LTDP問題SA算法的首要參

表2　LTDP實踐算例的載貨半掛車交流量(單位：veh)

數(shù)，求解結(jié)果與牽引車數(shù)量有很大關(guān)系。牽引車數(shù)量的確定方法包含最優(yōu)牽引車數(shù)量Mbest的確定和最優(yōu)牽引車路線方案的確定，以下是牽引車數(shù)量Mbest的算法求解基本流程。

Step 1: 取初始牽引車數(shù)量為經(jīng)驗值M=D/a(式中D為貨運需求總量;a為經(jīng)驗值)。

Step 2: 根據(jù)牽引車運行路線的總運距約束構(gòu)造可行的牽引車路線集合V,隨機選取M條牽引車路線作為初始解X。

Step 5: 內(nèi)循環(huán)計數(shù)q=q+1。

Step 6: 從V中隨機選取1條牽引車路線，替換X中隨機1條牽引車路線，生成新的解Z。

Step 7: Metropolis準(zhǔn)則判定(k為步長參數(shù))。

根據(jù)Metropolis準(zhǔn)則第1個判定條件，比較路線方案X和Z的貨運需求滿足率，若Δ=R(Z)-R(X)≥0，則將X替換為Z，即X=Z；若R(z)-R(X)<0， 進入Metropolis準(zhǔn)則的第2個判定條件，設(shè)r為0至1之間的隨機數(shù)，若exp(Δ×k/T)>r，則將X替換為為Z，即X=Z。

Step 9: 內(nèi)循環(huán)終止判定。

內(nèi)循環(huán)終止準(zhǔn)則要求達到設(shè)定的內(nèi)循環(huán)次數(shù)。若在等溫下q達到內(nèi)循環(huán)次數(shù)Ne，即q=Ne，則進入下一次外循環(huán)，T計數(shù)，q置零，即T=T×k,q=0；若q

Step 10: 外循環(huán)終止判定。

鄧小平同志在聽取朱基同志關(guān)于浦東新區(qū)“金融先行、貿(mào)易興市、基礎(chǔ)鋪路、東西聯(lián)動”的規(guī)劃宗旨匯報時，老人家即興講了一段振聾發(fā)聵的話：“金融很重要，是現(xiàn)代經(jīng)濟的核心，金融搞好了，一著棋活，全盤皆活。上海過去是金融中心，是貨幣自由兌換的地方，今后也要這樣搞。中國在金融方面取得國際地位，首先要靠上海。這個要好多年以后，但是現(xiàn)在就要做起。”當(dāng)時，我有幸在旁邊聆聽，受到極大震撼，覺得這段話是世界級的、非常深刻的至理名言，于是就記了下來。

外循環(huán)終止準(zhǔn)則要求達到外循環(huán)末溫。若外循環(huán)未達到終止溫度TF，即T-TF>0，回到Step 4；若T-TF≤0，終止SA算法外循環(huán)過程。

Step 11: 設(shè)R1,R2為擬達到的貨運需求滿足率邊界。若貨運需求滿足率RbestR2，則使M=M-1，回到Step 2；若貨運需求滿足率R1≤Rbest≤R2，則得到最優(yōu)牽引車數(shù)量Mbest，Mbest=M。

在牽引車數(shù)量Mbest確定后，可以以Mbest為已知量進行牽引車路線方案的求解，牽引車路線方案的算法求解流程總體上與牽引車數(shù)量求解流程一致，只是在Step 1直接取牽引車數(shù)為Mbest；此外，外循環(huán)終止判定環(huán)節(jié)增加另外一種準(zhǔn)則：若外循環(huán)獲得高于R2的貨運需求滿足率和低于第2.1節(jié)所建模型的目標(biāo)函數(shù)值Cbest，則回到Step 4；否則，終止SA算法外循環(huán)過程。

3.2后處理

后處理過程針對SA算法求解所得的滿意解，該過程是可選的，對特定算例滿意解有較好的再優(yōu)化效果。后處理包括兩方面，一是刪除空駛路段，二是對路段進行重新整合使其滿足路徑長度約束，具體步驟如下：(1)考察滿意方案中每條路線的路段是否為牽引車獨自行駛路段，將那些所包含的路段全部為這種路段的路線直接從方案中刪除；(2)考察滿意方案中每條路線的路段是否為這種路段，找出其所包含的路段中除了一段有普通貨運，其他路段全部為牽引車獨自行駛路段的路線；(3) 若將第(2)步中找出的路線刪除，則為了保證需求滿足率，必須把擬刪除的這些路線中有普通貨運的那條路段加到合適的路線上；(4)對經(jīng)過調(diào)整后的最終路線方案進行統(tǒng)計，更新統(tǒng)計指標(biāo)。

4算例求解

在本文所構(gòu)建的LTDP問題數(shù)學(xué)模型中，駕駛員與牽引車連續(xù)工作時間是牽引車路徑優(yōu)化過程的重要約束因素，這必然將模型解的可行域大大壓縮。貨運需求滿足率可能會因貨運需求分布、中心場站分布等的不同而難以達到100%。為確保獲得不同算例的滿意解，本文在對山東省城際干線甩掛運輸網(wǎng)絡(luò)算例進行求解時，將貨運需求滿足率分別設(shè)定為85%和100%兩種情況。選取一汽集團生產(chǎn)的平頭柴油半掛牽引車(型號CA4250P66K24T1A1HE)和山東魯峰專用汽車公司生產(chǎn)的兩軸廂式運輸半掛車(型號ST9351XXY)。根據(jù)交通運輸部發(fā)布的《道路運輸車輛燃料消耗量達標(biāo)車型表》的有關(guān)信息，當(dāng)車輛行駛速度定為50 km/h時，牽引車拖掛半掛車行駛的油耗取為32 L/(100 km)，牽引車獨自行駛的油耗取為18 L/(100 km)。

在山東省17個地市中，有6個地市作為中心場站時可以達到100%的貨運需求滿足率，這些城市包括：濟南、青島、淄博、濰坊、泰安、萊蕪?？傮w看，這幾個地市是交通區(qū)位較優(yōu)、貨源規(guī)模較大的城市。將貨運需求滿足率設(shè)為85%(在LTDP問題模型中取η1=85%，η2=86%)，則對17個算例的求解結(jié)果如表3所示。

表3　貨運需求滿足率為85%時各算例甩掛運輸牽引車調(diào)度方案求解結(jié)果

除了以威海、菏澤為中心場站的算例外，其他算例的貨運需求滿足率均達到了85%，噸公里CO2排放量的平均值為78.11 g/(t·km)。

參考既有相關(guān)研究結(jié)論，比較全國、山東省、臺灣省、美國、歐盟等國家和地區(qū)道路貨運噸公里CO2排放量的平均水平，以及由本文2.2節(jié)選定的既有基準(zhǔn)算例以總運距為目標(biāo)函數(shù)的最優(yōu)解的噸公里CO2排放量(圖2)?？梢?，理論研究層面的算例優(yōu)化計算結(jié)果優(yōu)于實踐。相對于VRP，CVRP，TTRP問題基準(zhǔn)算例，本文算例的求解效果更好一些。原因是在基于城際干線運輸過程的公路牽引車調(diào)度求解算例中，干線運輸車輛噸位較大且運距較長，規(guī)模經(jīng)濟效應(yīng)明顯。

圖2　各類算例的噸公里CO2排放量求解效果對比Fig.2　Comparison of solving results of CO2 emission per ton-kilometer in different instances　　注：全國和山東省數(shù)據(jù)來源于文獻[22]；臺灣省數(shù)據(jù)來源于文獻[23]；美國數(shù)據(jù)來源于文獻[24]；歐盟數(shù)據(jù)來源于文獻[25]。

由上述算例運算工作，有以下3點值得注意：

(1)由于每個工作日內(nèi)牽引車連續(xù)工作總時間決定了牽引車路徑的合理長度區(qū)間，城際干線甩掛運輸網(wǎng)絡(luò)上中心場站的位置、貨運需求的空間分布等因素對牽引車調(diào)度方案設(shè)計具有重要的影響，應(yīng)科學(xué)權(quán)衡貨運服務(wù)水平(貨運需求滿足率水平)和牽引車工作時間利用之間的關(guān)系。另一方面，本文的算例求解結(jié)果在一定程度上表明了中心場站選址與牽引車調(diào)度之間的密切關(guān)系，可考慮將牽引車調(diào)度方案和牽引車場站選址有機結(jié)合。

(2)在甩掛運輸模式下，每條牽引車路線上拖掛半掛車的數(shù)量是重要參數(shù)之一，在一定程度上可表征運輸網(wǎng)絡(luò)上牽引車的使用效果。本文的算例求解工作表明，每條牽引車路線上拖掛半掛車約為4臺；求解效果越好的算例，每條牽引車路線能拖掛的半掛車數(shù)量越多一些。企業(yè)應(yīng)盡可能采取措施提高每條路線上拖掛半掛車的數(shù)量。

(3)牽引車的駕駛員配備方式對于牽引車連續(xù)工作時間具有直接影響，這也決定了牽引車調(diào)度方案的形式。城際干線運輸網(wǎng)絡(luò)可能處于城市群，也可能處于較大地理空間范圍內(nèi)，這就使運距參差不一。當(dāng)駕駛員乘組包括2名及以上駕駛員時，每臺牽引車可以服務(wù)于更多的半掛車集散點，承擔(dān)更多的運輸需求，也可減少牽引車的保有和使用總量。

5結(jié)論

現(xiàn)階段我國企業(yè)能夠用于開展甩掛運輸?shù)能囆蜑闋恳囃蠏彀霋燔?，這決定了城際干線運輸是當(dāng)前我國發(fā)展甩掛運輸模式的主要應(yīng)用領(lǐng)域。結(jié)合當(dāng)前我國有關(guān)企業(yè)的甩掛運輸試點實踐，本文提出了以貨運噸公里CO2排放量為目標(biāo)函數(shù)的LTDP問題，該類問題面向“多對多”式的城際整車運輸需求，尊重駕駛員工作時間和牽引車連續(xù)工作時間等實踐要求。針對LTDP問題的整數(shù)規(guī)劃模型，設(shè)計了基于模擬退火的求解算法主流程，并輔以可選用的、針對主流程運算結(jié)果的后處理操作。算例表明，本文所構(gòu)建的LTDP問題整數(shù)規(guī)劃模型及其啟發(fā)式求解方法是可行的。現(xiàn)階段我國甩掛運輸試點企業(yè)往往在原有單體卡車運輸線路的基礎(chǔ)上將其改造為甩掛運輸線路，較多采用的甩掛運輸形式是“一線兩點，兩端甩掛”。從本文經(jīng)過求解獲得的牽引車路線方案看，較為理想的牽引車路線往往是若干“一線兩點，兩端甩掛”模式的組合，這種組合過程很復(fù)雜。在較大規(guī)模的城際干線運輸網(wǎng)絡(luò)中開展甩掛運輸，一般難以用傳統(tǒng)的、人工調(diào)度方式確定牽引車調(diào)度方案，應(yīng)考慮借助運籌優(yōu)化技術(shù)。

參考文獻：

References:

[1]李紅啟，高洪濤．甩掛運輸操作技術(shù)與方法[M]．北京：中國物資出版社，2012．

LI Hong-qi,GAO Hong-tao. Operational Technology and Method of Tractor and Semitrailer Transportation[M]. Beijing: China Logistics Press,2012.

[2]SEMET F,TAILLARD E. Solving Real-life Vehicle Routing Problems Efficiently Using Tabu Search[J]. Annals of Operations Research,1993,41(4):469-488.

[3]李亞茹．提高道路運輸效率的有效途徑: 甩掛運輸[J]．公路交通科技，2004，21(4)：119-122．

LI Ya-ru. Semi-trailer Swap Transport: An Effective Way to Improve Road Transport Efficiency[J]. Journal of Highway and Transportation Research and Development,2004,21(4): 119-122.

[4]CHAO I M. A Tabu Search Method for the Truck and Trailer Routing Problem[J]. Computers and Operations Research,2002,29(1): 33-51.

[5]VILLEGAS J G,PRINS C,PRODHON C,et al. A Matheuristic for the Truck and Trailer Routing Problem[J]. European Journal of Operational Research,2013,230(2): 231-244.

[6]BODIN L,MINGOZZI A,BALDACCI R,et al. The Rollon-rolloff Vehicle Routing Problem[J]. Transpor-tation Science,2000,34(3):271-288.

[7]BALDACCI R,BODIN L,MINGOZZI A. The Multiple Disposal Facilities and Multiple Inventory Locations Rollon-rolloff Vehicle Routing Problem[J]. Computers & Operations Research,2006,33(9): 2667-2702.

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

LIANG Bo. Research on Semi-trailer Loop Swap Transportation Applied in Large-scale Iron and Steel Works[D]. Changsha: Central South University,2009.

[9]范寧寧．煙大滾裝甩掛運輸牽引車調(diào)度優(yōu)化研究[D]．大連：大連海事大學(xué)，2012．

FAN Ning-ning. Research on Tractor Optimization Scheduling of Ro-Ro Left-hanging Transportation from Yantai to Dalian[D]. Dalian: Dalian Martime University,2012.

[10]張磊磊．LPG循環(huán)甩掛運輸調(diào)度優(yōu)化研究[D]．大連：大連海事大學(xué)，2013．

ZHANG Lei-lei. Research on LPG Cycle Drop and Pull Transport Optimization Scheduling[D]. Dalian: Dalian Martime University,2013.

[12]LI H,LI Y,ZHAO Q,et al. The Tractor and Semitrailer Routing Considering Carbon Dioxide Emissions[J/OL]. Mathematical Problems in Engineering,2013,Article ID 509160,1-12[2015-09-10].http://dx.doi.org/10.1155/2013/509160.

[13]LI H,LI Y,LU Y,et al. The Effects of the Tractor and Semitrailer Routing Problem on Mitigation of Carbon Dioxide Emissions[J/OL]. Discrete Dynamics in Nature & Society,2013,Article ID 80935,1-414[2015-09-10]. http://dx.doi.org/10.1155/2013/809135.

[14]HERTZ R P. Hours of Service Violations among Tractor-trailer Drivers[J]. Accident Analysis and Prevention,1991,23(1):29-36.

[15]IERLAND E V,GRAVELAND C,HUIBERTS R. An Environmental Economic Analysis of the New rail Link to European Main Port Rotterdam[J]. Transportation Research Part D: Transport & Environment,2000,5(3):197-209.

[16]CHRISTOFIDES N,MINGOZZI A,TOTH P. The Vehicle Routing Problem[M]//CHRISTOFIDES N,MINGOZZI A,TOTH P,et al. Combinatorial Optimiza-tion. London: John Wiley and Sons,1979.

[17]FISHER M L. Optimal Solution of Vehicle Routing Problems Using Minimum K-trees[J]. Operations Research,1994,42(4):626-642.

[18]CHRISTOFIDES N,EILON S. An Algorithm for the Vehicle-dispatching Problem[J]. Operational Research Quarterly,1969,20(3):309-318.

[19]RUSSELL R,IGO W. An Assignment Routing Problem[J]. Networks,1979,9(1):1-17.

[20]高洪濤，李紅啟．道路甩掛運輸組織技術(shù)及其應(yīng)用實踐[M]．北京：中國物資出版社，2011．

GAO Hong-tao,LI Hong-qi. Operational Method and Application of Tractor and Semitrailer Transportation[M]. Beijing: China Logistics Press,2011.

[21]LIN S W,YU V F,CHOU S Y. A Note on the Truck and Trailer Routing Problem[J]. Expert Systems with Applications,2010,37(1): 899-903.

[22]李紅啟．山東省甩掛運輸發(fā)展規(guī)劃研究[R]．北京：北京航空航天大學(xué)，2013．

LI Hong-qi. Research on Developing Plan of Tractor and Semitrailer Transportation in Shandong Province[R]. Beijing: Beihang University,2013.

[23]LIAO C H,TSENG P H,LU C S. Comparing Carbon Dioxide Emissions of Trucking and Intermodal Container Transport in Taiwan[J]. Transportation Research Part D: Transport & Environment,2009,14(7):493-496.

[24]DAVIS S C,DIEGEL S W,BOUNDY R G. Transportation Energy Data Book: Edition 32[R]. Oak Ridge: Oak Ridge National Laboratory,2011.

[25]European Environment Agency. Transport at a Crossroads-TERM 2008: Indicators Tracking Transport and Environment in the European Union[M]. Luxembourg: Office for Official Publications of the European Communities,2009.

Intercity Line-haul Tractor Dispatching Problem in Trailer Pick-up Transport and Its Solving MethodLI Hong-Qi1, CHANG Xin-Yu1, ZHU Xiao-Ning2, LU Yue3

(1. School of Transportation Science and Engineering, Beihang University, Beijing 100191, China; 2. School of Traffic and

Transportation, Beijing Jiaotong University, Beijing 100044, China; 3. Beijing Huayun Traffic Consulting and Development

Corporation, Beijing 100038, China)

Abstract：We put forward the line-haul tractor dispatching problem (LTDP) on the background of tractor dispatching involved in intercity line-haul trailer pick-up transport. In the LTDP, the transport demand is full-truck load which exists between any two customer depots (the many-to-many demand). The continuous working time lengths of driver and tractor are regarded as the important constraints. The objective function of LTDP is CO2emissions per ton-kilometer. We founded an integer programming model of LTDP, which is solved by a designed algorithm which takes simulated annealing (SA) as the main frame, and also provided an optional phase to improve the satisfactory solution get by the main frame. The algorithm is used to solve a realistic instance abstracted from the intercity line-haul trailer pick-up transport network in Shandong Province. The computation result shows that the the established integer programming model and the heuristic algorithm is feasible and valid, and line-haul trailer pick-up transport is more energy-efficient emissions-decreasing than truck transportation.

Key words：transport economics; tractor dispatching; simulated annealing; trailer pick-up transport; line-haul

文獻標(biāo)識碼：A

文章編號：1002-0268(2016)02-0151-08

中圖分類號：U492.3+31

doi:10.3969/j.issn.1002-0268.2016.02.023

作者簡介：李紅啟(1977-)，男，山東平度人，博士后.(lihongqi@buaa.edu.cn)

基金項目：國家自然科學(xué) (71202016)

收稿日期：2014-07-18