軌道交通開(kāi)行方案優(yōu)化模型研究綜述

于　劍　張星臣　許　璐

(中國(guó)鐵路經(jīng)濟(jì)規(guī)劃研究院1)　北京　100038)　(北京交通大學(xué)交通運(yùn)輸學(xué)院2) 　北京　100044)

?

軌道交通開(kāi)行方案優(yōu)化模型研究綜述

于劍1)張星臣2)許璐2)

(中國(guó)鐵路經(jīng)濟(jì)規(guī)劃研究院1)北京100038)(北京交通大學(xué)交通運(yùn)輸學(xué)院2)北京100044)

摘要：列車開(kāi)行方案是軌道交通運(yùn)輸組織中的核心技術(shù)計(jì)劃，亦是研究熱點(diǎn)之一.文中總結(jié)了軌道交通列車開(kāi)行方案典型優(yōu)化模型和求解方法，分析了目前研究的不足.優(yōu)化模型方面，歸納出運(yùn)營(yíng)商和旅客2類共14種優(yōu)化目標(biāo)，及車站能力約束、區(qū)間能力約束、車底運(yùn)用約束、乘務(wù)規(guī)則約束、客流關(guān)聯(lián)約束、服務(wù)水平約束、其他相關(guān)約束7類共24種約束條件；求解算法方面，歸納出常用的啟發(fā)式算法和數(shù)學(xué)解析方法2類共13種方法，并指出了現(xiàn)有成果在客流分配和算例規(guī)模方面的不足.

關(guān)鍵詞：鐵路運(yùn)輸；研究綜述；文獻(xiàn)查閱；開(kāi)行方案；優(yōu)化模型；求解方法

于劍(1990- )：男，碩士生，主要研究領(lǐng)域?yàn)榻煌ü芾砉こ?/p>

0引言

列車開(kāi)行方案是軌道交通列車運(yùn)輸組織計(jì)劃的核心內(nèi)容之一，一般包括5項(xiàng)內(nèi)容，即交路計(jì)劃(route/path planning)，開(kāi)行頻率(frequency)、停站計(jì)劃(halting pattern)、列車編組(fleet size)和列車類型(train mode).交路方案.決定列車開(kāi)行的起訖點(diǎn)和經(jīng)由路徑；開(kāi)行頻率.決定某條交路單位時(shí)間內(nèi)的開(kāi)行對(duì)數(shù)，進(jìn)而決定了其服務(wù)能力；停站方案.決定列車在其經(jīng)由路徑內(nèi)的停站方法，對(duì)服務(wù)能力和服務(wù)質(zhì)量有重要影響；編組計(jì)劃.決定列車編組長(zhǎng)度，同樣對(duì)服務(wù)能力有決定性作用；列車類型.決定列車的速度等級(jí)、車型、席位席別等.

開(kāi)行方案從根本上決定了軌道交通服務(wù)產(chǎn)品，問(wèn)題本身又具有高復(fù)雜性，得到了國(guó)內(nèi)外學(xué)者的廣泛重視，相關(guān)文獻(xiàn)數(shù)量較多.以往的研究綜述如王爽等[1]、閆海峰等[2]、左大杰等[3]，強(qiáng)調(diào)了分步求算、循環(huán)迭代的思想，但大都偏重于定性分析，為深入研究開(kāi)行方案編制方法，有必要對(duì)其定量?jī)?yōu)化的主要手段——優(yōu)化模型和求解方法進(jìn)行系統(tǒng)總結(jié).

1典型開(kāi)行方案優(yōu)化模型

大多數(shù)定量研究開(kāi)行方案編制方法的文獻(xiàn)都建立了優(yōu)化模型.鐵路和城市軌道交通雖然因?yàn)楦髯蕴匦缘牟煌谀Ｐ蛢?nèi)容和側(cè)重點(diǎn)上有一定區(qū)別，如鐵路可能將停站優(yōu)化作為重點(diǎn)之一，客流分配也需要考慮列車等級(jí)甚至?xí)r刻表，而城軌可能將開(kāi)行頻率與客流波動(dòng)的匹配作為優(yōu)化重點(diǎn)，客流分配更加注重?fù)Q乘路徑比選等，但模型形式上是相似的，常見(jiàn)的種類有單目標(biāo)模型(如藍(lán)伯雄等[4])、多目標(biāo)模型(如彭其淵等[5])、雙層規(guī)劃模型(如王永亮等[6])等，其中雙層規(guī)劃模型的上層一般用來(lái)評(píng)價(jià)、約束開(kāi)行方案，下層一般用來(lái)進(jìn)行客流分配，且大量文獻(xiàn)認(rèn)為客流分配符合用戶平衡.這些模型雖各有側(cè)重，但仍有較多相似性，現(xiàn)分為優(yōu)化目標(biāo)和約束條件2個(gè)部分對(duì)相關(guān)文獻(xiàn)中的開(kāi)行方案優(yōu)化模型進(jìn)行總結(jié)，其中客流分配是較為獨(dú)立的步驟，作為一大研究方向有大量文獻(xiàn)，此處不做綜述，且各文獻(xiàn)中重復(fù)的優(yōu)化目標(biāo)、約束未全做引用標(biāo)號(hào).

