面向服務水平的高速鐵路列車開行方案優化

史 峰，李彥霖，胡心磊，徐光明，單杏花

(1.中南大學 交通運輸工程學院，湖南 長沙 410075；2.中國鐵道科學研究院 電子計算技術研究所，北京 100081)

在列車運輸組織中，列車開行方案將客流轉化成列車流，為編制列車運行圖提供依據。由于高速鐵路列車高密度開行，使旅客出行的時變出行需求得以滿足，為了保證發車時間分布與時變需求相吻合，有必要在傳統列車開行方案內涵的基礎上進行擴展，引入列車始發時間，形成高速鐵路列車開行方案的新概念。高速鐵路列車開行方案的服務水平同樣是一個重要的關注內容，包括關鍵O-D對之間的服務列車數下限、每個車站在需求稀疏時段的發車時間間隔上限等。隨著高速鐵路網絡的快速發展，面向服務水平的高速鐵路列車開行方案優化問題成為提高運輸組織品質的重要研究問題。

很多學者對列車開行方案優化問題、列車停站方案優化子問題和列車上的客流分配子問題等展開了深入研究。其中，對于列車開行方案優化問題，史峰等[1]建立了開行方案的雙層規劃優化模型，上層規劃是鐵路企業對開行方案的優化，下層規劃是旅客對列車開行方案的反應，即換乘網絡上的客流分配，客流分配的結果作為鐵路企業評價開行方案的重要依據，并設計了求解模型的模擬退火算法。Kaspi等[2]在不考慮列車能力約束的情況下，對列車開行方案和時刻表進行綜合優化。FU等[3]建立了開行方案的混合整數規劃模型，并根據模型結構特點設計拉格朗日松弛算法。蘇煥銀等[4]建立了開行方案的雙層規劃優化模型，下層規劃將客流分配到列車上，設計了求解模型的模擬退火算法。FU等[3]和蘇煥銀等[4]都基于包括停站方案的列車運行區段備選集生成列車開行方案。徐光明[5]首先將客流分配到路網上，然后在每一個區段上開行若干列車單元，進而將相鄰列車單元拼接成列車，形成列車開行方案；還設計了模擬退火算法優化拼接方案。在上述研究中，Kaspi等[2]、蘇煥銀等[4]和徐光明[5]均是針對時變需求優化列車開行方案的。

對于列車停站方案優化子問題，鄧連波等[6]建立了列車停站方案的雙層規劃模型，上層規劃優化了列車停站方案，下層規劃針對給定的停站方案進行多類用戶均衡的客流分配，并設計了模擬退火優化算法。李得偉等[7]以方案總停站次數最少為目標，考慮節點的列車服務頻率、站間的列車可達性、單趟列車停站次數等約束，構建非線性規劃模型，將其轉化為連續優化模型，運用Matlab工具包求解。YUE等[8]考慮O-D對的服務列車數下限約束，基于給定列車開行方案優化停站方案和列車時刻表，使用拉格朗日松弛方法將數學模型轉化為線性約束問題來求解。YANG等[9]粗略地考慮各車站發送能力分布與旅客發送量的吻合程度，并考慮車站服務列車數的下限約束，基于給定列車開行方案優化列車時刻表和停站方案，建立了混合整數線性規劃模型，采用GAMS工具軟件求解。史峰等[10]分析了位于省(直轄市)、地、縣各級政府所在城市的高速鐵路車站的出行需求集聚效應，建立了高速鐵路線路上各級車站的列車經停比優化模型，發現高速鐵路列車在省級站經停比幾乎為1，不同線路上各級車站的最優經停比存在差異，這種差異與線路上各級車站的數量比率相關。

