高速鐵路列車開行方案優(yōu)化

豐海廣，藺 楊，王晗笑

（1.中國鐵路北京局集團公司石家莊站，河北 石家莊 050000；2.北京交通大學(xué)，北京 100044）

1 緒論

高速鐵路列車開行方案與運行圖是一個復(fù)雜的系統(tǒng)工程，在此之前需要對客流進行調(diào)查分析。以按流開車為原則，開行方案階段根據(jù)給定或預(yù)測的客流確定列車等級和數(shù)量，列車停站方案以及列車運行區(qū)段等。然后需要繪制列車運行圖，根據(jù)生成的列車開行方案確定列車離開和到達其沿途各個車站的具體時間，也就是列車時刻表。最后確定動車組交路計劃和乘務(wù)計劃等。目前許多研究都是將列車開行方案與列車時刻表分開研究的，在優(yōu)化高速鐵路列車開行方案時，不考慮生成的開行方案是否會給時刻表的安排帶來困難，而繪制列車運行圖都是根據(jù)已有的列車開行方案。

在實際應(yīng)用中，生成列車開行方案只是第一步，明確了列車數(shù)量、列車類型、列車編組、列車運行區(qū)段以及列車停站方案等，下一步需要繪制列車運行圖。在這個過程中，如果確定了列車數(shù)量、列車類型及編組，那么列車停站方案對于列車時刻表就有重大影響。

國內(nèi)對于列車開行方案優(yōu)化問題，史峰[1]建立了開行方案的雙層優(yōu)化模型，將旅客列車開行方案與旅客換乘方案結(jié)合起來，并設(shè)計了求解模型的模擬退火算法。周文梁[2]等通過分析與旅客列車開行方案相關(guān)的鐵路旅客運輸需求影響因素，引入了旅客運輸彈性需求函數(shù)，將旅客換乘方案的選擇歸結(jié)為彈性需求下的用戶平衡分配問題，建立了基于彈性需求的旅客列車開行方案的雙層規(guī)劃模型。陳路鋒[3]以高速鐵路列車開行方案決策為目標(biāo)，考慮旅客在換乘站的換乘懲罰，建立高速鐵路列車開行方案的雙層規(guī)劃模型。由于高速鐵路列車呈現(xiàn)發(fā)車頻率高的特點，使旅客出行呈現(xiàn)“城市公交”的特點，為了能夠體現(xiàn)高速鐵路的擁擠情況，構(gòu)建含有失敗概率P的服務(wù)網(wǎng)絡(luò)，即旅客在乘車階段可能由于擁擠無法上車。史峰[5]等引入列車始發(fā)時間，形成高速鐵路列車開行方案的新概念，針對關(guān)鍵OD對提出服務(wù)列車數(shù)下限，針對車站需求稀疏時段，提出發(fā)車時間間隔上限?；诼每统鲂械臅r變需求，建立面向旅客服務(wù)水平的高速鐵路列車開行方案的雙層優(yōu)化模型。付慧伶[6]等建立了基于備選集生成列車開行方案的混合整數(shù)規(guī)劃模型，提出了基于“備選集”的高速鐵路列車開行方案優(yōu)化方法。

國外的研究中，Claessens[7]對面向成本的模型進行了廣泛研究，目標(biāo)是確定在受到服務(wù)限制和能力要求的情況下盡量減少運營費用的線路?；贑laessens 的模型，Goossens[8]提出了一種分支定界方法，忽略了頻率的上限要求。荷蘭鐵路系統(tǒng)的實際經(jīng)驗表明，該方法在合理的時間內(nèi)運行，適用于實際情況。Borndorfer 和Pfetsch[9]提出了一種乘客可以自由選擇路線的模型。他們的目標(biāo)是將運營商的固定成本和可變成本以及乘車時間之和（忽略了換乘時間）減到最小。Bussieck[10]提出的直達旅客方法不需要這種假設(shè)，它們增加了容量限制，以確保所有直達旅客都能被運送，并用整數(shù)規(guī)劃方法求解。

本文主要研究列車停站方案與列車時刻表的協(xié)同優(yōu)化，闡述列車停站方案與列車時刻表協(xié)同優(yōu)化研究的背景和意義，對列車停站方案與列車時刻表的相關(guān)理論進行了論述，在此基礎(chǔ)上，構(gòu)建了列車停站方案與列車時刻表的協(xié)同優(yōu)化模型，模型以列車在中間站停留時間最小化為目標(biāo)，考慮了列車追蹤時間間隔、旅客需求、服務(wù)頻率以及列車旅行時間等約束，設(shè)計簡單算例，運用GAMS 軟件對模型進行了驗證。