1.1優(yōu)化目標(biāo)

開(kāi)行方案影響著運(yùn)營(yíng)商和旅客的效益，所以絕大多數(shù)模型的優(yōu)化目標(biāo)都同時(shí)考慮這2個(gè)方面(譚政紅[7]認(rèn)為，運(yùn)營(yíng)商成本應(yīng)通過(guò)完善管理制度而不是犧牲旅客服務(wù)質(zhì)量來(lái)控制，所以不考慮)，具體包括：

1) 運(yùn)營(yíng)商方面運(yùn)營(yíng)商的效益包括收益和成本2個(gè)方面.

(1)運(yùn)營(yíng)商收益票價(jià)總額，即客票收入.史峰等[8]使用人公里票價(jià)率乘以旅客總周轉(zhuǎn)量計(jì)算.

(2)運(yùn)營(yíng)商成本

?列車固定成本，即開(kāi)行一列車的固定成本，主要是整備維修，員工工資福利等費(fèi)用，如付慧伶等[9]、王媛媛等[10].

?列車運(yùn)營(yíng)成本，即列車在運(yùn)營(yíng)中的可變成本，包括折舊、能耗、材料購(gòu)置等費(fèi)用.文獻(xiàn)[8]使用列車公里費(fèi)用乘以列車走行距離計(jì)算，文獻(xiàn)[11]將這項(xiàng)成本細(xì)化為列車公里總費(fèi)用、車公里總費(fèi)用、車小時(shí)總費(fèi)用，2008年[11]增加列車組織費(fèi)用.

?中轉(zhuǎn)組織費(fèi)用，文獻(xiàn)[8]將其描述為一個(gè)關(guān)于中轉(zhuǎn)人次數(shù)正相關(guān)的線性公式.

?列車開(kāi)行時(shí)段數(shù)量，列車開(kāi)行時(shí)段數(shù)量過(guò)多將增加運(yùn)營(yíng)成本，鄧連波等[12-13]將最小化時(shí)段數(shù)量作為優(yōu)化目標(biāo).

?區(qū)間斷面客流量均衡度，文獻(xiàn)[6]提出，指各區(qū)間上下行路段的斷面客流量之比(以較小者作為分子)的平均值，反映城軌的正外部性.

?運(yùn)能不足導(dǎo)致的客流流失懲罰成本，由藍(lán)伯雄等[14]提出，用來(lái)體現(xiàn)軌道交通的公共服務(wù)特性，左大杰[15]極小化了剩余客流量.

?列車空位走行距離,此值越大代表列車坐席虛糜度越高，汪波等[16]將坐席虛糜度最小作為目標(biāo).

2) 旅客方面同理，旅客的效益也包括收益和成本2個(gè)方面.

(1)旅客收益文獻(xiàn)[8]指出旅客在旅行中收益是位移，由于對(duì)于不同開(kāi)行方案，旅客的位移并無(wú)差別，所以不將其納入目標(biāo)函數(shù).文獻(xiàn)[13]指出，考慮彈性旅客需求時(shí)，可將乘客人公里最大化作為優(yōu)化目標(biāo).

(2)旅客成本

?票價(jià)支出，一般用客流量、人公里票價(jià)率、行程長(zhǎng)度之積計(jì)算.

?乘車時(shí)間成本，即旅客在車上耗費(fèi)的時(shí)間成本，可分為乘車運(yùn)行時(shí)間成本和停站時(shí)間成本，杜欣等[17]將后者最小化作為目標(biāo)，文獻(xiàn)[10]給出了城軌大小交路下這兩項(xiàng)的詳細(xì)計(jì)算方法，文獻(xiàn)[7]定義了始發(fā)集結(jié)時(shí)間.