對于列車上的客流分配子問題，史峰等[1]針對日需求設計了客流分配的換乘網絡，使旅客出行方案與網絡路徑一一對應，出行費用與路徑長度相等，利用換乘網絡上的客流分配求解旅客的出行方案，大幅提升了旅客出行方案求解的效率。Kaspi等[2]在客流分配時設計了1個規模很小的旅客換乘網絡，2趟列車在1個車站的換乘過程只需要1條換乘弧和若干等待弧。Douglas等[11]在只考慮旅客直達情況下，對于城市軌道交通中的任意點對，設計了時變需求旅客選擇列車的屋頂算法，將全天劃分為多個區間，每1個區間內計劃到達的旅客具有相同的最優乘車方案。Su等[12]采用了與Kaspi等[2]相同的換乘網絡，注意到旅客在購票的瞬間占用列車能力，模擬旅客的購票過程設計列車上的客流分配過程，將屋頂模型擴展為多階段屋頂模型，并擴展到旅客出行全過程。

本文在上述研究成果基礎上，面向服務水平研究高速鐵路列車開行方案優化問題。以高速鐵路線路為研究對象，考慮旅客出行的時變需求、高速鐵路線路條件、動車組小時數和服務水平，借助于列車在省級站經停比幾乎為1的特征，將相關O-D對的服務列車數轉化為各級車站服務列車數，建立高速鐵路列車開行方案優化模型，并設計模擬退火優化算法。

1 問題描述

記高速鐵路列車開行方案為Ω={T=(LT，VT，BT，DT)}， 其中LT，VT，BT，DT分別為列車T的運行區段、停站方案、編組和始發時刻估計值。1個合理的高速鐵路列車開行方案，必須具有較小的旅客出行費用和鐵路運輸成本，還需為旅客提供一定水平的服務。因此，高速鐵路列車開行方案優化問題可描述如下：

給定各O-D對的時變客流需求、高速鐵路線路條件、動車組小時數，在一定服務水平和各項能力約束下，優化高速鐵路列車開行方案Ω，使得旅客出行費用和鐵路運輸成本均最小化。

2 問題分析

1) 列車運行區段及備選集

列車運行區段LT包括列車始發站、終點站和列車徑路，由于高速鐵路上的列車徑路是唯一確定的，所以列車運行區段只包括列車的始發站和終點站。

列車運行區段備選集L是由若干個備選運行區段構成的集合。備選運行區段是指任意2個具有始發終到能力的車站之間的區段，其中具有始發終到能力的車站通常是指具有動車所(段)或動車組存車線的車站。在優化列車開行方案時，全部列車運行區段都限制于備選集L中，即LT∈L，T∈Ω，從而縮小了優化搜索空間。

列車運行區段備選集的構建：設定客流量下限值，對于具有始發終到能力的2個車站，若這2個車站之間的客流需求達到設定的客流量下限值，則將其加入備選集；在一個省屬地域范圍內，線路上具有始發終到能力的2個端頭站，無論客流需求大小，均將其加入備選集，多用于“早晚三角區”開行短途列車。

2) 列車停站方案

給定所有列車運行區段{LT|T∈Ω}，依據各O-D對的服務列車數和各站的服務列車數，確定列車停站方案{VT|T∈Ω}。通常規定所有列車在省級站全停，由此便可確定列車在地級站和縣級站停站數的下限。同為地級站或縣級站，到發客流量大小的差異，停車數的下限也存在差異。

3) 列車編組

列車編組BT分為16輛和8輛編組2種，通常根據線路通過能力和服務水平等確定采用哪種編組。

4) 列車始發時刻估計值

為了滿足旅客時變需求，若掌握了列車在各站的發車時刻信息，則可能評價列車發車時刻與旅客時變需求的吻合程度。參照列車運行方案圖的理念，在不考慮列車運行線沖突的情況下，在傳統列車開行方案中引入列車始發時刻估計值，便可推導出列車在各站的發車時刻信息，實現列車發車時刻與旅客時變需求吻合程度的評價。

對于任意始發站，在時長為Δt的時段內，按照發車時刻呈均勻分布的原則排列列車始發時刻，便可估計出所有列車的始發時刻{DT|T∈Ω}。

5) 服務水平

