汽車列車調(diào)度問題研究綜述

李紅啟，呂 潭

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

汽車列車調(diào)度問題研究綜述

李紅啟，呂 潭

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

針對學界在汽車列車調(diào)度問題方面的研究成果，以TTRP問題、RRVRP問題和TSRP問題等為分類，梳理各類汽車列車調(diào)度問題的基本形式，從數(shù)學模型構(gòu)建、求解算法設(shè)計與實現(xiàn)等主要方面明確既有學術(shù)研究進展，并分析各類汽車列車調(diào)度問題的異同點。各類汽車列車調(diào)度問題尚有很大的研究空間，其中TTRP問題和RRVRP問題研究工作趨向于求解方法和計算效果的提升，TSRP問題研究工作趨向于基本模型確定與求解方法設(shè)計。

車輛調(diào)度；汽車列車；甩掛運輸；TTRP問題；RRVRP問題；TSRP問題

一、引 言

從世界各國交通運輸發(fā)展狀況看，公路貨物運輸普及最廣，無論在貨運量還是在貨物周轉(zhuǎn)量方面，多數(shù)國家的公路貨物運輸都占據(jù)明顯優(yōu)勢。公路貨物運輸在運輸和物流體系中占據(jù)重要地位的同時，也面臨降低物流成本和節(jié)能減排的巨大壓力[1-2]。相對于大規(guī)模建設(shè)拓展高等級公路等運輸基礎(chǔ)設(shè)施和大范圍推廣應(yīng)用高技術(shù)裝備水平的汽車而言，優(yōu)化貨運汽車的調(diào)度管理方法是提高公路貨物運輸效率、降低成本的更便捷高效的途徑[2-3]。

貨運汽車是由動力部分和載貨部分組成的[4]。從世界各國運輸行業(yè)發(fā)展實踐看，貨運汽車可分為兩大類(見圖1①公路貨運汽車的種類繁多，本示意圖僅簡要羅列最基本的類型，而這些最基本的類型可區(qū)分出本文所關(guān)注的對象。實際上，這4種類型可由車軸結(jié)構(gòu)與數(shù)量、輪胎數(shù)、可拖掛的掛車等的不同而衍生出多種派生類型。)：卡車(圖1中類型Ⅰ)和汽車列車(圖1中的類型Ⅱ、Ⅲ、Ⅳ)。汽車列車是由卡車、牽引車、全掛車、半掛車等通過特定組合而成，卡車或牽引車是汽車列車的動力部分，卡車的載貨車廂、全掛車和半掛車是汽車列車的載貨部分。

圖1 公路貨運汽車基本類型

隨著汽車制造與運用技術(shù)進步，世界各國物流運輸企業(yè)越來越多地采用汽車列車從事物流活動。以美國為例，盡管汽車列車保有量只占所有在冊貨運車輛總數(shù)的2%，但汽車列車的平均車公里是單體卡車平均車公里的5倍，汽車列車實現(xiàn)的車公里占所有貨車車公里的11%，消耗了美國運輸業(yè)能耗總量的27%[5]。20世紀40年代美國卡車承擔的貨物周轉(zhuǎn)量占公路貨物周轉(zhuǎn)總量的57%，近年則降至10%以內(nèi)，而汽車列車承擔的貨物周轉(zhuǎn)量比重從20世紀40年代的40%左右上升到目前的90%以上[6]。相對于卡車，汽車列車能夠通過動力部分和載貨部分的自由分離和結(jié)合實現(xiàn)甩掛運輸，從而獲得更高的車輛使用效率[7-9]。

學術(shù)界普遍認為汽車列車的調(diào)度問題很復(fù)雜，是NP難題，部分學者認為傳統(tǒng)車輛調(diào)度問題(vehicle routing problem，簡稱VRP)只是汽車列車調(diào)度問題的一個特例[10-12]。由于世界上貨運和物流企業(yè)可選用的汽車列車組合方式多種多樣，這就使汽車列車調(diào)度問題有很多的具體研究對象，迄今國內(nèi)外學術(shù)界在汽車列車調(diào)度問題方面的研究成果主要體現(xiàn)為三類：TTRP問題、RRVRP問題和TSRP問題。

二、VRP問題簡介

VRP問題(車輛調(diào)度問題)于20世紀50年代提出[13]，迄今學術(shù)界獲得了豐富的VRP問題研究成果。經(jīng)典VRP問題即帶容量限制的VRP問題(the capacitated vehicle routing problem，簡稱CVRP)，可描述如下：G=(V,A)為有向網(wǎng)絡(luò)，V={0,1,2,…,n}表示網(wǎng)絡(luò)中的節(jié)點集合，其中點0表示網(wǎng)絡(luò)的中心場站，場站保有m輛同類型的卡車，容量為Q(也即車輛載運能力)，其余點均為客戶點，各點的需求量為qi；A={(i,j)∣i,j∈V,i≠j}表示網(wǎng)絡(luò)中各點間弧的集合，車輛在每段弧上的行駛成本為cij。車輛從場站出發(fā)，最終回到場站；每個客戶點能且只能被一輛車服務(wù)；每輛車行駛路徑上的客戶點需求總和不能超過Q；車輛行駛路徑的長度不能超過L。定義0-1決策變量xijk，xijk=1表示車輛k(k∈M={1,2,…,m})經(jīng)過弧(i,j)，dij為各弧的長。CVRP問題數(shù)學模型如下：