?換乘時(shí)間成本，換乘時(shí)間是指旅客換乘過(guò)程的走行時(shí)間和等待時(shí)間之和(如文獻(xiàn)[9-10]).有較多研究將最大化直達(dá)客流量作為優(yōu)化目標(biāo)，本質(zhì)上是減少換乘時(shí)間成本.考慮換乘時(shí)間成本將使客流分配過(guò)程變得較為復(fù)雜，部分文獻(xiàn)忽略了這部分成本，如Ralf Bornd?rfer等[18]；部分研究將換乘時(shí)間成本設(shè)為定值，如王柄達(dá)等[19].

?旅行時(shí)間成本，是乘車時(shí)間成本與換乘時(shí)間成本之和.文獻(xiàn)[11]將其表示為旅行時(shí)間、客流量和旅客平均時(shí)間價(jià)值三者的乘積.宋健等[20]和鄭鋰等[21]指出列車跨站開(kāi)行有利的條件是長(zhǎng)距離出行乘客得到的節(jié)約時(shí)間總和大于部分乘客增加的候車與換乘時(shí)間總和.

?中轉(zhuǎn)風(fēng)險(xiǎn)，文獻(xiàn)[8]提出，反映旅客除中轉(zhuǎn)時(shí)間外所承擔(dān)的風(fēng)險(xiǎn)和精神負(fù)擔(dān)，取決于中轉(zhuǎn)站往終點(diǎn)站的旅客運(yùn)輸能力，表示為換乘時(shí)間乘以一定參數(shù).

?旅行舒適度，可用擁擠費(fèi)用表示，文獻(xiàn)[12]利用列車實(shí)際載客量和定員的比值定義(當(dāng)實(shí)際載客量低于定員時(shí)，擁擠費(fèi)用為0)；類似的，文獻(xiàn)[5]定義了旅客出行舒適度，與列車等級(jí)、速度、換乘時(shí)間、停站時(shí)間相關(guān)；由文獻(xiàn)[8]提出的疲勞恢復(fù)時(shí)間，也用來(lái)反映乘車舒適度，與乘車環(huán)境和乘車時(shí)間相關(guān)；文獻(xiàn)[20]定義的客專舒適度僅考慮列車和席位類型，不考慮載客量，陳勝波等[22-23]認(rèn)為載客量與列車定員間的方差應(yīng)最小化，滿載率應(yīng)在一定范圍內(nèi)；何宇強(qiáng)等[24]提出旅客方便性概念，由列車的發(fā)車時(shí)段決定.

1.2約束條件

開(kāi)行方案約束條件保證了開(kāi)行方案的可行性，數(shù)量較多，引用文獻(xiàn)[16]對(duì)開(kāi)行方案約束條件的分類方法，對(duì)相關(guān)文獻(xiàn)中涉及到的約束條件總結(jié)如下(未列出個(gè)別不常見(jiàn)約束).

1) 車站能力約束

?車站接發(fā)車能力約束[25]，類似的，部分文獻(xiàn)考慮始發(fā)站發(fā)車能力約束、終到站終到能力約束[26]、車站通過(guò)能力約束

單位時(shí)間在車站通過(guò)或停靠的總列車數(shù)≤

車站接發(fā)車能力

(1)

?折返站折返能力約束

單位時(shí)間在車站折返的總列車數(shù)≤

車站折返能力

(2)

?中轉(zhuǎn)換乘組織能力約束，類似的，有文獻(xiàn)提出車站集散能力約束[27]

單位時(shí)間車站內(nèi)中轉(zhuǎn)換乘旅客的總?cè)藬?shù)≤

車站中轉(zhuǎn)換乘組織能力

(3)

2) 區(qū)間能力約束區(qū)間最小追蹤間隔約束[28]，同理也可表示為區(qū)間最大通過(guò)能力約束，即區(qū)間開(kāi)行頻率小于能力允許的最大開(kāi)行頻率

(4)

3) 車底運(yùn)用約束

?車底數(shù)量約束

∑每列車的編組長(zhǎng)度≤可使用的車底總數(shù)

(5)

?各類列車的車輛小時(shí)總數(shù)約束，這是為了考慮運(yùn)輸資源的有限性，同理，也可表示為列車公里數(shù)約束

∑某類列車的車輛小時(shí)≤

該類列車的車輛小時(shí)總數(shù)最大值

(6)

?列車編組長(zhǎng)度約束

最小編組長(zhǎng)度≤列車編組長(zhǎng)度≤最大編組長(zhǎng)度

(7)

