李紅啟 盧 越 朱曉寧

1. 北京航空航天大學，交通科學與工程學院，北京100191

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

3. 北京交通大學，交通運輸學院，北京100044

0 引 言

經(jīng)濟發(fā)達國家在20世紀60年代就已盛行借助汽車列車開展甩掛運輸，該運輸組織形式被廣泛應用于城際干線運輸、城市配送以及多式聯(lián)運等領域。相對于卡車，汽車列車能夠通過動力部分和載貨部分的自由分離和結合而開展甩掛運輸，從而獲得更高的車輛使用效率[1,2]。

學術界普遍認為汽車列車的調度問題很復雜，是NP難題。迄今國內(nèi)外學術界在甩掛運輸汽車列車調度問題方面的研究成果主要體現(xiàn)為三類：（1）針對卡車與全掛車組合而成汽車列車調度的TTRP問題（the Truck and Trailer Routing Problem），研究成果以文獻[3,4]等為代表；（2）針對城市垃圾運輸過程的牽引車加掛半掛車組合而成汽車列車調度的 RRVRP問題（the Rollon-Rolloff Vehicle Routing Problem），研究成果以文獻[5][6]等為代表；（3）針對廠內(nèi)（局部）運輸過程的牽引車加掛半掛車組合而成汽車列車調度問題，研究成果以[7][8][9]等為代表；以及針對城際干線運輸過程的牽引車加掛半掛車組合而成汽車列車調度的TSRP問題，該類問題主要由文獻[10]提出。

從調度作業(yè)對象看，甩掛運輸車輛調度包括牽引車調度、載貨半掛車調度、空半掛車調度和汽車列車調度等。本文定位于城際干線運輸背景下的牽引車調度這一問題，建立一類公路牽引車調度問題數(shù)學模型，設計基于模擬退火的求解算法，并輔以實例分析。

1 問題描述

城際干線甩掛運輸牽引車調度問題將分布于經(jīng)濟地理空間的城市抽象為網(wǎng)絡節(jié)點、將城際高等級公路抽象為網(wǎng)絡的邊。城際干線運輸網(wǎng)絡的幾乎所有節(jié)點間均可能存在貨運需求，這種節(jié)點間的運輸需求呈現(xiàn)為“多對多”的關系，與VRP問題中節(jié)點間運輸需求的“一對多”關系[11]明顯不同。

城際干線甩掛運輸牽引車調度問題的基本特征如下：

（1）從能否保有牽引車角度知網(wǎng)絡節(jié)點分為兩類：中心場站和客戶點。中心場站是唯一的，且保有大量牽引車，也是牽引車運行路線的始發(fā)終到點，牽引車不能長久停留于客戶點；客戶點的運輸需求以載貨半掛車為單元，任意兩個客戶點之間都可以有任意數(shù)量的運輸需求。

（2）在甩掛運輸模式中，牽引車連續(xù)工作時間與駕駛員工作時間之間聯(lián)系密切。由于人體持續(xù)工作耐力、車輛行駛過程安全要求等因素，駕駛員法定工作時間是有硬性要求的。為合理利用牽引車乘組工作時間，每條牽引車運行路線的總運距在一個區(qū)間內(nèi)，允許牽引車在同一運行路線中多次進出中心場站和某一客戶點。牽引車的行駛狀態(tài)只有兩種：牽引車獨自行駛，牽引車拖掛載貨半掛車行駛。也即，本問題不考慮空掛車調配。

（3）牽引車、半掛車車型是同一的，且滿足互換性和匹配性要求。設定牽引車獨自行駛和牽引車拖掛載貨半掛車行駛的平均速度為同一常量；設定牽引車獨自行駛、牽引車拖掛載貨半掛車行駛的百公里油耗量為常量；設定載貨半掛車的額定載重量和貨物實載率為常量。

（4）城際干線甩掛運輸牽引車調度問題的求解目標是“噸公里CO2排放量”（單位：克CO2/噸公里），旨在明確甩掛運輸車輛調度模式的效率和節(jié)能減排效果。依據(jù)聯(lián)合國政府間氣候變化專門委員會（Intergovernmental Panel on Climate Change）提供的CO2排放量計算方法，燃油消耗量與CO2排放量之間為確定的比例關系。

（5）貨運需求滿足率和車輛運行成本間體現(xiàn)為效益背反。對于某個物流運輸企業(yè)而言，在合理權衡運輸服務水平和運輸成本時，有的貨運需求可不予滿足。也即，城際干線甩掛運輸牽引車調度問題可要求貨運需求滿足率達到一定水平（不必為100%）。

（6）求解城際干線甩掛運輸牽引車調度問題后，應能夠確定所需要使用的牽引車總數(shù)及每臺牽引車的運行路線方案，同時給出牽引車運行路線滿意方案的“噸公里CO2排放量”。