目標函數(shù)：

(1.1)

約束條件：

(1.2)

(1.3)

(1.4)

(1.5)

(1.6)

(1.7)

目標函數(shù)(1.1)表示車輛行駛總成本最小化；約束條件(1.2)和(1.3)要求車輛路徑閉合；約束條件(1.4)表示每個客戶點只被一輛車服務(wù)，且只被服務(wù)一次；約束條件(1.5)為車輛容量約束；約束條件(1.6)為車輛路徑的長度約束。CVRP問題數(shù)學模型還有其他表示形式，可參見文獻[14]和文獻[15]。此外，上述CVRP問題模型若增加其他約束條件，就可成為不同類型的CVRP拓展問題，如帶時間窗VRP問題(VRPTW)、多場站VRP問題(MDVRP)、帶集貨VRP問題(VRPB)、多車型VRP問題(HVRP)等。

三、TTRP問題

對于卡車與全掛車組合而成汽車列車(圖1中的類型Ⅱ)的調(diào)度問題，有關(guān)研究一般稱其為TTRP問題(truckandtrailerroutingproblem)。TTRP問題就是[12]：一些客戶點既可以由汽車列車服務(wù)，也可以由單獨的卡車服務(wù)，而有些客戶點僅能由卡車提供貨運服務(wù)；設(shè)定卡車和掛車數(shù)量已知，路徑上客戶點的運量滿足車輛載運能力約束；求解目標是尋找成本最低的車輛路徑集，這些路徑的起訖點都在中心場站，每個客戶點都只被提供一次貨運服務(wù)。既有研究工作可分為三類：針對近似TTRP問題的研究成果、針對基本TTRP問題的研究成果和針對拓展TTRP問題的研究成果。

1.近似TTRP問題

在學術(shù)界關(guān)注TTRP問題早期，有學者根據(jù)卡車加掛全掛車的汽車列車類型在企業(yè)的應(yīng)用實踐抽象出一類車輛調(diào)度問題，這類汽車列車調(diào)度問題與后來提出的基本TTRP問題有很多相似但尚未形成明確的數(shù)學描述，本文將之稱為近似TTRP問題。

Semet等[7]較早研究若干小賣部(連鎖店)利用21輛卡車和7輛掛車進行貨物配送的車輛調(diào)度問題。配送客戶點被分為卡車客戶點和汽車列車客戶點兩類，卡車客戶點僅允許卡車進行配送，不允許汽車列車進行配送，汽車列車客戶點允許卡車或汽車列車進行配送。車輛路徑分為卡車路徑和汽車列車路徑，汽車列車路徑包括主路徑和子路徑，其中主路徑中只包含汽車列車客戶點，汽車列車在主路徑上某一客戶點臨時甩下掛車后，可只用卡車對卡車客戶點進行配送，從而得到以汽車列車客戶點為起止點的子路徑。Semet[16]后來將上述問題定義為PAVRP問題(partialaccessibilityconstrainedvehicleroutingproblem)，車輛路徑被分為三類：①卡車單獨行駛路徑，其中包括卡車客戶點和汽車列車客戶點；②汽車列車行駛路徑，僅包括汽車列車客戶點，不含子路徑；③汽車列車行駛路徑，包含主路徑和子路徑。同時假定主路徑上任一客戶點最多只能有一條子路徑，且掛車不裝載卡車客戶點的貨物。

Gerdessen[17]將一類卡車加掛全掛車的路徑問題定義為VRPT問題(vehicleroutingproblemwithtrailers)，設(shè)定汽車列車與卡車的行駛速度不同，并定義了“調(diào)遣時間”(manoeuvringtime)的概念，對于可達性差的客戶點，使用卡車進行服務(wù)相比于使用汽車列車進行服務(wù)可明顯地節(jié)省時間，客戶點據(jù)此分為可達和不可達等兩類。假設(shè)任意客戶點的貨運需求均為單位需求，每個客戶點都可作為掛車的臨時?？奎c，且最多只能停靠一次。

2.基本TTRP問題

在近似TTRP問題研究基礎(chǔ)上，學術(shù)界提出針對卡車加掛全掛車路徑問題的、相對確定的數(shù)學描述[10]，這一描述為后來眾多研究所沿用?；綯TRP問題為：令：G=(V,E)為運輸網(wǎng)絡(luò)，V={0,1,2,…,n}為點集，其中點0為場站，其余點為客戶點，E為各點間弧的集合。客戶點分為兩類：一類是卡車客戶點(簡稱TC)，只允許卡車進行配送；另一類是汽車列車客戶點(簡稱VC)，既允許汽車列車又允許卡車進行配送。車輛路徑分為三類：第一類稱為PTR，路徑中的客戶點(可以同時包含VC和TC)均由卡車進行配送；第二類稱為PVR，路徑中的客戶點(只包含VC)均由汽車列車進行配送；第三類稱為CVR，路徑包含一條主路徑(只包含VC)和至少一條以主路徑上某一客戶點為起止點的子路徑(可以同時包含VC和TC)，且卡車與掛車可以在路徑上的特定客戶點處進行貨物換裝。設(shè)定場站保有mk輛卡車和ml輛掛車(mk≥ml)，載重容量分別為Qk和Ql，各客戶點的需求為qi(i∈V{0})。在可行解中，PVR和CVR路徑共有ml條，PTR路徑為mk-ml條。對于PTR，所有客戶點的需求總量不能超過Qk；對于PVR，所有客戶點的需求總量不能超過Qk+Ql；對于CVRP，所有客戶點的需求總量不能超過Qk+Ql，單個子路徑上客戶點的需求總量不能超過Qk。求解目標是：所有路徑的總長度最小化。

