軌道交通開行方案優化模型研究綜述

于　劍　張星臣　許　璐

(中國鐵路經濟規劃研究院1)　北京　100038)　(北京交通大學交通運輸學院2) 　北京　100044)

?

軌道交通開行方案優化模型研究綜述

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

(中國鐵路經濟規劃研究院1)北京100038)(北京交通大學交通運輸學院2)北京100044)

摘要：列車開行方案是軌道交通運輸組織中的核心技術計劃，亦是研究熱點之一.文中總結了軌道交通列車開行方案典型優化模型和求解方法，分析了目前研究的不足.優化模型方面，歸納出運營商和旅客2類共14種優化目標，及車站能力約束、區間能力約束、車底運用約束、乘務規則約束、客流關聯約束、服務水平約束、其他相關約束7類共24種約束條件；求解算法方面，歸納出常用的啟發式算法和數學解析方法2類共13種方法，并指出了現有成果在客流分配和算例規模方面的不足.

關鍵詞：鐵路運輸；研究綜述；文獻查閱；開行方案；優化模型；求解方法

于劍(1990- )：男，碩士生，主要研究領域為交通管理工程

0引言

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

開行方案從根本上決定了軌道交通服務產品，問題本身又具有高復雜性，得到了國內外學者的廣泛重視，相關文獻數量較多.以往的研究綜述如王爽等[1]、閆海峰等[2]、左大杰等[3]，強調了分步求算、循環迭代的思想，但大都偏重于定性分析，為深入研究開行方案編制方法，有必要對其定量優化的主要手段——優化模型和求解方法進行系統總結.

1典型開行方案優化模型

大多數定量研究開行方案編制方法的文獻都建立了優化模型.鐵路和城市軌道交通雖然因為各自特性的不同，在模型內容和側重點上有一定區別，如鐵路可能將停站優化作為重點之一，客流分配也需要考慮列車等級甚至時刻表，而城軌可能將開行頻率與客流波動的匹配作為優化重點，客流分配更加注重換乘路徑比選等，但模型形式上是相似的，常見的種類有單目標模型(如藍伯雄等[4])、多目標模型(如彭其淵等[5])、雙層規劃模型(如王永亮等[6])等，其中雙層規劃模型的上層一般用來評價、約束開行方案，下層一般用來進行客流分配，且大量文獻認為客流分配符合用戶平衡.這些模型雖各有側重，但仍有較多相似性，現分為優化目標和約束條件2個部分對相關文獻中的開行方案優化模型進行總結，其中客流分配是較為獨立的步驟，作為一大研究方向有大量文獻，此處不做綜述，且各文獻中重復的優化目標、約束未全做引用標號.

1.1優化目標

開行方案影響著運營商和旅客的效益，所以絕大多數模型的優化目標都同時考慮這2個方面(譚政紅[7]認為，運營商成本應通過完善管理制度而不是犧牲旅客服務質量來控制，所以不考慮)，具體包括：

1) 運營商方面運營商的效益包括收益和成本2個方面.

(1)運營商收益票價總額，即客票收入.史峰等[8]使用人公里票價率乘以旅客總周轉量計算.

(2)運營商成本

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

?列車運營成本，即列車在運營中的可變成本，包括折舊、能耗、材料購置等費用.文獻[8]使用列車公里費用乘以列車走行距離計算，文獻[11]將這項成本細化為列車公里總費用、車公里總費用、車小時總費用，2008年[11]增加列車組織費用.

?中轉組織費用，文獻[8]將其描述為一個關于中轉人次數正相關的線性公式.

?列車開行時段數量，列車開行時段數量過多將增加運營成本，鄧連波等[12-13]將最小化時段數量作為優化目標.

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

?運能不足導致的客流流失懲罰成本，由藍伯雄等[14]提出，用來體現軌道交通的公共服務特性，左大杰[15]極小化了剩余客流量.

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

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

(1)旅客收益文獻[8]指出旅客在旅行中收益是位移，由于對于不同開行方案，旅客的位移并無差別，所以不將其納入目標函數.文獻[13]指出，考慮彈性旅客需求時，可將乘客人公里最大化作為優化目標.

(2)旅客成本

?票價支出，一般用客流量、人公里票價率、行程長度之積計算.

?乘車時間成本，即旅客在車上耗費的時間成本，可分為乘車運行時間成本和停站時間成本，杜欣等[17]將后者最小化作為目標，文獻[10]給出了城軌大小交路下這兩項的詳細計算方法，文獻[7]定義了始發集結時間.

?換乘時間成本，換乘時間是指旅客換乘過程的走行時間和等待時間之和(如文獻[9-10]).有較多研究將最大化直達客流量作為優化目標，本質上是減少換乘時間成本.考慮換乘時間成本將使客流分配過程變得較為復雜，部分文獻忽略了這部分成本，如Ralf Bornd?rfer等[18]；部分研究將換乘時間成本設為定值，如王柄達等[19].

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