2 問題描述

本文用一個二元決策變量來表示列車是否在車站停車。當(dāng)?shù)玫揭唤M可行的決策變量時，就可以確定每列車的停站方案。一般情況下，如果確定了列車停站方案，那么在確定列車時刻表時可能會出現(xiàn)一些潛在的缺陷。一方面，雖然給定的列車停站方案可能是與客流量相關(guān)的較優(yōu)的方案，但在制定列車時刻表方面可能會造成時間上的浪費；另一方面，如果對預(yù)先指定的列車停站方案根據(jù)實際需要進行改變，則需要重新生成列車時刻表來適應(yīng)列車停站方案?；诖?，考慮這兩個問題來實現(xiàn)列車停站方案和列車時刻表的協(xié)同優(yōu)化是困難的。

首先對于不同的列車停站方案，列車在沿途車站的停站次數(shù)會影響列車時刻表的生成，越少的停站次數(shù)對于列車本身意味著越少的停站時間。

在模型中，我們通過設(shè)置列車到達與離開車站的時間和在車站的停留時間之間的關(guān)系制定列車在車站的最短停留時間的約束，把火車停站計劃與列車時刻表問題聯(lián)系在一起，以最小化列車在初始站的實際出發(fā)時間與預(yù)期出發(fā)時間的差值和列車在車站的停留時間為目標(biāo)函數(shù)。

對于列車停站方案，城市軌道交通系統(tǒng)在研究過程中通常假設(shè)所有列車的速度相同，禁止超車操作或者在每個車站有相同的停留時間等。本文考慮的列車停站方案與城市軌道交通中的列車停站方案相似。但是與城市軌道交通相比，高速鐵路的運營要復(fù)雜得多。第一方面：在高速鐵路中，至少有兩種不同速度的列車在鐵路走廊上運行，而且允許高速列車在每個運力足夠的車站超過低速列車，這從本質(zhì)上增加了尋找最優(yōu)策略的難度。第二方面：在給定的停站方案下，每列列車在每個站點的停留時間不是一個常數(shù)。第三方面：列車在始發(fā)站的出發(fā)順序也影響著方案的質(zhì)量。第四方面：在列車停站方案預(yù)先確定后，還需要進一步考慮更多的約束條件，如區(qū)間通過能力、車站接發(fā)車能力等。

在客流方面，一般情況下，高速鐵路的客流變化沒有城市軌道交通變化得明顯。在高速鐵路中，大多數(shù)乘客都是根據(jù)鐵路運營商提出的時間表來制定出行計劃的。相比之下，城市軌道交通的旅客出行有不同的特點，在選擇城市軌道交通作為出行方式時，乘客在制定出行計劃之前通常不考慮城市軌道交通的時刻表，由于需求的隨機性導(dǎo)致了依賴于時間的動態(tài)特性。本文中，我們特別將車站總需求作為決策過程中的參數(shù)，只作為靜態(tài)常數(shù)。

通過以上分析，為便于問題的制定，對模型做出以下假設(shè)。

假設(shè)1：在鐵路走廊上，為了滿足不同旅客的需求，通常將整個鐵路線路劃分為若干區(qū)段。但是這種情況將為描述某一站列車發(fā)車順序增加很大的難度。為了簡化這一問題，本文假設(shè)所有列車都以第一個車站作為始發(fā)站，以最后一個車站作為終點站，這種假設(shè)也可以很方便地根據(jù)實際情況進行擴展。在必要時，任何車站允許超車，但是任何路段禁止超車。

假設(shè)2：在求解過程中，問題的一個關(guān)鍵約束條件與需要滿足的旅客需求有關(guān)，但是提出的方法只是要生成一個戰(zhàn)略水平的時刻表，而不是生成一個操作水平的時刻表，我們不需要詳細確定每個車站旅客上下車的人數(shù)，但是要考慮到每列車的預(yù)計載客人數(shù)與每個車站的旅客需求量，我們要求每個車站停站列車提供的能力要超過該站旅客的總需求。