基于路徑分類，Villegas等[18]就上述基本TTRP問題建立如下數(shù)學模型：令N=Nt∪Nv={1,2,…,n}為網(wǎng)絡(luò)中客戶點集合，Nt和Nv分別為TC和VC集合。以Ω表示TTRP的所有可行路徑集合，Г?Ω表示PTR集合，Ψ?Ω表示PVR集合，Π?Ω則表示CVR集合。定義0-1變量aij、bik、eil、xj、yk和zl，aij=1表示客戶點i在路徑j(luò)(j∈Г)上，bik=1表示客戶點i在路徑k(k∈Ψ)上，eil=1表示客戶點i在路徑l(l∈Π)上，xj=1、yk=1和zl=1分別表示路徑j(luò)、k和l在最終解中。以cr表示路徑r(r∈Ω)的長度，mt和mr分別表示卡車和掛車數(shù)量。

目標函數(shù)：

(2.1)

約束條件：

(2.2)

(2.3)

(2.4)

(2.5)

(2.6)

(2.7)

(2.8)

目標函數(shù)(2.1)尋求解中所有路徑的總長度最小化；約束條件(2.2)表示VC可以存在于三種不同的路徑中，每個VC都被服務(wù)且只被服務(wù)一次；約束條件(2.3)表示TC可以存在于PTR和CVR中，且每個TC都被服務(wù)且只被服務(wù)一次；約束條件(2.4)和(2.5)分別表示卡車和牽引車總數(shù)約束。

3.拓展TTRP問題

在基本TTRP問題模型中增加或改變某些約束條件，可得到一些拓展TTRP問題。如：

(1)RTTRP問題(relaxed truck and trailer routing problem)[19]。將基本TTRP問題中對卡車和掛車數(shù)量的約束條件去掉，就是RTTRP問題。

(2)TTRPTW問題(truck and trailer routing problem with time windows)[20]。針對客戶點可能存在服務(wù)時間段要求，為每個客戶點添加時間窗[ETi,LTi]，就形成TTRPTW問題。

(3)ETTRP問題(extended truck and trailer routing problem)。在基本TTRP問題中，所有的VC均可停放掛車，都可作為子路徑的始終點，但實踐中并非所有的客戶點都有條件作為臨時的掛車停放點。Zitz[21]就此提出ETTRP問題，設(shè)立獨立的掛車?？奎c，同一個?？奎c可以位于多條路徑上。ETTRP問題還兼顧考慮各客戶點的服務(wù)時間窗，且不允許卡車和掛車之間的貨物換裝。

(4)GTTRP問題(generalized truck and trailer routing problem)[22]。GTTRP問題增加“中轉(zhuǎn)站”這種站點類型(中轉(zhuǎn)站與VC位置不同且無運輸需求)，汽車列車可以在VC和中轉(zhuǎn)站停放掛車，允許卡車與掛車之間的貨物換裝，GTTRP問題同時考慮混合車隊、時間窗以及車輛的變動成本和固定成本。

4.TTRP問題的求解

算例是驗證汽車列車調(diào)度問題數(shù)學模型及其求解算法可行性和有效性的必需條件，既有研究對于汽車列車調(diào)度問題算例的生成方式主要有兩種：以企業(yè)實際的運輸網(wǎng)絡(luò)和運輸活動為基礎(chǔ)生成算例，其中需對個別指標或參量進行預(yù)處理；以已有VRP問題基準算例為基礎(chǔ)生成新算例。用精確算法求解TTRP問題會面臨很多困難，既有研究主要采用啟發(fā)式算法。用于TTRP問題求解的啟發(fā)式算法主要有以下幾種：

(1)以禁忌搜索算法為主。Semet等[7]使用標準禁忌搜索算法對由企業(yè)實踐活動提煉出的TTRP問題(算例包含45個小賣部，各小賣部訂單需求數(shù)在70～90個)進行求解，涉及21臺卡車與7臺掛車的調(diào)度，求解獲得了優(yōu)于企業(yè)既有車輛調(diào)度方案的結(jié)果。Chao[10]提出兩階段算法：構(gòu)造算法和禁忌搜索優(yōu)化，并在算法中融入確定性退火偏差概念；參照既有的7個VRP測試問題，構(gòu)建出21個TTRP測試算例(客戶點規(guī)模為50～199個)，這些算例也被后來的研究工作當作TTRP問題基準算例。Scheuerer[11]提出兩種面向TTRP問題解的構(gòu)造算法，采用禁忌搜索算法予以優(yōu)化，對禁忌搜索算法的各個參數(shù)進行較為細致的靈敏度分析，并對Chao[10]提供的21個算例進行求解，得到更優(yōu)的計算結(jié)果。

(2)以模擬退火算法為主。Lin等[12]將模擬退火算法應(yīng)用于TTRP問題求解，在針對21個基準算例的計算結(jié)果中，有11個新的最優(yōu)解和6個已知的最優(yōu)解，說明用模擬退火算法求解TTRP更為有效，且模擬退火算法的平均計算時間要少于其他既有算法。此外，文獻[19]和文獻[20]分別應(yīng)用模擬退火算法對RTTRP和TTRPTW問題進行求解。