高速鐵路列車開行方案的服務水平包括以下2個方面，一方面是對關鍵O-D對的服務水平，另一方面是對車站的服務水平。

列車開行方案對于車站的服務水平，是指對于給定車站v、時段k=1，2，…，(t2-t1)/Δτ的停站列車數Tv(k)需要達到的下限規定標準Sv(Δτ)，以此保證稀疏需求時段內(比如早晚時段)車站的服務列車數。

6) 動車組小時數

列車開行方案需要以一定數量的動車組為保障，注意到開行方案優化期間并沒有確定列車運行時刻表，進而沒有確定動車組周轉方案，也就沒有確定所需要的動車組數量。我們轉而以可支配動車組小時數作為列車開行方案實際使用的動車組小時數的上限約束，這是一種退而求其次的處理辦法。

3 模型構建

3.1 約束條件

綜上所述，列車開行方案Ω必須滿足相關的約束條件，具體描述如下。

(1) 列車運行區段備選集約束。構造列車運行區段備選集L={lk|k=1，2，…，m}，列車T∈Ω的運行區段LT僅限于列車運行區段備選集L中產生，即

LT∈L={lk|k=1，2，…，m}T∈Ω

(1)

(2) 列車T∈Ω的編組BT約束。列車T的編組分為8輛編組和16輛編組，即

BT∈{8輛編組，16輛編組}T∈Ω

(2)

(3)

(4)

(5)

(4) 各時段和全天的區間通過能力約束。根據各列車在各站的出發或通過時間，可以統計出時段k內進入區間e的列車數Te(k)，進而統計出全天進入區間e的列車數為Te(D)。Te(k)和Te(D)分別受相應的通過能力限制，即

Te(k)≤Ce(Δt)

e∈E，k=1，2，…，(t2-t1)/Δt

(6)

Te(D)≤Ce(D)e∈E

(7)

(5) 每個車站始發和終到的列車總數約束。車站的始發和終到列車數不能超過車站始發終到能力限制，即

(8)

(9)

(6) 可支配動車組小時數作為上限約束。記列車T∈Ω的旅行時間為tT，列車開行方案使用的動車組小時數不超過可支配動車組小時數D，即

(10)

(11)

(8) 各車站各時段內停站列車數約束。記時段k在車站v∈V停站的列車數為Tv(k)，Tv(k)不得低于規定的下限列車數Sv(Δτ)，即

Tv(k)≥Sv(Δτ)

k=1，2，…，(t2-t1)/Δτ，v∈V

(12)

(9) 動車組周轉約束。在任意車站，始發列車編組總數等于終到列車編組總數，使得動車組得以周轉運行，即

(13)

(10) 剩余客流總人數為0。這是列車開行方案完成全部出行旅客運輸任務的保障，要求開行列車數、停站數及其分布提供足夠的運輸能力，并通過客流分配進行驗證。記客流分配的剩余客流總人數為P，此約束可表示為

P=0

(14)

3.2 優化模型

minZ=λ(wrτr+whτh+wcτc)+

(15)

s.t.

式(1)—式(14)

該雙層規劃模型描述了一個主從博弈，博弈的主體方為鐵路運輸企業，根據旅客的反應優化列車開行方案(上層規劃)；從屬方為旅客，針對鐵路運輸企業制定的列車開行方案，以旅客的集體選擇行為作為反應，即產生旅客出行時間τr，τh，τc和剩余客流總量P等，作為鐵路企業決策的依據(下層規劃)。求解下層規劃的客流分配方法見文獻[12]。

4 模擬退火算法關鍵技術

列車開行方案優化是NP難問題[13]，通常采用智能算法求解。比如史峰等[14]基于模擬退火算法優化求解普通列車開行方案。WANG等[15]采用遺傳算法優化列車停站方案。考慮到模擬退火算法具有較強的魯棒性和適用性，下面設計模擬退火算法求解模型。