能夠確定城市節(jié)點間貨運需求量是設計城際干線甩掛運輸牽引車調度問題實踐算例的基本條件。本文參照文獻[12]提供的城際干線運量估算數(shù)據(jù)，以山東省17地市間貨運活動為應用背景，抽象設計若干城際干線甩掛運輸牽引車調度問題實踐算例。在這些算例中，以17地市中的某一城市作為中心場站、其他16個城市作為客戶點，可得到17個不同的算例。

2 求解算法的基本流程

借鑒既有針對TTRP問題和RRVRP問題等汽車列車調度問題求解算法的研究成果，本文采用模擬退火（SA）算法求解城際干線甩掛運輸牽引車調度問題。SA算法被既有研究工作證明是可以成功解決汽車列車調度問題的一類啟發(fā)式算法（如文獻[5][13][14]）。

2.1 可行鄰域

SA算法可行鄰域的構建過程如圖1所示。牽引車運行路線的總運距要求是構造備選路線的基本依據(jù)。在對新算例進行試驗時，采用“牽引車數(shù)量=貨運需求總量/a”進行，其中a表示經(jīng)驗值。在重復模擬退火優(yōu)化過程中增加牽引車數(shù)，使得滿足率持續(xù)提高，可確定合適的牽引車數(shù)。

圖1 可行鄰域的構建Fig.1 Feasible neighborhood construction

2.2 基本流程

牽引車數(shù)量是SA算法的首要參數(shù)，求解結果與牽引車數(shù)量有很大關系。牽引車數(shù)量的確定方法包含最優(yōu)牽引車數(shù)量Mbest的確定和最優(yōu)牽引車路線方案的確定。以下是牽引車數(shù)量Mbest的算法求解流程：

Step 1 以經(jīng)驗值確定當前牽引車數(shù)量M；

Step 2 由可行鄰域（V）中隨機選取M條牽引車路線作為初始解X；

Step 3 設定初溫T=T0，外循環(huán)計數(shù)變量w=0，內(nèi)循環(huán)計數(shù)變量q=0，貨運滿足率為初始解X的貨運滿足率Rbest=R(X)；

Step 4 外循環(huán)以自然數(shù)遞增計數(shù)；

Step 5 內(nèi)循環(huán)以自然數(shù)遞增計數(shù)；

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

Step 7 Metropolis準則判定（k為步長參數(shù)）：若Δ=R(Z)-R(X)≥0，則將X替換為Z，即X=Z；若R(Z)-R(X)<0，設r為 0至 1之間的隨機數(shù)，若exp(Δ×k/T)>r，則將X替換為為Z，即X=Z；

Step 8 計算當前路線方案Xbest下的Rbest，Xbest=X，Rbest=R(X)；

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

內(nèi)循環(huán)終止準則：達到設定的內(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)終止判定：

外循環(huá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ù)量求解流程一致，不同之處是在Step 1直接取牽引車數(shù)為Mbest，此外，外循環(huán)終止判定準則有所差異。

下面為牽引車路線方案求解算法的偽代碼示意。

Step 1: LetM=Mbest.

Step 2: Generate the initial solutionXrandomly;

Step 3: LetT=T0;w=0;q=0;Rbest=R(X);

Step 4:w=w+1;q=q+1;

Step 5: Generate a solutionYbased onX;

Step 6: If Δ=R(Y)-R(X) ≥0, {LetX=Y;}Else {Generateγ= random (0, 1); If exp(Δ·w2/T) >γ, {LetX=Y;}}

Step 7:Xbest=X,Rbest=R(X);

Step 8: Ifq=Me, {T=τ·T;q=0;} Else {Go to Step 3;}

Step 9: IfC(X) ≤C0,R(X) ≥ηandT-TF>0, {C0=C(X),

Go to Step 3;}Else {Cbest=C0, Terminate the SA heuristics;}

3 算法策略

3.1 復制操作

依據(jù)牽引車運行路線的總運距要求所構造的備選路線總數(shù)決定了可行鄰域規(guī)模，也決定了SA算法的求解效果。在本文所設計的山東省17地市間貨運網(wǎng)絡實例中，不同城市以其經(jīng)濟和交通區(qū)位特點決定了該城市作為中心場站的優(yōu)勢，也就決定了其作為中心場站時可行鄰域規(guī)模上的差異。為擴展鄰域，本文提出面向某一特定路線的復制操作：① 在初始備選路線中，找到各個牽引車路線所途經(jīng)各個客戶點的最大貨運需求量Dmax；② 對各條路線，將其復制為Dmax條相同的路線，從而擴展了鄰域。提出復制操作的主要理由是：根據(jù)牽引車運行路線總運距約束所構造的可行鄰域中，每條備選路線都只在可行解中出現(xiàn)且僅出現(xiàn)1次，這可能導致在產(chǎn)生最終路線方案結果的模擬退火迭代過程中，某條牽引車路線出現(xiàn)多次的幾率很低。但在企業(yè)的物流運輸實踐中，某條牽引車運行路線上可能有多臺車輛并行運行。為此，以復制操作確保優(yōu)秀的運行路線可被多次選中。