(3)以鄰域搜索算法為主。Villegas等[23]綜合運用貪婪隨機自適應(yīng)、變鄰域搜索和先路徑后聚類的方法對TTRP問題進行求解，也是采用21個基準算例，計算結(jié)果表明該綜合化算法能夠得到的優(yōu)化結(jié)果要優(yōu)于已知最優(yōu)結(jié)果。Villegas等[18]綜合運用貪婪隨機自適應(yīng)和迭代鄰域搜索算法來獲得局部最優(yōu)解，采用了兩組測試算例，其中一組是既有的21個基準算例，另一組是來自Lin等[19]提供的36個隨機算例(客戶點數(shù)量為75～150個)，實驗結(jié)果表明該文提供的算法能夠得到與既有最優(yōu)結(jié)果十分相近的結(jié)果，但求解速度要快于既有算法。

四、RRVRP問題

采用牽引車加半掛車組合開展貨物運輸時，車輛的動力部分(牽引車)雖然不能承載貨物，但其調(diào)度更加靈活，牽引車獨自行駛時可節(jié)省可觀的燃料消耗量。迄今學術(shù)界針對牽引車加掛半掛車組合的運用問題研究工作主要體現(xiàn)在兩方面：RRVRP問題和TSRP問題。RRVRP問題源于城市垃圾運輸活動，針對車廂可卸式的垃圾運輸車。垃圾運輸車將空車廂送到垃圾收集點，車廂裝滿垃圾后，由垃圾運輸車將重車廂運到垃圾集中處理站進行卸車和后續(xù)處理。垃圾運輸車的作業(yè)方式與牽引車加掛半掛車的汽車列車作業(yè)方式類似，可將車廂可卸式垃圾運輸車的動力部分和載貨部分分別對應(yīng)為牽引車和半掛車。

1.基本RRVRP問題

De Meulemeester等[24]研究單場站、多客戶點、多處理站的掛車調(diào)度問題，本文視其為RRVRP問題的早期形式?？蛻酎c分為居民區(qū)客戶點和工業(yè)區(qū)客戶點。居民區(qū)客戶點的服務(wù)類型有：①牽引車將空掛車送往客戶點，并空駛回場站；②牽引車空駛到客戶點，將重掛車帶回場站。工業(yè)區(qū)客戶點的服務(wù)類型為：①牽引車將空掛車送往客戶點，并空駛回場站；②牽引車空駛到客戶點，帶上重掛車，將其送往處理站，待處理后將空掛車帶回場站。

Bodin等[25]將城市垃圾運輸問題定義為RRVRP問題(rollon-rolloff vehicle routing problem)。令G=(V,A)表示運輸網(wǎng)絡(luò)，V和A分別為點集和弧集，網(wǎng)絡(luò)上有一個場站v0和一個處理站vd。場站為牽引車行駛路徑的起止點，處理站是將重掛車轉(zhuǎn)變?yōu)榭諕燔嚨狞c，還作為空掛車的存儲站。由于每臺牽引車一次只能拖掛一輛掛車，針對任意客戶點牽引車都會有一個完整的服務(wù)過程。令T={1,2,…,n}表示n個服務(wù)過程的集合，Mi=(si,vi1,vi2,…,viki,ei)為服務(wù)過程的向量表示，將服務(wù)過程分為四類：①Mi=(si,vd,ei)，其中si,ei∈V{v0,vd}，牽引車在si點帶上重掛車將其送到處理站，等待處理后再將空掛車運往ei點，通常情況下si=ei；②Mi=(si,vi1,ei)，其中si=ei=vd且Vi1∈V{v0,vd}，牽引車在處理站掛上空掛車將其送到客戶點vi1處，再掛上重掛車返回處理站；③Mi=(si,ei)，其中si=vd且ei∈V{v0,vd}，牽引車在處理站掛上空掛車將其送到客戶點ei處；④Mi=(si,ei)，其中ei=vd且si∈V{v0,vd}，牽引車將客戶點處的重掛車帶回處理站。

目標函數(shù)：

(3.1)

約束條件：

(3.2)

(3.3)

(3.4)

(3.5)

目標函數(shù)(3.1)尋求車輛空駛總時間的最小化，約束條件(3.2)為類型①、③和④服務(wù)過程的分類約束，約束條件(3.3)確保所有類型②的服務(wù)過程都包含于路徑中，約束條件(3.4)將類型②服務(wù)過程包含于路徑中時滿足時間約束。

2.拓展RRVRP問題

拓展形式的RRVRP問題主要將站點類型、服務(wù)類型、車輛裝備類型等特定約束予以拓展或變形。

Baldacci等[26]將站點類型增加到四種，新增用于存放未被使用空掛車的空掛車存放站，并將處理站和存放站數(shù)量擴展為多個，形成M-RRVRP問題(multiple disposal facilities and multiple inventory locations RRVRP)。掛車類型也可細分，牽引車可以拖帶任意一種掛車，不同存放站所能存放的掛車類型不同，不同處理站所能處理的掛車類型也不同。Baldacci等[26]將M-RRVRP視為TVRP-MG問題(the time constrained vehicle routing problem on a multigraph)的特例。