在模擬退火算法框架中，需要根據問題特點設計初始解的生成方法和鄰域解的搜索方法，并要求初始解和新的鄰域解滿足全部約束條件。在所有約束條件中：式(1)—式(5)比較獨立，是容易滿足的；對于能力約束式(6)—式(10)，若增加太多列車必然導致該約束條件遭到破壞，這時可以通過提高列車客座率和增加16輛編組列車數的方法，力圖在滿足能力約束式(6)—式(10)的情況下滿足服務水平約束式(11)、式(12)和剩余客流量約束式(14)；在構造初始方案時，通過盡可能地多開列車、多設停站，使服務水平約束式(11)、式(12)和剩余客流量約束式(14)得以滿足；在鄰域搜索時，一旦服務水平約束式(11)、式(12)或剩余客流量約束式(14)遭到破壞，立即以增加列車或增加停站的方式恢復這些約束條件的可行性；對于動車組周轉約束式(13)，可通過限制雙向列車成對運行使其得以滿足。

在下面的算法設計中，將忽略模擬退火算法的一般性框架敘述，重點介紹模擬退火算法設計的關鍵技術，包括列車停站方案的確定方法、初始解的生成方法和鄰域解的搜索方法。

4.1 停站方案的確定方法

列車停站方案受到服務水平約束式(11)和式(12)，以及剩余客流量約束式(14)的制約，下面依據式(11)、式(12)和式(14)的滿足情況討論列車停站方案的確定方法。

在任意車站，將停站列車和通過列車統稱為經過列車，并將停站列車數與經過列車數的比值稱為經停比。文獻[10]研究表明，高速鐵路列車在省級車站的合理經停比接近于1。對于2個省級車站r和s，若Trs

若O-D對(r，s)∈W之間存在剩余客流，即不滿足式(14)，則可以增加列車在車站r和s或(r，s)之間途中車站的停站次數，甚至增開服務于點對(r，s)的列車，直至滿足式(14)為止。

若列車開行稀疏的時空區域不滿足式(12)，則適當增加停站密度。若仍然不滿足式(12)，則適當增加列車，直至滿足式(12)為止。之所以要先增加停站密度，再增加列車密度，是因為在客流較稀疏的時空區域，多停站少開車是合理的開行法則。

4.2 初始開行方案的生成

根據模擬退火算法框架和停站方案的確定方法，按照如下步驟生成初始列車開行方案。

步驟1：確定無能力約束的列車開行方案。

對于備選集L中全部運行區段，在可行時段k=1，2，…，(t2-t1)/Δt內開行1趟列車；將各個時段k內開行的列車均勻排列始發時間，確定列車的停站方案，推導列車在沿途各站的到達和出發時刻，全部列車無能力約束。

步驟2：按照列車定員分解列車。

步驟3：調整列車開行數量與停站。

在列車網絡上進行客流分配，獲得所有列車的客座率，分別按照如下情形調整列車開行數量與停站方案。

若不滿足服務水平約束式(12)，則增加相應時空區域的列車停站和開行列車數，直至滿足式(12)為止；

若不滿足能力約束式(6)—式(10)，則在保持式(12)的基礎上，按照客座率從低到高的順序刪除列車，直至滿足式(6)—式(10)為止；

若不滿足服務水平約束式(11)或剩余客流量約束式(14)，則在保持能力約束式(6)—式(10)的基礎上，增加列車或停站，直至滿足式(11)和式(14)為止。

為了保證式(13)得到滿足，上述增加或刪除列車的操作都得成對進行。

4.3 鄰域解的搜索策略

在模擬退火算法中，需要在滿足開行方案所有約束條件下，采用下列搜索策略依次搜索鄰域解。

策略1：刪除列車。以給定概率刪除客座率小于下限標準的8輛編組列車，同時在反方向區段刪除1列客座率最低的8輛編組列車。

策略2：增加列車。在始發能力允許的車站和時段內，選擇現行列車客座率最高的列車運行區段增開1趟8輛編組列車，同時在反方向區段按照相同原則增開1趟8輛編組列車。