?列車檢修約束，城市軌道交通系統(tǒng)一般不考慮這個(gè)約束

列車交路長(zhǎng)度≤有關(guān)規(guī)定中列車的檢修距離

(8)

4) 乘務(wù)規(guī)則約束乘務(wù)組不超勞約束，城市軌道交通系統(tǒng)一般不考慮這個(gè)約束

列車連續(xù)運(yùn)行時(shí)間≤值乘該列車的

各乘務(wù)組最大值乘時(shí)間之和

(9)

5) 客流關(guān)聯(lián)約束此類約束一般為對(duì)客流分配結(jié)果的約束，如OD間各客流路徑上客流量的和(小于)等于該OD客流總量，列車最大車上人數(shù)小于等于列車滿載人數(shù)等，本文不予詳述.

6) 服務(wù)水平約束

?列車輸送能力約束，此約束要求旅客運(yùn)輸需求量必須被全部滿足，但考慮到實(shí)際中輸送能力可能不足的情況，可不將此作為緊約束

∑區(qū)間上各列車定員×最大上座率≥

該區(qū)間斷面客流量

(10)

?區(qū)間最大開(kāi)行間隔約束，這是為了保證一定的服務(wù)質(zhì)量

(11)

?最大、最小上座率約束[29]，上座率的大小影響服務(wù)水平和運(yùn)營(yíng)成本

定員×頻率×最小上座率≤區(qū)間斷面客流量≤

定員×頻率×最大上座率

(12)

?最低停站等級(jí)約束，減少停站可提高列車旅速

列車所停站等級(jí)≥該列車最低停靠站等級(jí)

(13)

?最小停站距離約束

相鄰兩停站間距離≥最小停站距離

(14)

?最大停站數(shù)量約束，高等級(jí)的高速鐵路旅客列車應(yīng)有一定的停站數(shù)量限制，以提高服務(wù)水平

某等級(jí)列車的停站數(shù)量≤

該等級(jí)列車最大停站數(shù)量

(15)

?必須停站要求約束，這是考慮到因技術(shù)作業(yè)或政治經(jīng)濟(jì)等因素要求列車必須在某些站停車的情況

必須停的站點(diǎn)集合?列車停站集合

(16)

?每站必須有列車停靠、每區(qū)間必須有列車經(jīng)過(guò)約束[22,24]

停靠/通過(guò)各站、區(qū)間的列車數(shù)量≥1

(17)

?各時(shí)段內(nèi)站站停列車至少開(kāi)行1列[30]

?存在換乘可能的列車間必須有至少一個(gè)相同的停靠站

(18)

?停站數(shù)量對(duì)旅行速度的影響等式約束

列車速度系數(shù)=

(19)

?交路最大繞行率約束，交路長(zhǎng)度與最短路徑長(zhǎng)度相比不應(yīng)有太大差距，防止過(guò)遠(yuǎn)繞行，也有文獻(xiàn)考慮交路最大長(zhǎng)度約束

(20)

?最大、最小交路個(gè)數(shù)約束，這是考慮到經(jīng)過(guò)各區(qū)段、始發(fā)終到站的不同交路數(shù)量不應(yīng)過(guò)多的事實(shí)，文獻(xiàn)[6]還考慮了全網(wǎng)最大、最小交路數(shù).

最小交路個(gè)數(shù)≤區(qū)間、車站不同交路

數(shù)量≤最大交路個(gè)數(shù)

(21)

?網(wǎng)絡(luò)最大旅客周轉(zhuǎn)量約束、最大席位周轉(zhuǎn)量約束、最小平均上座率約束(前兩者的商)、最大平均旅客剩余率約束、最大平均換乘次數(shù)約束，對(duì)個(gè)別重點(diǎn)OD客流，單獨(dú)考慮的剩余率、上座率約束

?直達(dá)率約束，這是一種最大化直達(dá)客流量的思想

(22)

7) 其他相關(guān)約束主要是各變量、符號(hào)的關(guān)系約束、非負(fù)約束、整數(shù)約束、0-1約束

2求解方法總結(jié)

在求解方法上，國(guó)內(nèi)外形成了較鮮明的對(duì)比，中、大規(guī)模路網(wǎng)優(yōu)化中，國(guó)內(nèi)一般使用啟發(fā)式算法求算滿意解，而國(guó)外則偏向于使用數(shù)學(xué)方法尋求最優(yōu)解，常用的規(guī)劃求解軟件是Cplex；對(duì)于小規(guī)模優(yōu)化，國(guó)內(nèi)文獻(xiàn)一般使用Lingo軟件求解.下面對(duì)現(xiàn)有文獻(xiàn)中求解開(kāi)行方案的啟發(fā)式算法和數(shù)學(xué)方法進(jìn)行總結(jié).