假設(shè)3：列車在進站和出站前，需要進行減速和加速操作。與直達列車相比，這些操作必然會造成額外的旅行時間損失。但是為簡便起見，本文不考慮車站減速和加速造成的時間損失，也就是說，不管是停站列車還是直達列車，列車在車站之間的行駛時間只與車站之間的距離和列車的速度有關(guān)。

假設(shè)4：為了保證列車在始發(fā)站開行之前進行準(zhǔn)備工作的必要時間，假設(shè)所有列車開行時間不早于預(yù)期開行時間。

3 模型的建立

為了方便建模，表1列出了公式中使用的所有集合、索引和參數(shù)。

表1 模型相關(guān)集合、索引與參數(shù)

本文主要研究如何同時生成列車停站計劃和列車時刻表的最優(yōu)策略，其中需要為每個站點的每列列車指定以下運行特性，包括發(fā)車時間、到站時間、停站計劃和發(fā)車順序等。共有以下五個決策變量：

（1）tisd：列車i從車站s出發(fā)的時間。

（2）tisa：列車i到達車站s的時間。

（3）xis：如果列車i在車站s停車，xis=1；如果列車i在車站s不停車，xis=0。

（4）yijs：在車站s，如果列車i比列車j先發(fā)車，yijs=1；如果列車i比列車j后發(fā)車，yijs=0。

（5）ziG：如果列車i是高速列車，ziG=1；如果列車i是低速列車，ziG=0。

決策變量1和2可以生成一個列車時刻表；決策變量3 是為了確定列車i是否在s站停站，也用來制定列車i在s站的停留時間的約束，這是停站計劃與時刻表之間的關(guān)鍵聯(lián)系；變量4指定每個中間站的列車發(fā)車順序，用來制定每個站的車頭時距約束以保證安全操作；決策變量5 表示列車的類型，決定列車的速度。

本文所涉及的約束表述如下：

（1）接近在始發(fā)站預(yù)期出發(fā)時間的約束。一般來說，由于在鐵路走廊需要安排各種不同類型的列車，需要預(yù)先確定每一列車在始發(fā)站的出發(fā)時間，來保證所考慮的時間范圍內(nèi)的服務(wù)水平，出發(fā)時間安排得好也可以提高列車服務(wù)對乘客的吸引力。然而，如果我們根據(jù)這些最優(yōu)的出發(fā)時間來設(shè)計列車時刻表，可能會出現(xiàn)一些沖突，因為列車的停站方案和速度不一定是一致的。為了消除這些沖突，盡快找到一個最佳的解決方案，我們定義每一列車實際出發(fā)時間與最佳出發(fā)時間的最大允許時間間隔為ΔT。然后，最接近預(yù)期出發(fā)時間約束可表示為：

顯然，這些約束確保了每列列車從始發(fā)站出發(fā)的預(yù)定出發(fā)時間不能早于預(yù)期出發(fā)時間，也不能超過最大波動時間。在實際應(yīng)用中，考慮到實際運行情況，不可能將波動時間設(shè)置為太大的常數(shù)。

（2）列車追蹤時間間隔約束。為了保證鐵路線路的安全運行，需要制定車頭時距約束，保證相鄰列車之間的安全距離，包括到站車頭時距、出站車頭時距和區(qū)段跟蹤車頭時距。雖然影響相鄰列車間最小車頭時距的因素有很多（如制動距離、反應(yīng)時間等），但本文仍然將最小車頭時距作為一個常數(shù)。由于假設(shè)同一列車的速度在每段鐵路上為常數(shù)，因此通過測量相鄰列車到達和離開各車站時的時差，就可以很容易地確定相鄰列車之間的距離。

①發(fā)車時間間隔和到站時間間隔約束?？紤]到每個車站的可供使用的站臺數(shù)目，如果列車到站或者離站，須預(yù)留一段時間，以備下一班列車到站或者離站。換句話說，這個時間段實際上是兩列火車到達或離開操作的時間間隔。為了有效地表達這一約束，我們需要引入變量表示相鄰兩列火車在線路上開行時不同列車在中間站的出發(fā)順序。這里，我們使用變量yijs表示i，j次列車在s站的發(fā)車順序，則車頭時距約束可以表示為：