Wy等[27]為各站點添加了時間窗約束，形成RRVRPTW問題(RRVRP with time windows)，并增加了兩種服務(wù)類型：①牽引車空駛到客戶點，掛上掛車將其送到最近的存放站；②牽引車在場站掛上重掛車，將其送到合適的處理站。

3.RRVRP問題的求解

迄今出現(xiàn)過針對RRVRP問題的精確算法，如Baldacci等[26]提出針對M-RRVRP問題的精確算法，該算法主要參考不同類型松弛問題模型的三個邊界。絕大多數(shù)研究工作采用啟發(fā)式算法求解RRVRP問題。

Bodin等[25]提供4組共20個不同類型的RRVRP問題測試算例，算例中服務(wù)過程數(shù)分別為50、75、100、150、199，并分別使用分解算法、部分枚舉法、服務(wù)過程嵌入/服務(wù)過程優(yōu)化算法和模擬退火4種算法對測試算例進行求解，4種啟發(fā)式算法均能得到合理的結(jié)果，其中部分枚舉法得到的結(jié)果最優(yōu)，而模擬退火的計算速度最快。Derigs等[28]基于局部搜索和大鄰域搜索來求解RRVRP問題，并以Bodin等[25]提供的20個算例及其結(jié)果作為比較標準，計算結(jié)果表明該文的混合算法要好于既有算法。Wy等[29]針對RRVRP問題提出基于群體計算、并包含大鄰域搜索和多種優(yōu)化算法的混合啟發(fā)式算法，選擇Bodin等[25]提供的20個測試算例作為驗證算法性能的基準算例，得到17個更優(yōu)的結(jié)果。

Baldacci等[26]選擇了三種不同類型的測試算例。第一類是根據(jù)既有CVRP問題基準算例設(shè)計的2組共8個M-RRVRP算例，其服務(wù)過程數(shù)分別為30、50、60和70；第二類是選自Bodin等[25]提供的6個RRVRP基準算例；第三類是11個既有CVRP算例(客戶點數(shù)在50～100個)。計算結(jié)果表明，該文提出的精確算法能夠得到大多數(shù)算例的最優(yōu)解或近似最優(yōu)解。

Wy等[27]針對RRVRPTW問題提出基于迭代運算的大鄰域搜索算法，其中包含構(gòu)造算法和路徑內(nèi)優(yōu)化、路徑間優(yōu)化等多種優(yōu)化策略。該文選取34個基準算例，其中14個算例來自美國某家垃圾處理公司(客戶點需求量取值包括6、16、20、21、25、26、30、291)，另外20個算例由人工生成(客戶點需求量取值包括35、58、132、185)。計算結(jié)果表明該文提出的算法能夠減少牽引車數(shù)量及其總的行駛時間，當計算時間設(shè)定為10分鐘時，該算法得到最優(yōu)結(jié)果在總行駛時間上要比實踐采用的車輛調(diào)度方案縮短5.95%。

五、TSRP問題

牽引車加半掛車組合的汽車列車由于采用大噸位半掛車而具備更高的生產(chǎn)效率，由于裝卸甩掛作業(yè)而具備更高的集裝化調(diào)配中轉(zhuǎn)效率，牽引車加掛車組合的汽車列車能夠?qū)崿F(xiàn)規(guī)?；\輸。針對牽引車加半掛車組合的調(diào)度問題研究工作尚有更大的學術(shù)拓展空間，多數(shù)既有研究成果繼承了VRP問題和TTRP問題的思維模式，迄今學術(shù)界尚沒有形成廣泛認可的牽引車加半掛車優(yōu)化調(diào)度問題的基本模型。本文把針對牽引車加半掛車組合而成汽車列車的優(yōu)化運用問題稱為TSRP問題(tractor and semi-trailer routing problem)。迄今學術(shù)界針對TSRP問題的研究背景主要有兩種：短途(配送)運輸和中長途(干線)運輸。

TSRP問題的短途運輸應(yīng)用背景包括廠內(nèi)運輸、局部性運輸。梁波[30]研究以大型鋼鐵企業(yè)內(nèi)部物資運輸為背景的TSRP問題。將大型鋼鐵廠內(nèi)的生產(chǎn)單元、倉庫、發(fā)貨站臺及各點之間的路徑抽象為運輸網(wǎng)絡(luò)，兩點之間的運輸需求看作運輸任務(wù)。場站僅作為牽引車?？康?，場站沒有運輸任務(wù)。該文所構(gòu)建的數(shù)學模型包括以下主要部分：目標函數(shù)為牽引車使用量和牽引車行駛費用的最小化；約束條件包括牽引車拖掛能力限制、路徑閉合、時間窗約束、運輸任務(wù)序列約束等。范寧寧[31]將煙大滾裝甩掛牽引車調(diào)度問題抽象為具有雙重時間窗的甩掛車輛調(diào)度問題，建立以集疏運運營成本最小化為目標的數(shù)學模型，約束條件包括：牽引車的狀態(tài)只能是掛上掛車、甩下掛車、等待或者行駛，牽引車在某地所掛上的重掛車或者向某地配備的空掛車數(shù)受該地貨運需求的約束，時間窗約束，等。張磊磊[32]將牽引車加半掛車的汽車列車應(yīng)用于LPG運輸，以LPG煉油廠為牽引車場站，以總成本(包括牽引車油耗成本、違反時間窗限制的懲罰成本和牽引車派出成本)最小為目標，約束條件包括：牽引車數(shù)量約束、牽引車的額定載重量約束、牽引車行駛最大限定里程約束、節(jié)點上牽引車數(shù)量平衡約束、路徑閉合、牽引車到發(fā)時間約束等。