2.1啟發(fā)式算法

啟發(fā)式算法在求算大規(guī)模問(wèn)題時(shí)的優(yōu)勢(shì)是可在合理時(shí)間內(nèi)得到滿意解，所以應(yīng)用較多，常見(jiàn)的開(kāi)行方案啟發(fā)式算法有：

1) 基于人工經(jīng)驗(yàn)的算法文獻(xiàn)[8]提出了基于編制人員“按流開(kāi)車”經(jīng)驗(yàn)的列車開(kāi)行原則，設(shè)計(jì)了相應(yīng)啟發(fā)式算法，特點(diǎn)是只需計(jì)算一次，無(wú)迭代，效率高，可以用來(lái)生成初始方案和鄰域方案.類似的還有文獻(xiàn)[27]等.

2) 模擬退火算法模擬退火計(jì)劃表是其核心，重點(diǎn)是設(shè)計(jì)解的鄰域生成方法和退火規(guī)則.文獻(xiàn)[11]利用模擬退火算法求解雙層規(guī)劃模型，客流分配運(yùn)用了“GP配流算法”，使用類似方法的還有文獻(xiàn)[12-13]，其中文獻(xiàn)[13]采用增廣Lagrange算法進(jìn)行客流分配，利用合并時(shí)段的方法降低開(kāi)行時(shí)段數(shù)；再如周文梁等[31]利用模擬退火算法研究了開(kāi)行方案和運(yùn)行圖的綜合優(yōu)化.

3) 禁忌搜索算法禁忌搜索算法通過(guò)引入禁忌表防止迂回搜索，同時(shí)通過(guò)藐視準(zhǔn)則赦免被禁忌的優(yōu)良解，是一種有效的全局搜索算法.文獻(xiàn)[22]設(shè)計(jì)了禁忌表，采用最大迭代次數(shù)作為終止規(guī)則，并討論了禁忌長(zhǎng)度的合理取值.

4) 遺傳算法遺傳算法通過(guò)模擬生物進(jìn)化過(guò)程擇優(yōu)，是近年來(lái)受到廣泛關(guān)注的全局搜索算法，其關(guān)鍵是編碼方法、雜交和變異算子設(shè)計(jì).文獻(xiàn)[16]設(shè)計(jì)了含停站序列、速度等級(jí)、定員、頻率等的染色體編碼方法，染色體較長(zhǎng).文獻(xiàn)[5]利用遺傳算法求解其多目標(biāo)模型，將開(kāi)行頻率和客流分配方案作為染色體，對(duì)小型路網(wǎng)進(jìn)行了研究.董守清等[32]對(duì)交路和停站編碼，利用群體飄移產(chǎn)生初始種群，采用Baltzmann選擇策略，并使用協(xié)同對(duì)稱群體交叉遺傳算子.文獻(xiàn)[6]將模擬退火算法和遺傳算法混合，將后者作為主引擎，前者作為鄰域解生成和判定的步驟，求解其雙層規(guī)劃模型.陳路鋒等[33]利用遺傳算法搜索備選集，每代對(duì)優(yōu)良抗體進(jìn)行鄰域搜索并更新備選集.

5) 混沌算法混沌優(yōu)化是混沌應(yīng)用研究領(lǐng)域的一個(gè)嶄新方向，適用于局部搜索.何宇強(qiáng)等(2006)[24]利用混沌算法求解其雙層規(guī)劃模型，對(duì)0-1決策變量建立相應(yīng)混沌變量并載波，得到了滿意解.

6) 拉格朗日松弛算法拉格朗日松弛算法將模型中的難約束轉(zhuǎn)化為目標(biāo)函數(shù)，并通過(guò)權(quán)重進(jìn)行調(diào)整與松動(dòng)，可降低優(yōu)化難度.文獻(xiàn)[9]利用拉格朗日松弛算法將模型分為客流分配和開(kāi)行方案確定兩個(gè)子問(wèn)題，每次拉格朗日松弛算法迭代中分別利用線性規(guī)劃方法和其他啟發(fā)算法求解子問(wèn)題.

7) 蟻群算法蟻群算法，又稱螞蟻算法，模擬的是螞蟻尋找食物的過(guò)程.文獻(xiàn)[31]利用蟻群算法對(duì)單線停站方案進(jìn)行優(yōu)化，Saeed Asadi Bagloee[34]將其運(yùn)用于備選交路集的擇優(yōu)過(guò)程.