②區(qū)段追蹤時間間隔：區(qū)段追蹤時間間隔是保證相鄰跟蹤列車在各站間段安全距離的最小時間間隔。它主要取決于相鄰列車的制動能力、速度以及信號聯(lián)鎖設(shè)備的類型。由于我們假設(shè)同類型列車的速度為常數(shù)，且禁止在路段上超車，因此相鄰兩列列車在車站間路段上的最小追蹤時間間隔可以表示為發(fā)車追蹤時間間隔和到站追蹤時間間隔。

圖1給出了4個可行的時刻表，圖中分別表示了不同車頭時距約束之間的關(guān)系，其中h1和h2分別表示對應(yīng)站點出發(fā)和到達作業(yè)的時間差；h3為考慮路段不同位置相鄰兩列列車的跟蹤時差。

通過以上分析，可以將跟蹤車頭時距約束表示為與出發(fā)和到達車頭時距約束相同的形式。如果我們將hd定義為tz和td所需的最大車頭時距，那么到達車頭時距約束、出發(fā)車頭時距約束和跟蹤車頭時距約束可以合并為一組簡化約束，具體如下：

圖1 兩列相鄰列車的到站、離站和跟蹤車頭時距的圖解

（3）在車站的停留時間限制：如列車預(yù)定在某一特定車站?？?，應(yīng)留出一定時間讓列車進行必要的操作，如上下旅客、更換乘員等。其次，停留時間約束是將列車停站方案問題與列車時刻表問題明確聯(lián)系起來的關(guān)鍵。變量xis表示列車i是否在車站s停車，進而表示每個列車的停站方案。很顯然，如果我們知道每列火車在每個車站到達和離開的時間,列車的實際停留時間是可以計算的，且停留時間應(yīng)不少于一個預(yù)先確定的最低時間tτ。

（4）乘客需求約束：為了適當(dāng)表示列車在一個車站的運輸能力，我們特別介紹估計承載能力系數(shù)δis∈ ( 0,1) ，通過綜合考慮潛在的預(yù)留空位和可能的下車乘客，將其與每列車每個車站聯(lián)系起來。然后，δis·Ci將被視為列車i在車站s的估計能力。因此，在一個車站停車的列車所提供的能力必須大于該車站的旅客需求。

雖然上述第二個假設(shè)與實際應(yīng)用略有不同，但我們也可以利用它在策略層面有效地制定乘客需求約束，具體如下：

（5）停站方案限制:在實際操作中，由于每個車站的乘客需求是在整個規(guī)劃范圍內(nèi)考慮的，乘客需求限制可能會導(dǎo)致在一些客流需求小的車站的少量停車。為了增加乘客的服務(wù)靈活性，我們可以增加額外的限制，以確保每個車站至少有一定數(shù)量的列車停靠。該方法雖然一定程度上增加了長途旅客的總出行時間，但可以預(yù)期提高服務(wù)的便捷性和平衡性。約束條件表述如下：

其中Rs符號是給定的閾值，表示在s站所需的最小停站數(shù)。

（6）車站間旅行時間約束：本文不考慮列車加速減速造成的時間損失，同一類型列車在各路段的速度為常數(shù)。列車i從車站s到車站s+1 的旅行時間等于列車i到達車站s+1 的時間減去列車i從車站s出發(fā)的時間。

此外，模型中考慮兩類列車時，將區(qū)分同一路段不同類型列車的運行時間。通過引入列車類型變量，可以對不同列車的站間旅行時間約束如下：

式（15）保證了高速列車集合中包含 |G|列車的總數(shù)。式（14）通過距離除以列車i的速度，表示不同列車的站間旅行時間。

在實際應(yīng)用中，鐵路公司應(yīng)利用最低成本來評估所生成的列車停站計劃和列車時刻表。考慮到這一點，我們可以在滿足乘客需求的情況下，用實際旅行時間表示所考慮的成本。一般情況下，所有列車的總旅行時間可以表示為：

顯然，式（16）本質(zhì)上是每列火車從起點到終點實際行駛時間的總和。同樣，總旅行時間可以進一步分解為以下兩部分，得到更直觀的理解：

式（17）第一部分與中間站點的總停留時間相關(guān)，第二部分為鐵路旅行時間之和。在這個方程中，因為每種類型的列車的運行時間都被認為是一個常數(shù)，所以第二部分實際上是一個常數(shù)。然后，本文將總出行時間最小化等價于總停留時間最小化。因此，將總停留時間作為目標(biāo)函數(shù)，重新表示為：