?中轉風險，文獻[8]提出，反映旅客除中轉時間外所承擔的風險和精神負擔，取決于中轉站往終點站的旅客運輸能力，表示為換乘時間乘以一定參數.

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

1.2約束條件

開行方案約束條件保證了開行方案的可行性，數量較多，引用文獻[16]對開行方案約束條件的分類方法，對相關文獻中涉及到的約束條件總結如下(未列出個別不常見約束).

1) 車站能力約束

?車站接發車能力約束[25]，類似的，部分文獻考慮始發站發車能力約束、終到站終到能力約束[26]、車站通過能力約束

單位時間在車站通過或停靠的總列車數≤

車站接發車能力

(1)

?折返站折返能力約束

單位時間在車站折返的總列車數≤

車站折返能力

(2)

?中轉換乘組織能力約束，類似的，有文獻提出車站集散能力約束[27]

單位時間車站內中轉換乘旅客的總人數≤

車站中轉換乘組織能力

(3)

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

(4)

3) 車底運用約束

?車底數量約束

∑每列車的編組長度≤可使用的車底總數

(5)

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

∑某類列車的車輛小時≤

該類列車的車輛小時總數最大值

(6)

?列車編組長度約束

最小編組長度≤列車編組長度≤最大編組長度

(7)

?列車檢修約束，城市軌道交通系統一般不考慮這個約束

列車交路長度≤有關規定中列車的檢修距離

(8)

4) 乘務規則約束乘務組不超勞約束，城市軌道交通系統一般不考慮這個約束

列車連續運行時間≤值乘該列車的

各乘務組最大值乘時間之和

(9)

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

6) 服務水平約束

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

∑區間上各列車定員×最大上座率≥

該區間斷面客流量

(10)

?區間最大開行間隔約束，這是為了保證一定的服務質量

(11)

?最大、最小上座率約束[29]，上座率的大小影響服務水平和運營成本

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

定員×頻率×最大上座率

(12)

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

列車所停站等級≥該列車最低停靠站等級

(13)

?最小停站距離約束

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

(14)

?最大停站數量約束，高等級的高速鐵路旅客列車應有一定的停站數量限制，以提高服務水平

某等級列車的停站數量≤

該等級列車最大停站數量

(15)

?必須停站要求約束，這是考慮到因技術作業或政治經濟等因素要求列車必須在某些站停車的情況

必須停的站點集合?列車停站集合

(16)

?每站必須有列車停靠、每區間必須有列車經過約束[22,24]

停靠/通過各站、區間的列車數量≥1

(17)

?各時段內站站停列車至少開行1列[30]

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

(18)

?停站數量對旅行速度的影響等式約束

列車速度系數=

(19)

?交路最大繞行率約束，交路長度與最短路徑長度相比不應有太大差距，防止過遠繞行，也有文獻考慮交路最大長度約束

(20)

?最大、最小交路個數約束，這是考慮到經過各區段、始發終到站的不同交路數量不應過多的事實，文獻[6]還考慮了全網最大、最小交路數.

最小交路個數≤區間、車站不同交路

數量≤最大交路個數

(21)

?網絡最大旅客周轉量約束、最大席位周轉量約束、最小平均上座率約束(前兩者的商)、最大平均旅客剩余率約束、最大平均換乘次數約束，對個別重點OD客流，單獨考慮的剩余率、上座率約束

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

(22)

7) 其他相關約束主要是各變量、符號的關系約束、非負約束、整數約束、0-1約束

2求解方法總結

在求解方法上，國內外形成了較鮮明的對比，中、大規模路網優化中，國內一般使用啟發式算法求算滿意解，而國外則偏向于使用數學方法尋求最優解，常用的規劃求解軟件是Cplex；對于小規模優化，國內文獻一般使用Lingo軟件求解.下面對現有文獻中求解開行方案的啟發式算法和數學方法進行總結.

2.1啟發式算法

啟發式算法在求算大規模問題時的優勢是可在合理時間內得到滿意解，所以應用較多，常見的開行方案啟發式算法有：

1) 基于人工經驗的算法文獻[8]提出了基于編制人員“按流開車”經驗的列車開行原則，設計了相應啟發式算法，特點是只需計算一次，無迭代，效率高，可以用來生成初始方案和鄰域方案.類似的還有文獻[27]等.

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

3) 禁忌搜索算法禁忌搜索算法通過引入禁忌表防止迂回搜索，同時通過藐視準則赦免被禁忌的優良解，是一種有效的全局搜索算法.文獻[22]設計了禁忌表，采用最大迭代次數作為終止規則，并討論了禁忌長度的合理取值.

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

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

