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

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

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

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

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

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

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

1 問題描述

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

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

2 問題分析

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

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

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

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

2) 列車停站方案

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

3) 列車編組

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

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

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

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

5) 服務(wù)水平

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

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

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

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

3 模型構(gòu)建

3.1 約束條件

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

(1) 列車運(yùn)行區(qū)段備選集約束。構(gòu)造列車運(yùn)行區(qū)段備選集L={lk|k=1，2，…，m}，列車T∈Ω的運(yùn)行區(qū)段LT僅限于列車運(yùn)行區(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)進(jìn)入?yún)^(qū)間e的列車數(shù)Te(k)，進(jìn)而統(tǒng)計出全天進(jìn)入?yún)^(qū)間e的列車數(shù)為Te(D)。Te(k)和Te(D)分別受相應(yīng)的通過能力限制，即

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) 動車組周轉(zhuǎn)約束。在任意車站，始發(fā)列車編組總數(shù)等于終到列車編組總數(shù)，使得動車組得以周轉(zhuǎn)運(yùn)行，即

(13)

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

P=0

(14)

3.2 優(yōu)化模型

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

(15)

s.t.

式(1)—式(14)

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

4 模擬退火算法關(guān)鍵技術(shù)

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

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

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

4.1 停站方案的確定方法

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

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

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

若列車開行稀疏的時空區(qū)域不滿足式(12)，則適當(dāng)增加停站密度。若仍然不滿足式(12)，則適當(dāng)增加列車，直至滿足式(12)為止。之所以要先增加停站密度，再增加列車密度，是因?yàn)樵诳土鬏^稀疏的時空區(qū)域，多停站少開車是合理的開行法則。

4.2 初始開行方案的生成

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

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

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

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

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

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

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

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

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

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

4.3 鄰域解的搜索策略

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

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

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

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

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

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

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

5 算例分析

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

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

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

5.2 算例結(jié)果

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

圖2 杭州—福州—深圳間列車運(yùn)行方案

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

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

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

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

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

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

6 結(jié) 語

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