模型匯總為：

約束條件為：式（1）、式（6）-（15）。

4 案例分析

將上文建立的模型應(yīng)用于我國京滬高鐵走廊列車停站方案和列車時刻表的設(shè)計。這條高速鐵路全長1 318km，由24個車站和23段鐵路組成，優(yōu)化前列車停戰(zhàn)方案如圖2所示。在接下來的實驗中，根據(jù)給定的數(shù)據(jù)進行編程求解。鐵路段長度、預(yù)期出發(fā)時間、乘客需求等參數(shù)進行了事先的收集。

圖2 優(yōu)化前列車停站方案

圖3 優(yōu)化的列車停站方案

（1）距離和旅行時間。京滬高鐵各區(qū)段的距離可以查定。通過距離除以列車速度推導(dǎo)出車站間旅行時間，為便于描述，所生成的旅行時間均設(shè)為整數(shù)。

（2）載客量和旅客需求。據(jù)了解，京滬高鐵走廊上使用的車輛主要是CRH380列車，編組方式有8車和16 車。為實驗簡便，按照發(fā)車順序依次分配8 車和16車編組類型。因為我們只提供協(xié)同優(yōu)化高速鐵路列車時刻表和列車停站方案的理論框架,為簡單起見，承載能力系數(shù)δis=1。車站的旅客需求由OD 客流量計算，OD 客流量等于車站到其他后續(xù)站的總OD客流量。我們只考慮一天的列車時刻表，這段時間鐵路線路上共有41 列列車運行，其中最高速度300km/h 的 G 組列車 38 列，最高速度 250km/h 的 D 組列車3列。

（3）預(yù)計出發(fā)時間等參數(shù)。在本實驗中，實際出發(fā)時間和出發(fā)順序均取實際時刻表中給出的始發(fā)站出發(fā)時間和出發(fā)順序作為期望出發(fā)時間和出發(fā)順序。實際時刻表取自12306上一天的列車時刻表，并繪制每列車的停站模式。為保障操作安全，列車在中間站的最小停留時間、發(fā)車追蹤時間間隔、到站追蹤時間間隔時距、區(qū)間追蹤時間間隔均取2min，最大波動時間取5min。為了提高部分小客源站點的服務(wù)質(zhì)量，每個中間站點至少安排3 列列車停靠，供乘客上下車。

利用上述輸入數(shù)據(jù)，利用GAMS 軟件和CPLEX求解器對案例進行求解。目標(biāo)函數(shù)的最優(yōu)值為594min，即列車在中間站的最短停留時間為594min，優(yōu)化后的列車停戰(zhàn)方案如圖3所示，而在優(yōu)化之前列車的在中間站的總停留時間為838min。838min的總停站時間是根據(jù)鐵路12306 查詢每次列車在各站的到達和發(fā)車時間統(tǒng)計得到的，可以看出算例優(yōu)化了列車在中間站的停站時間。同時，對于優(yōu)化后的列車停站方案，經(jīng)計算發(fā)現(xiàn)各車站停站列車提供的載客能力都滿足旅客需求。

本案例從以下四個方面對京滬高鐵進行了案例分析和結(jié)果評價：

（1）列車在中間站的總停站時間減少，達成優(yōu)化模型考慮的目標(biāo)。

（2）列車在始發(fā)站預(yù)期發(fā)車時間與實際基本一致，考慮到模型中對于列車在始發(fā)站的發(fā)車時間的約束，將發(fā)車時間限制在一定范圍內(nèi)，列車發(fā)車時間不會有太大的變化。

（3）各車站停站列車提供的載客能力可以滿足車站旅客需求。

（4）列車停站方案的變化及其原因分析。

5 結(jié)語

為了協(xié)同考慮列車停站方案與列車時刻表問題，首先將列車停站方案和列車時刻表集成到單線鐵路的基本協(xié)同優(yōu)化模型中。為了建立列車停站方案與列車時刻表之間的聯(lián)系，引入了變量確定列車是否在中間站停車。通過最小化列車在中間站的停留時間，將問題轉(zhuǎn)化為混合整數(shù)線性規(guī)劃模型，利用旅客需求約束保證必要的服務(wù)水平。最后，以京滬高鐵為例，結(jié)合實際運行數(shù)據(jù)進行了實例分析，驗證了模型的可行性與有效性。