1.基本TSRP問題

目標函數(shù)：

(4.1)

約束條件：

(4.2)

(4.3)

(4.4)

(4.5)

(4.6)

(4.7)

目標函數(shù)(4.1)表示噸公里二氧化碳排放量的最小化，其本質(zhì)上為變動成本最小化；約束條件(4.2)表示網(wǎng)絡(luò)中所有客戶點的需求都得到滿足；約束條件(4.3)和(4.4)表示每輛牽引車進出場站至少一次；約束條件(4.5)表示任意一輛牽引車進出某一點的次數(shù)相等；約束條件(4.6)和(4.7)為路徑長度約束。

2.TSRP問題的求解

由于暫未形成相對固定的牽引車加半掛車優(yōu)化調(diào)度問題的基本模型，面向TSRP問題的算例主要有兩種：來自企業(yè)實踐的算例和計算機生成的隨機算例。

梁波[30]采用禁忌搜索算法，對衡鋼集團廠內(nèi)車輛循環(huán)甩掛運輸活動進行研究，算例中的網(wǎng)絡(luò)節(jié)點數(shù)為12個。范寧寧[31]采用節(jié)約算法對煙大滾裝甩掛運輸問題求解，實例分析中網(wǎng)絡(luò)節(jié)點數(shù)為8個。張磊磊[32]使用禁忌搜索算法求解某實踐算例，算例中LPG公司管轄范圍內(nèi)共7個網(wǎng)絡(luò)節(jié)點，節(jié)點間共有9項LPG運輸任務(wù)。

Li等[33]和Li等[34]提出干線運輸網(wǎng)絡(luò)背景下的TSRP問題模擬退火算法，該文一方面借助MATLAB程序隨機生成40個網(wǎng)絡(luò)節(jié)點數(shù)為5～8個的小規(guī)模隨機算例，另一方面選擇以我國山東省17地市為節(jié)點的干線運輸網(wǎng)絡(luò)，并輔以貨運數(shù)據(jù)的實踐算例。隨機算例和實踐算例計算結(jié)果表明該文所采用的啟發(fā)式算法具備可行性和有效性。

六、各類汽車列車調(diào)度問題的異同點

貨物周轉(zhuǎn)量(即實際運送貨物噸數(shù)及貨物平均運距之積)是物流運輸活動的主要統(tǒng)計指標，其不僅包含運輸對象數(shù)量，還考慮運輸距離因素，因而能夠全面地反映物流運輸生產(chǎn)成果。從這個統(tǒng)計指標看，描述物流運輸活動時應(yīng)兼顧車輛和運距因素。對于不同實際應(yīng)用背景下的一系列車輛調(diào)度運用問題，從運輸車輛類型的角度，可分為依托卡車的VRP問題和依托汽車列車的VRP問題；從運輸距離的角度，可分為末端配送/短途運輸過程的VRP問題和中長途干線運輸?shù)腣RP問題。迄今學術(shù)界針對車輛調(diào)度運用問題的研究工作非常豐富，可將既有研究工作大致地予以歸類，見表1。

表1 車輛調(diào)度運用問題研究工作的大致歸類

無論是哪種車輛調(diào)度運用問題，其在優(yōu)化類數(shù)學模型描述方面都有一些相同之處，主要包括：①目標函數(shù)涵蓋兩方面，首先是尋求變動成本最小化，其次是尋求所需車輛數(shù)的最少化；②單中心場站問題往往要求車輛路徑是閉合的；③主要的約束條件旨在確保車輛路徑的連續(xù)性；④節(jié)點的度約束，即要求途經(jīng)客戶點的行駛車輛入度與出度平衡；⑤每條車輛路徑的長度有上限約束；⑥車輛載重有上限約束；⑦除了基本TSRP問題，一般要求客戶點只由1臺車進行貨運服務(wù)，且只服務(wù)1次，這就使可行的車輛路徑中每個客戶點不重復(fù)出現(xiàn)。

由于不同類型車輛的技術(shù)經(jīng)濟優(yōu)勢有明顯的差異，相應(yīng)車輛調(diào)度問題的研究背景、研究定位可能存在明顯的不同。以包含1個中心場站(v0)和n個末端站/客戶點(vi,i=1,2,…,n)的運輸網(wǎng)絡(luò)為例：

(1)貨運需求。將貨運需求分為三類：由v0發(fā)往vi的貨運量記為d=(d01,d02,…,d0n)；由vi發(fā)往v0的貨運量記為p=(p10,p20,…,pn0)；n個末端站/客戶點兩兩之間的貨物流量記為

(5)優(yōu)化模型。目標函數(shù)為運輸過程的變動成本最小化MinTC′·T+SC′·S。主要約束條件包括：

第一類，路徑連續(xù)性和路徑閉合約束；第二類，車輛動力部分和載貨部分的數(shù)量約束，k·T≥S；第三類，設(shè)定車輛動力部分由一個中心場站存放，則由節(jié)點發(fā)出的車輛數(shù)量和到達該節(jié)點的車輛動力部分數(shù)量相等，即PA0·T=0；第四類，貨運需求約束有三：由場站發(fā)往客戶點的貨物量PA2·S≥d，由客戶點發(fā)往場站的貨物量PA1·S≥p，客戶點之間貨物交流需求的約束。