6) 拉格朗日松弛算法拉格朗日松弛算法將模型中的難約束轉化為目標函數，并通過權重進行調整與松動，可降低優化難度.文獻[9]利用拉格朗日松弛算法將模型分為客流分配和開行方案確定兩個子問題，每次拉格朗日松弛算法迭代中分別利用線性規劃方法和其他啟發算法求解子問題.

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

2.2數學解析方法

數學解析方法可以求出問題的最優解，但計算復雜，計算量大，適用于中小規模開行方案優化問題.文獻中常見的幾類數學方法或手段如下：

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

馬長青等[36]基于情景集思想優化小規模線路的停站和頻率；文獻[18]對指定交路下的列車開行頻率建模優化；文獻[10]建立混合整數非線性規劃模型，通過理想點法將多目標轉化為單目標，并分析了相關參數對最優解的影響；文獻[24]利用多目標模型對單線路備選交路集擇優；

2) 動態規劃法動態規劃通過把原問題分解為相對簡單的子問題的方式求解復雜問題.陳強等[37]利用動態規劃法優化跨線開行頻率，文獻[19]求算網絡中有長度限制的最長路徑.

3) 列生成算法列生成算法主要應用于求解變量數遠大于約束數的大型模型，子問題為主問題提供優秀的基變量，主問題提供引導子問題的對偶信息，此方法也經常與啟發式算法、分支定界法結合.文獻[15，19]設計了結合啟發式算法的列生成算法，分別用CPLEX9.1，CPLEX10.1求解，證明列生成算法能有效減少計算量，提高求解效率.

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

5) 模糊數學規劃法模糊數學規劃法可將多目標線性規劃問題轉化為單目標線性規劃問題，Yu-Hern Chang等[39]使用了該方法.

3結 束 語

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

參 考 文 獻

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

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

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

[4]藍伯雄，吳李知.高速鐵路客運網絡列車開行方案優化模型[J].中國管理科學，2010，18(6):51-58.

[5]彭其淵，賈曉秋，關曉宇，等.隨機穩定性配流規劃的客運專線列車開行方案模型[J].西南交通大學學報，2011，46(1):143-147.

[6]王永亮，張星臣，徐彬，等.城市軌道交通網絡化列車開行方案優化方法[J].中國鐵道科學，2012，33(5):120-126.

[7]譚政紅.基于旅客服務特性的客運專線旅客列車開行方案研究[D].成都：西南交通大學，2013.

[8]史峰，鄧連波，黎新華，等.客運專線相關旅客列車開行方案研究[J].鐵道學報，2004，26(2):16-20.

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

[10]王媛媛，倪少權.城市軌道交通大小交路模式列車開行方案的優化[J].鐵道學報，2013，35(7):1-8.

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

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

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

[14]藍伯雄，吳李知.鐵路客運網絡列車開行方案優化模型的列生成算法[J].運籌與管理，2012，21(1):1-10.

[15]左大杰.鐵路快速客運網絡旅客列車開行方案優化研究[D].成都：西南交通大學，2010.

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

[17]杜欣，牛永濤，韓寶明，等.基于節點重要度的客運專線旅客列車開行方案[J].北京交通大學學報，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].成都：西南交通大學，2010.

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

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

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

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

[24]何宇強，張好智，毛保華，等.客運專線旅客列車開行方案的多目標雙層規劃模型[J].鐵道學報，2006，28(5):6-10.

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

[26]黃武國.客運專線旅客列車開行方案研究[D].成都：西南交通大學，2011.

[27]熊星.基于混合集合規劃的高速鐵路列車開行方案優化研究[D].北京：北京交通大學，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]佟璐，聶磊，付慧伶，等.基于運輸組織模式導向的旅客列車開行方案模型研究[J].大連交通大學學報，2011，32(3):26-31.

[30]房霄虹.城市軌道交通網絡化運輸組織協調理論及方法研究[D].北京：北京交通大學，2010.

[31]周文梁.客運專線網絡列車開行方案與運行圖綜合優化模型及算法[D].長沙：中南大學，2010.

[32]董守清，閆海峰，李群仁.基于運行網絡配流的客專列車開行方案遺傳優化研究[J].中國鐵道科學，2012，33(4):105-111.

[33]陳路鋒，宋瑞，何世偉，等.基于雙層規劃模型的高速鐵路列車開行方案優化研究[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]楊曉.客運專線旅客列車開行方案研究[D].北京：北京交通大學，2008.

[36]馬長青，徐健.基于情景集的魯棒列車開行方案問題研究[J].物流技術，2011，30(9):135-137.

[37]陳強，何世偉，宋瑞,等.動態規劃方法研究城市軌道交通網狀線路跨線列車開行方案[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

中圖法分類號：U292.6