2.2數(shù)學(xué)解析方法

數(shù)學(xué)解析方法可以求出問(wèn)題的最優(yōu)解，但計(jì)算復(fù)雜，計(jì)算量大，適用于中小規(guī)模開(kāi)行方案優(yōu)化問(wèn)題.文獻(xiàn)中常見(jiàn)的幾類數(shù)學(xué)方法或手段如下：

1) 利用LINGO軟件求解LINGO意為“交互式的線性和通用優(yōu)化求解器”，由美國(guó)LINDO系統(tǒng)公司推出，內(nèi)嵌各類優(yōu)化算法，以下文獻(xiàn)均使用LINGO求解 (文獻(xiàn)[35]利用EXCEL求解).

馬長(zhǎng)青等[36]基于情景集思想優(yōu)化小規(guī)模線路的停站和頻率；文獻(xiàn)[18]對(duì)指定交路下的列車開(kāi)行頻率建模優(yōu)化；文獻(xiàn)[10]建立混合整數(shù)非線性規(guī)劃模型，通過(guò)理想點(diǎn)法將多目標(biāo)轉(zhuǎn)化為單目標(biāo)，并分析了相關(guān)參數(shù)對(duì)最優(yōu)解的影響；文獻(xiàn)[24]利用多目標(biāo)模型對(duì)單線路備選交路集擇優(yōu)；

2) 動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃通過(guò)把原問(wèn)題分解為相對(duì)簡(jiǎn)單的子問(wèn)題的方式求解復(fù)雜問(wèn)題.陳強(qiáng)等[37]利用動(dòng)態(tài)規(guī)劃法優(yōu)化跨線開(kāi)行頻率，文獻(xiàn)[19]求算網(wǎng)絡(luò)中有長(zhǎng)度限制的最長(zhǎng)路徑.

3) 列生成算法列生成算法主要應(yīng)用于求解變量數(shù)遠(yuǎn)大于約束數(shù)的大型模型，子問(wèn)題為主問(wèn)題提供優(yōu)秀的基變量，主問(wèn)題提供引導(dǎo)子問(wèn)題的對(duì)偶信息，此方法也經(jīng)常與啟發(fā)式算法、分支定界法結(jié)合.文獻(xiàn)[15，19]設(shè)計(jì)了結(jié)合啟發(fā)式算法的列生成算法，分別用CPLEX9.1，CPLEX10.1求解，證明列生成算法能有效減少計(jì)算量，提高求解效率.

4) 分支定界法、分支切割法分支定界(Branch-and-Bount)法和分支切割(branch-and-cut)法都是有效的整數(shù)、混合整數(shù)規(guī)劃求解算法，Goossens, J.-W.等[38]應(yīng)用后者求解模型.

5) 模糊數(shù)學(xué)規(guī)劃法模糊數(shù)學(xué)規(guī)劃法可將多目標(biāo)線性規(guī)劃問(wèn)題轉(zhuǎn)化為單目標(biāo)線性規(guī)劃問(wèn)題，Yu-Hern Chang等[39]使用了該方法.

3結(jié) 束 語(yǔ)

開(kāi)行方案編制是運(yùn)輸組織計(jì)劃編制的核心工作之一，國(guó)內(nèi)外學(xué)者對(duì)相關(guān)問(wèn)題做出了較多探索，取得了一定成果，但也存在一些問(wèn)題，如部分研究建立了客流平衡分配模型，而其在軌道交通領(lǐng)域運(yùn)用的科學(xué)性有待論證，再如大多數(shù)文獻(xiàn)算例規(guī)模較小，所提出的方法對(duì)大規(guī)模網(wǎng)絡(luò)的求算效率不明確.今后的研究應(yīng)著重在模型實(shí)用性、算法高效性和客流處理科學(xué)性方面做出更深層次的探索.

參 考 文 獻(xiàn)

[1]王爽，趙鵬.客運(yùn)專線旅客列車開(kāi)行方案研究綜述[J].綜合運(yùn)輸，2008(4)：58-62.

[2]閆海峰，董守清，李群仁，等.客運(yùn)專線列車開(kāi)行方案優(yōu)化思路綜述[J].鐵道運(yùn)輸與經(jīng)濟(jì)，2008，30(5):69-71，75.