七、結(jié) 語

汽車列車是由公路牽引車或卡車等動力部分，和半掛車或全掛車等載貨部分組合而成，且動力部分和載貨部分可自由分離與結(jié)合。相比于單體卡車，汽車列車有其明顯的技術(shù)經(jīng)濟優(yōu)勢。自20世紀90年代以來，特別是在最近數(shù)年，汽車列車調(diào)度問題越來越成為國際學術(shù)界廣泛關(guān)注的研究熱點。本文對迄今國內(nèi)外學術(shù)界在汽車列車調(diào)度問題方面的研究成果進行初步梳理，將汽車列車調(diào)度問題分為TTRP問題、RRVRP問題和TSRP問題等大類，明確了各類汽車列車調(diào)度問題的基本形式及其演化過程，從數(shù)學模型構(gòu)建、求解算法設(shè)計與實現(xiàn)等方面總結(jié)既有學術(shù)研究進展。各類汽車列車調(diào)度問題尚有很大的研究拓展空間，值得學術(shù)界進一步重視。其中，TTRP問題和RRVRP問題研究工作可重點關(guān)注求解方法設(shè)計和計算效果提升等方面；而尚待明確基本數(shù)學模型的TSRP問題，其研究工作可更多地側(cè)重于優(yōu)化模型構(gòu)建、求解方法設(shè)計實現(xiàn)、基準算例設(shè)計等方面。

[1]LéONARDIJ,BAUMGARTNERM.CO2efficiencyinroadfreighttransportation:Statusquo,measuresandpotential[J].TransportationResearchPartD, 2004, 9(6):451-464.

[2]KAMAKATéF,SCHIPPERL.TrendsintruckfreightenergyuseandcarbonemissionsinselectedOECDcountriesfrom1973to2005 [J].EnergyPolicy, 2009, 37(10):3743-3751.

[3]SUZUKIY.Anewtruck-routingapproachforreducingfuelconsumptionandpollutantsemission[J].TransportationResearchPartD, 2011, 16(1):73-77.

[4]DREXLM.Applicationsofthevehicleroutingproblemwithtrailersandtransshipments[J].EuropeanJournalofOperationalResearch, 2013, 227(2):275-283.

[5]DAVISSC,DIEGELSW,BOUNDYRG.TransportationEnergydatabook2011[EB/OL]. [2015-04-18].http://www-cta.ornl.gov/data/index.shtml.

[6]徐亞華，謝家舉，譚小平．美國卡車貨運及甩掛運輸發(fā)展的經(jīng)驗與啟示[J]．交通建設(shè)與管理，2011(3)：36-40.

[7]SEMETF,TAILLARDE.Solvingreal-lifevehicleroutingproblemsefficientlyusingtabusearch[J].AnnalsofOperationsResearch, 1993, 41(4):469-488.

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

[9]高洪濤，李紅啟．道路甩掛運輸組織理論與實踐[M]．北京：人民交通出版社，2010．

[10]CHAOIM.Atabusearchmethodforthetruckandtrailerroutingproblem[J].ComputersandOperationsResearch, 2002, 29(1):33-51.

[11]SCHEUERERS.Atabusearchheuristicforthetruckandtrailerroutingproblem[J].ComputersandOperationsResearch, 2006, 33(4): 894-909.

[12]LINSW,YUVF,CHOUSY.Solvingthetruckandtrailerroutingproblembasedonasimulatedannealingheuristic[J].ComputersandOperationsResearch, 2009, 36(5):1683-1692.

[13]DANTZIGGB,RAMSERJH.Thetruckdispatchingproblem[J].ManagementScience, 1959, 6(1):80-91.

[14]LAPORTEG.Fiftyyearsofvehiclerouting[J].TransportationScience, 2009, 43(4):408-416.

[15]BALDACCIR,TOTHP,VIGOD.Recentadvancesinvehicleroutingexactalgorithms[J]. 4OR:AQuarterlyJournalofOperationsResearch, 2007, 5(4):269-298.

[16]SEMETF.Atwo-phasealgorithmforthepartialaccessibilityconstrainedvehicleroutingproblem[J].AnnalsofOperationsResearch1995, 61(1):45-65.

[17]GERDESSENJC.Vehicleroutingproblemwithtrailers[J].EuropeanJournalofOperationalResearch, 1996, 93(1):135-147.

[18]VILLEGASJG,PRINSC,PRODHONC,etal.Amatheuristicforthetruckandtrailerroutingproblem[J].EuropeanJournalofOperationalResearch, 2013, 230(2):231-244.

[19]LINSW,YUVF,CHOUSY.Anoteonthetruckandtrailerroutingproblem[J].ExpertSystemswithApplications, 2010, 37(1):899-903.

[20]LINSW,YUVF,LUCC.Asimulatedannealingheuristicforthetruckandtrailerroutingproblemwithtimewindows[J].ExpertSystemswithApplications, 2011, 38(12):15244-15252.

[21]ZITZR.Algorithmsforthetruckandtrailerroutingproblem[D].Odense:SyddanskUniversitet, 2010.