策略3：改變列車編組。若2個方向都存在8輛編組列車的客座率高于上限標準，則以給定概率將這2列相向列車都調整為16輛編組；若2個方向都存在16輛編組列車的客座率低于下限標準，則以給定概率將這2列相向列車都調整為8輛編組。

策略4：拼接列車。若1個方向上存在接續車站相同、接續時間相近的2趟相同編組列車，并且反方向存在2趟相同運行區段和編組的列車，分別將2個方向的列車拼接起來，形成更長距離的列車。

策略5：刪除列車后增加停站。若不滿足服務水平約束式(11)、式(12)和剩余客流約束式(14)，則相應地增加停站，直至滿足式(11)、式(12)和式(14)，并在停站稀疏的時空區域適當增加停站。

策略6：增加列車后調整停站。對于新增加的列車，相應地確定停站，與其它列車經停比相適應。在保持滿足式(11)、式(12)和式(14)的情況下，選擇停站密集的時空區域刪除停站，使得旅客出行時間下降。

5 算例分析

5.1 算例數據

以杭福深高速鐵路線為例，該線路共有53個車站，其中省級站5個，地級站10個，縣級站38個，線路上車站等級和區間里程如圖1所示。

圖1 杭福深高速鐵路線圖(單位：km)

5.2 算例結果

運用本文提出的模型和算法，求解得到杭福深高速鐵路線雙向列車運行方案圖，如圖2所示。圖中縱坐標只顯示了具有始發終到能力的車站站名，實心菱形點表示列車的始發終到車站和時間，空心圓點表示列車的中途停靠車站和時間。優化后的列車開行方案評價指標見表1。從表1可知，旅客的平均出行時間偏差較小(20 min)，列車平均客座率較高(72%)。

圖2 杭州—福州—深圳間列車運行方案

折射動車組小時旅客出行費用/元列車總數/對出發時間偏差/min平均客座率/%1 1306.12×1071002072

每個車站的經過列車數、停站列車數和經停比分別按上、下行表示在圖3中，圖中橫坐標為在線路上順序排列的車站，并以數字1,2,3分別表示車站的省地縣級的等級，圖中左側縱坐標為列車數，用于表示車站的經過列車數和停站列車數，右側縱坐標為比例值，用于表示車站的經停比。

結合圖1和圖3可知：杭福深高速鐵路中段的經過列車較多，但廈門至饒平的列車較少，這是因為廈門至饒平這段線路位于福建省與廣東省的交界區域，客流較少；不同等級車站的經停比具有顯著層次性：省級站的經停比為1，地級站的經停比分布于0.7～0.9之間，縣級站的經停比分布于0.2～0.5之間，地級站的經停比顯著高于縣級站的經停比，是因為杭福深高速鐵路上的縣級站很多，地級站對同地區縣級站具有出行集聚效應。

圖3 杭州—福州—深圳間各車站列車服務情況

采用C#語言編程，該算例的運行時間為20 min，收斂曲線如圖4所示，可見，運算收斂速度較快，收斂趨勢較為穩定，表明本文提出的優化方法具有較高的運行效率。

圖4 算法迭代收斂趨勢示意圖

6 結 語

本文對傳統列車開行方案增加了列車始發時間估計值，綜合考慮旅客出行時變O-D需求、高速鐵路線路運輸能力、列車定員、可支配動車組小時數等因素，面對關鍵O-D對的服務列車數和稀疏時空區域的服務列車間隔等服務水平，構建了優化高速鐵路列車開行方案的雙層規劃模型，上層規劃優化列車開行方案，下層規劃根據給定的開行方案進行時變需求客流分配。設計了列車停站方案確定方法、初始開行方案生成方法和鄰域解的搜索方法，進而設計了求解模型的模擬退火算法。算例分析表明，采用該模型和算法求解的列車開行方案在時空區域上較好地吻合了旅客出行的時變需求，其服務水平達到規定下限，該模型和算法具有良好的優化效率和實用性。