[3]左大杰，王慈光，陳韜,等.鐵路旅客列車開(kāi)行方案問(wèn)題的研究綜述[J].鐵道運(yùn)輸與經(jīng)濟(jì)，2010，32(1):35-39.

[4]藍(lán)伯雄，吳李知.高速鐵路客運(yùn)網(wǎng)絡(luò)列車開(kāi)行方案優(yōu)化模型[J].中國(guó)管理科學(xué)，2010，18(6):51-58.

[5]彭其淵，賈曉秋，關(guān)曉宇，等.隨機(jī)穩(wěn)定性配流規(guī)劃的客運(yùn)專線列車開(kāi)行方案模型[J].西南交通大學(xué)學(xué)報(bào)，2011，46(1):143-147.

[6]王永亮，張星臣，徐彬，等.城市軌道交通網(wǎng)絡(luò)化列車開(kāi)行方案優(yōu)化方法[J].中國(guó)鐵道科學(xué)，2012，33(5):120-126.

[7]譚政紅.基于旅客服務(wù)特性的客運(yùn)專線旅客列車開(kāi)行方案研究[D].成都：西南交通大學(xué)，2013.

[8]史峰，鄧連波，黎新華，等.客運(yùn)專線相關(guān)旅客列車開(kāi)行方案研究[J].鐵道學(xué)報(bào)，2004，26(2):16-20.

[9]付慧伶，聶磊，楊浩，等.基于備選集的高速鐵路列車開(kāi)行方案優(yōu)化方法研究[J].鐵道學(xué)報(bào)，2010，32(6):1-8.

[10]王媛媛，倪少權(quán).城市軌道交通大小交路模式列車開(kāi)行方案的優(yōu)化[J].鐵道學(xué)報(bào)，2013，35(7):1-8.

[11]史峰，周文梁，陳彥，等.基于彈性需求的旅客列車開(kāi)行方案優(yōu)化研究[J].鐵道學(xué)報(bào)，2008，30(3):1-6.

[12]鄧連波，曾強(qiáng)，高偉，等.基于彈性需求的城市軌道交通列車開(kāi)行方案研究[J].鐵道學(xué)報(bào)，2012，34(12):16-25.

[13]鄧連波，曾強(qiáng)，高偉，等.城市軌道交通列車開(kāi)行方案優(yōu)化方法[J].中國(guó)科技論文在線，2010，5(10):767-772.

[14]藍(lán)伯雄，吳李知.鐵路客運(yùn)網(wǎng)絡(luò)列車開(kāi)行方案優(yōu)化模型的列生成算法[J].運(yùn)籌與管理，2012，21(1):1-10.

[15]左大杰.鐵路快速客運(yùn)網(wǎng)絡(luò)旅客列車開(kāi)行方案優(yōu)化研究[D].成都：西南交通大學(xué)，2010.

[16]汪波，楊浩，張志華，等.基于周期運(yùn)行圖的京津城際鐵路列車開(kāi)行方案研究[J].鐵道學(xué)報(bào)，2007，29(2):8-13.

[17]杜欣，牛永濤，韓寶明，等.基于節(jié)點(diǎn)重要度的客運(yùn)專線旅客列車開(kāi)行方案[J].北京交通大學(xué)學(xué)報(bào)，2010，34(6):5-10.

[18]RALF B， MARTIN G， MARC E. A column-generation approach to line planning in public transport[J]. Transportation Science,2007,41(1):123-132.

[19]王柄達(dá).客運(yùn)專線旅客列車開(kāi)行方案編制優(yōu)化方法研究[D].成都：西南交通大學(xué)，2010.

[20]宋鍵，徐瑞華，繆和平，等.市域快速軌道交通線開(kāi)行快慢車問(wèn)題的研究[J].城市軌道交通研究，2006，9(12):23-27.

[21]鄭鋰，宋瑞，何世偉，等.城市軌道交通跨站停車方案優(yōu)化模型及算法[J].鐵道學(xué)報(bào)，2009，31(6):1-8.

[22]陳勝波，何世偉，何必勝，等.基于免疫克隆選擇算法的市域快速軌道交通列車開(kāi)行方案優(yōu)化研究[J].石家莊鐵道大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，26(3):81-86.

[23]陳勝波，何世偉，何必勝，等.客流波動(dòng)條件下城市軌道交通列車開(kāi)行方案研究[J].城市軌道交通研究，2013，16(10):53-58.

[24]何宇強(qiáng)，張好智，毛保華，等.客運(yùn)專線旅客列車開(kāi)行方案的多目標(biāo)雙層規(guī)劃模型[J].鐵道學(xué)報(bào)，2006，28(5):6-10.