[22]DREXLM.Branchandpriceandheuristiccolumngenerationforthegeneralizedtruckandtrailerroutingproblem[J].RevistadeMétodosCuantitativosparalaEconomíaylaEmpresa, 2011, 12(1): 5-38.

[23]VILLEGASJG,PRINSC,PRODHONC,etal.AGRASPwithevolutionarypathrelinkingforthetruckandtrailerroutingproblem[J].Computers&OperationsResearch, 2011, 38(9):1319-1334.

[24]DEMEULEMEESTERL,LAPORTEG,LOUVEAUXFV,etal.Optimalsequencingofskipcollectionsanddeliveries[J].JournaloftheOperationalResearchSociety, 1997, 48(1): 57-64.

[25]BODINL,MINGOZZIA,BALDACCIR,etal.Therollon-rolloffvehicleroutingproblem[J].TransportationScience2000, 34(3):271-288.

[26]BALDACCIR,BODINL,MINGOZZIA.Themultipledisposalfacilitiesandmultipleinventorylocationsrollon-rolloffvehicleroutingproblem[J].Computers&OperationsResearch, 2006, 33(9):2667-2702.

[27]WYJ,KIMBI,KIMS.Therollon-rolloffwastecollectionvehicleroutingproblemwithtimewindows[J].EuropeanJournalofOperationalResearch, 2013, 224(3):466-476.

[28]DERIGSU,PULLMANNM,VOGELU.AshortnoteonapplyingasimpleLS/LNS-basedmetaheuristictotherollon-rolloffvehicleroutingproblem[J].Computers&OperationsResearch, 2013, 40(3):867-872.

[29]WYJ,KIMBI.Ahybridmetaheuristicapproachfortherollon-rolloffvehicleroutingproblem[J].Computers&OperationsResearch, 2013, 40(8):1947-1952.

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

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

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

[33]LIHongqi,LIYanran,LUYue,etal.Theeffectsofthetractorandsemitrailerroutingproblemonmitigationofcarbondioxideemissions[J].DiscreteDynamicsinNatureandSociety, 2013(12):1-14.

[34]LIHongqi,LIYanran,ZHAOQiuhong,etal.Thetractorandsemitrailerroutingconsideringcarbondioxideemissions[J].MathematicalProblemsinEngineering, 2013(12):1-12.

《大連海事大學學報(社會科學版)》投稿須知

1．來稿應(yīng)具有創(chuàng)新性、學術(shù)性、科學性、規(guī)范性和可讀性，要求論點明確，論據(jù)充分，層次清晰，資料可靠，文字精練。

2．收稿范圍：經(jīng)濟學、管理學、法學、政治學、哲學、海洋文化、語言學、文學等領(lǐng)域的研究論文，重點刊發(fā)航運經(jīng)濟、航運管理、海商法、海洋政治、海洋文化等方面的論文。

3．作者可通過本刊E-mail(skxb@dlmu.edu.cn)投稿，自交稿之日起，若1個月內(nèi)未收到本刊通知，可自行處理。

4．來稿應(yīng)附中文題名、英文題名、作者姓名及其漢語拼音、單位及所在城市和郵編、摘要、關(guān)鍵詞、中圖分類號。

5．在稿件首頁地腳處注明第一作者和導師(如論文作者系研究生)簡介(包括姓名、出生年、性別、學歷、職稱、聯(lián)系電話、E-mail及詳細通信地址)，有基金項目支持的稿件應(yīng)注明論文所屬項目的正式名稱及項目編號。

6．論文題名應(yīng)恰當簡明地反映文章的特定內(nèi)容，一般不超過20字，盡量不使用副題名；英文題名應(yīng)與中文題名含義一致。

7．論文摘要盡量寫成報道性摘要，一般應(yīng)包括以下4項內(nèi)容：研究目的；研究方法和過程；結(jié)果；結(jié)論。摘要應(yīng)客觀真實，不摻雜作者的主觀見解，不作模棱兩可的結(jié)論，要求結(jié)構(gòu)嚴謹，語意確切，充分反映文章的主題范圍及內(nèi)容梗概。摘要長度一般為200～300字。摘要一律采用第三人稱表述，不使用“本文”、“作者”等作為主語。

8．關(guān)鍵詞應(yīng)反映論文主題、研究對象及所屬學科范疇，一般選擇3～8個，一般不采用英文縮寫。

9．圖、表應(yīng)精選，有自明性，并隨文出現(xiàn)。插圖須符合制圖規(guī)范，且可在Visio繪圖軟件上打開、編輯。表格一律用三線表。

10．參考文獻應(yīng)是文中直接引用的公開出版物，以期刊論文為主。本刊參考文獻采用順序編碼制格式著錄，論文中引用依出現(xiàn)的先后以阿拉伯數(shù)字排列，并在右上角用方括號標注。

11．本刊有權(quán)對來稿進行文字性刪改，如不同意，請在來稿中注明。

12．本刊已被“中國期刊網(wǎng)”、“萬方數(shù)據(jù)——數(shù)字化期刊群”及“中文科技期刊數(shù)據(jù)庫”等數(shù)據(jù)庫全文收錄，如作者不同意將論文編入，請在來稿時聲明。

2015-07-07

國家自然科學基金青年基金項目(71202016)

李紅啟(1977-)，男，博士，講師；E-mail:lihongqi@buaa.edu.cn

1671-7031(2015)06-0001-10

U491

A