以濟南作為中心場站的算例，復制操作前后可行鄰域中牽引車路線總數(shù)分別為25 407條、73 610條，可行鄰域規(guī)模擴充至原先的近3倍。本文仍以該算例進行試驗：在相同的初溫、末溫、退火速度、內(nèi)外循環(huán)規(guī)則、終止判別條件、迭代判別條件、步長規(guī)則等條件下，采用重復10次計算取結果的平均數(shù)來對比可行鄰域擴展前后的求解結果（見表 1），可以發(fā)現(xiàn)增加復制操作環(huán)節(jié)有助于求解效果的改善。此外，增加復制操作環(huán)節(jié)時運算時間稍長。通過固定計算機軟硬件配置來進行試驗，當k取值為0.99時，有無復制操作的運算時間分別為123 s和108 s。

表1 采用復制操作與否的求解結果對比Tab.1 Results comparision of adopting copy operation or not

3.2 步長

k作為SA算法Metropolis準則的步長參數(shù)，其設定方式一般有固定步長和變步長兩種情形。k的設定方式對SA算法的求解結果影響明顯，步長決定了SA過程迭代前期是否能夠快速跳出局部最優(yōu)解和迭代后期是否能夠快速獲得全局最優(yōu)解。

（1）以變步長k=w4（w為迭代次數(shù)）進行試驗

Metropolis準則使一些迭代過程的更新解不會被采納，在本文試驗的4萬余次迭代中，有750余次迭代過程的解被采納（見圖 2）。在該試驗的前 100次迭代過程中，目標函數(shù)值以較快的速度降低至100g/(t·km)以下，而后續(xù)迭代中目標函數(shù)值的降低速度明顯減緩。

圖2 k=w4時被采納的迭代過程Fig.2 The acceptable iterations when k=w4

（2）以固定步長k=104進行試驗

當步長固定為 104次時，在相同的總迭代次數(shù)下，被采納更新解的迭代數(shù)達到近 11 000次，說明Metropolis準則第二條被觸發(fā)的次數(shù)遠遠高于k=w4的試驗。取該試驗最后1 000次被采納更新解的迭代（見圖3），最后1 000次迭代過程的解仍出現(xiàn)明顯幅度的波動。

圖3 k=104時被采納的迭代過程Fig.3 The acceptable iterations when k=104

本文對步長設定規(guī)則做了一系列試驗，試驗主要涉及變步長和固定步長的多種取法，每種步長參數(shù)下重復運算10次并取平均值，結果如表2所示?？梢?，采用不同設定方式的變步長時運算結果波動較小，采用固定步長時的運算結果與步長參數(shù)設定的關系較為明顯。在不同算例中，若采用固定步長，則需進行大量的試驗來確定步長參數(shù)，本文建議以變步長作為步長參數(shù)（可取k=w3）。

表2 步長參數(shù)取值方式試驗Tab.2 Tests of assignment of step-size parameters

3.3 內(nèi)外循環(huán)規(guī)則

對于SA算法內(nèi)外循環(huán)過程對求解效果的影響，本文做了 3組試驗，要求各組試驗的總迭代次數(shù)相同，試驗結果如表3所示。在相同的總迭代次數(shù)下，內(nèi)循環(huán)次數(shù)越多則求解效果越差，且總迭代次數(shù)越少，這種現(xiàn)象越明顯。依靠降溫的外循環(huán)在向最優(yōu)解趨近的速度上要快于內(nèi)循環(huán)。本文建議采用無內(nèi)循環(huán)的策略，以使運算過程在較短時間內(nèi)完成。

表3 模擬退火過程內(nèi)外循環(huán)試驗Tab.3 Tests of inner and outer loop of SA

4 求解結果

在對山東省城際干線甩掛運輸網(wǎng)絡算例進行求解時，貨運需求滿足率設定為不低于 85%。車輛方面，選取一汽集團生產(chǎn)的平頭柴油半掛牽引車（型號CA4250P66K24T1A1HE）和山東魯峰專用汽車公司生產(chǎn)的兩軸廂式運輸半掛車（型號 ST9351XXY）。車輛行駛速度定為50 km/h，牽引車拖掛半掛車行駛的油耗取為 32 L/100km，牽引車獨自行駛的油耗取為18 L/100km。