[25]鄧連波，史峰，周文梁.旅客列車停站設(shè)置方案優(yōu)化[J].中國(guó)鐵道科學(xué)，2009，30(4):102-107.

[26]黃武國(guó).客運(yùn)專線旅客列車開(kāi)行方案研究[D].成都：西南交通大學(xué)，2011.

[27]熊星.基于混合集合規(guī)劃的高速鐵路列車開(kāi)行方案優(yōu)化研究[D].北京：北京交通大學(xué)，2012.

[28]DENG Lianbo， ZENG Qiang， GAO Wei， et al. Optimization method for train plan of urban rail transit[J]. ICCTP 2011: Towards Sustainable Transportation Systems-Proceedings of the 11th International Conference of Chinese Transportation Professionals，2011：1189-1199.

[29]佟璐，聶磊，付慧伶，等.基于運(yùn)輸組織模式導(dǎo)向的旅客列車開(kāi)行方案模型研究[J].大連交通大學(xué)學(xué)報(bào)，2011，32(3):26-31.

[30]房霄虹.城市軌道交通網(wǎng)絡(luò)化運(yùn)輸組織協(xié)調(diào)理論及方法研究[D].北京：北京交通大學(xué)，2010.

[31]周文梁.客運(yùn)專線網(wǎng)絡(luò)列車開(kāi)行方案與運(yùn)行圖綜合優(yōu)化模型及算法[D].長(zhǎng)沙：中南大學(xué)，2010.

[32]董守清，閆海峰，李群仁.基于運(yùn)行網(wǎng)絡(luò)配流的客專列車開(kāi)行方案遺傳優(yōu)化研究[J].中國(guó)鐵道科學(xué)，2012，33(4):105-111.

[33]陳路鋒，宋瑞，何世偉，等.基于雙層規(guī)劃模型的高速鐵路列車開(kāi)行方案優(yōu)化研究[J].鐵道運(yùn)輸與經(jīng)濟(jì)，2013，35(6):18-23.

[34]Saeed A B， Avishai A C. Transit-network design methodology for actual-size road networks[J]. Transportation Research Part B-Methodological,2011,45(10):1787-1804.

[35]楊曉.客運(yùn)專線旅客列車開(kāi)行方案研究[D].北京：北京交通大學(xué)，2008.

[36]馬長(zhǎng)青，徐健.基于情景集的魯棒列車開(kāi)行方案問(wèn)題研究[J].物流技術(shù)，2011，30(9):135-137.

[37]陳強(qiáng)，何世偉，宋瑞,等.動(dòng)態(tài)規(guī)劃方法研究城市軌道交通網(wǎng)狀線路跨線列車開(kāi)行方案[J].城市軌道交通研究，2010，13(3):17-22.

[38]Goossens J W， van Hoesel S， Kroon L. A branch-and-cut approach for solving railway line-planning problems[J]. Transportation Science,2004,38(3):379-393.

[39]CHANGYuhern， YEH Chunghsing， SHEN Chingcheng. A multiobjective model for passenger train services planning: Application to Taiwan’s high-speed rail line[J]. Transportation Research Part B: Methodological,2000,34(2):91-106.

Review on the Optimization Models of

the Train Line Plan in Rail Transport

YU Jian1)ZHANG Xingchen2)XU Lu2)

(EconomicPlanningInstituteofChinaRailway,Beijing100038,China)1)

(SchoolofTrafficandTransportation,BeijingJiaotongUniversity,Beijing100044,China)2)

Abstract：Line planning is a key technical plan and a research hotspot in the organization of rail transport system. This paper presents a systematical summary of the typical optimization models and solving methods of the line planning problem (LPP) of rail transport system and the shortcomings in the current study based on a number of relevant literatures. The summary of the optimization models includes 14 different objectives, classified as 2 categories considering the operators and passengers respectively; and 24 different constrains, classified as 7 categories: station capacity constrain, section capacity constrain, rolling stock operation constrain, crew management constrain, passenger flow constrain, service constrain and other related constrains; whereas the summary of the solving methods includes 13 different common methods, classified as 2 categories: heuristic algorithm and mathematical analysis method. Passenger flow assignment and the scale of the cases in the literatures are considered as shortcomings of the current achievements.

Key words：railway transportation; research review; literature review; line plan; optimization model; solving method

收稿日期：2015-11-27

doi:10.3963/j.issn.2095-3844.2016.01.040

中圖法分類號(hào)：U292.6