李紅啟，呂 潭

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

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

李紅啟，呂 潭

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

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

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

一、引 言

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

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

圖1 公路貨運(yùn)汽車基本類型

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

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

二、VRP問題簡介

VRP問題(車輛調(diào)度問題)于20世紀(jì)50年代提出[13]，迄今學(xué)術(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é)點(diǎn)集合，其中點(diǎn)0表示網(wǎng)絡(luò)的中心場站，場站保有m輛同類型的卡車，容量為Q(也即車輛載運(yùn)能力)，其余點(diǎn)均為客戶點(diǎn)，各點(diǎn)的需求量為qi；A={(i,j)∣i,j∈V,i≠j}表示網(wǎng)絡(luò)中各點(diǎn)間弧的集合，車輛在每段弧上的行駛成本為cij。車輛從場站出發(fā)，最終回到場站；每個(gè)客戶點(diǎn)能且只能被一輛車服務(wù)；每輛車行駛路徑上的客戶點(diǎn)需求總和不能超過Q；車輛行駛路徑的長度不能超過L。定義0-1決策變量xijk，xijk=1表示車輛k(k∈M={1,2,…,m})經(jīng)過弧(i,j)，dij為各弧的長。CVRP問題數(shù)學(xué)模型如下：

目標(biāo)函數(shù)：

(1.1)

約束條件：

(1.2)

(1.3)

(1.4)

(1.5)

(1.6)

(1.7)

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

三、TTRP問題

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

1.近似TTRP問題

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

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

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

2.基本TTRP問題

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

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

目標(biāo)函數(shù)：

(2.1)

約束條件：

(2.2)

(2.3)

(2.4)

(2.5)

(2.6)

(2.7)

(2.8)

目標(biāo)函數(shù)(2.1)尋求解中所有路徑的總長度最小化；約束條件(2.2)表示VC可以存在于三種不同的路徑中，每個(gè)VC都被服務(wù)且只被服務(wù)一次；約束條件(2.3)表示TC可以存在于PTR和CVR中，且每個(gè)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]。針對客戶點(diǎn)可能存在服務(wù)時(shí)間段要求，為每個(gè)客戶點(diǎn)添加時(shí)間窗[ETi,LTi]，就形成TTRPTW問題。

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

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

4.TTRP問題的求解

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

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

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

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

四、RRVRP問題

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

1.基本RRVRP問題

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

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

目標(biāo)函數(shù)：

(3.1)

約束條件：

(3.2)

(3.3)

(3.4)

(3.5)

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

2.拓展RRVRP問題

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

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

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

3.RRVRP問題的求解

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

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

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

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

五、TSRP問題

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

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

1.基本TSRP問題

目標(biāo)函數(shù)：

(4.1)

約束條件：

(4.2)

(4.3)

(4.4)

(4.5)

(4.6)

(4.7)

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

2.TSRP問題的求解

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

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

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

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

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

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

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

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

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

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

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

七、結(jié) 語

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

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

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

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

[9]高洪濤，李紅啟．道路甩掛運(yùn)輸組織理論與實(shí)踐[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)甩掛運(yùn)輸模式研究[D]．長沙：中南大學(xué)，2009．

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

[32]張磊磊．LPG循環(huán)甩掛運(yùn)輸調(diào)度優(yōu)化研究[D]．大連：大連海事大學(xué)，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.

《大連海事大學(xué)學(xué)報(bào)(社會科學(xué)版)》投稿須知

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

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

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

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

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

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

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

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

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

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

11．本刊有權(quán)對來稿進(jìn)行文字性刪改，如不同意，請?jiān)趤砀逯凶⒚鳌?/p>

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

2015-07-07

國家自然科學(xué)基金青年基金項(xiàng)目(71202016)

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

1671-7031(2015)06-0001-10

U491

A