在山東省的17地市中，有6個地市作為中心場站時可以達到100%的貨運需求滿足率，這些城市包括：濟南、青島、淄博、濰坊、泰安、萊蕪?？傮w來看，這幾個地市是交通區(qū)位較優(yōu)、貨源規(guī)模較大的城市。將貨運需求滿足率設為85%，則對17個算例的求解結果如表4所示（具體路線略）。

表4 貨運需求滿足率為85%時各算例牽引車調度方案求解結果Tab.4 Solving results of the tractor scheduling plan of all the instances when the satisfaction rate is 85%

除了以威海、菏澤為中心場站的算例外，其他算例的貨運需求滿足率均達到了 85%，噸公里 CO2排放量的平均值為78.11 g/(t·km)。該結果較現(xiàn)階段山東省公路貨運行業(yè)的噸公里 CO2排放量水平[15]（約為135 g/(t·km)和我國公路貨運業(yè)的噸公里 CO2排放量水平[16]明顯要低。值得指出的是，本文研究工作是基于城際干線運輸過程的公路牽引車調度算例進行求解，干線運輸車輛噸位較大且運距較長，規(guī)模經(jīng)濟效應明顯。

從本文經(jīng)過求解獲得的牽引車路線方案看，較為理想的牽引車路線往往是若干“一線兩點，兩端甩掛”模式的組合，這種組合過程更為復雜?？梢姡谳^大規(guī)模的城際干線運輸網(wǎng)絡中開展甩掛運輸，一般難以用傳統(tǒng)的、人工調度方式確定牽引車調度方案。應高度重視城際干線運輸牽引車調度工作的復雜性，并特別注重發(fā)揮各種物流信息化技術和人工智能決策技術的支持作用，盡量提高牽引車使用率和運用靈活性，科學設置駕駛員乘組方案；此外，要盡可能地將牽引車調度方案設計工作和牽引車場站選址、建設與運用環(huán)節(jié)有機結合。

5 結束語

城際干線貨運是甩掛運輸模式的主要應用領域之一，本文針對城際干線甩掛運輸過程所用的公路牽引車的優(yōu)化調度問題開展研究。該問題的基本特征包括：干線網(wǎng)絡節(jié)點間貨運需求為“多對多”式，貨運需求以載貨半掛車為計量單位，問題優(yōu)化目標為噸公里碳排放量最小化。本文設計了基于模擬退火的求解算法流程，并借助山東省干線甩掛運輸網(wǎng)絡實踐算例的求解試驗過程，確定算法的主要運算策略：運用復制操作實現(xiàn)可行鄰域規(guī)模擴展，采用變步長，只采用外循環(huán)。求解結果可同時確定牽引車數(shù)量、牽引車路線方案、優(yōu)化目標函數(shù)值。后續(xù)研究工作可從多個角度展開，在模型方面如增加多場站條件、增加時間窗因素、增加半掛車流量平衡要求，等等；在方法方面可尋求求解效率和效果更好的混合啟發(fā)式算法。

[1] Semet F., Taillard E. Solving real-life vehicle routing problems efficiently using tabu search[J]. Annals of Operations Research, 1993, 41(4): 469-488.

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

[3] Chao I.M. A tabu search method for the truck and trailer routing problem[J]. Computers and Operations Research, 2002, 29(1): 33-51.

[4] Villegas J. G., Prins C., Prodhon C., Medaglia A. L.,Velasco N. A matheuristic for the truck and trailer routing problem[J]. European Journal of Operational Research, 2013, 230(2): 231-244.

[5] Bodin L., Mingozzi A., Baldacci R., Ball M. The rollon–rolloff vehicle routing problem[J]. Transportation Science 2000, 34(3):271-288.

[6] 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.

[7] 梁波. 大型鋼鐵企業(yè)廠內(nèi)車輛循環(huán)甩掛[D]．長沙：中南大學，2009．

[8] 范寧寧. 煙大滾裝甩掛運輸牽引車調度優(yōu)化研究[D]．吉林：吉林大學，2012．

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

[10] Li H. Q., Li. Y., Zhao Q., Lu Y., Song Q. The Tractor and Semitrailer Routing Considering Carbon Dioxide Emissions[J]. Mathematical Problems in Engineering,2013, Article ID 509160, 1-12, http:// dx.doi.org/10.1155/2013/509160.

[11] Barcos L., Rodríguez V., álvarez M. J., Robusté F.Routing design for less-than-truckload motor carriers using Ant Colony Optimization[J]. Transportation Research Part E, 2010, 46(3): 367-383.

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

[13] 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.

[14] 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.

[15] 北京航空航天大學，山東省交通運輸廳. 山東省甩掛運輸發(fā)展規(guī)劃研究[R]. 2013．

[16] Li H. Q., Lu Y., Zhang J., et al. Trends in highway freight transportation's carbon dioxide emissions and policies in China [J]. Energy Policy, 2013, 57,99-106.