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

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

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

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

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

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

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

1 問題描述

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

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

2 問題分析

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

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

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

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

2) 列車停站方案

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

3) 列車編組

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

4) 列車始發(fā)時刻估計值

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

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

5) 服務水平

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

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

6) 動車組小時數(shù)

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

3 模型構建

3.1 約束條件

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

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

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

(1)

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

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

(2)

(3)

(4)

(5)

(4) 各時段和全天的區(qū)間通過能力約束。根據(jù)各列車在各站的出發(fā)或通過時間，可以統(tǒng)計出時段k內(nèi)進入?yún)^(qū)間e的列車數(shù)Te(k)，進而統(tǒng)計出全天進入?yún)^(qū)間e的列車數(shù)為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) 每個車站始發(fā)和終到的列車總數(shù)約束。車站的始發(fā)和終到列車數(shù)不能超過車站始發(fā)終到能力限制，即

(8)

(9)

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

(10)

(11)

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

Tv(k)≥Sv(Δτ)

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

(12)

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

(13)

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

P=0

(14)

3.2 優(yōu)化模型

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

(15)

s.t.

式(1)—式(14)

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

4 模擬退火算法關鍵技術

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

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

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

4.1 停站方案的確定方法

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

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

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

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

4.2 初始開行方案的生成

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

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

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

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

步驟3：調(diào)整列車開行數(shù)量與停站。

在列車網(wǎng)絡上進行客流分配，獲得所有列車的客座率，分別按照如下情形調(diào)整列車開行數(shù)量與停站方案。

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

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

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

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

4.3 鄰域解的搜索策略

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

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

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

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

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

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

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

5 算例分析

5.1 算例數(shù)據(jù)

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

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

5.2 算例結果

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

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

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

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

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

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

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

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

6 結 語

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