面向提升旅客出行效率的高速鐵路列車停站方案優(yōu)化

許若曦，聶 磊，付慧伶*

(1.北京宇恒未來規(guī)劃設(shè)計有限公司，北京100022；2.北京交通大學交通運輸學院，北京100044)

0 引言

我國高速鐵路運營里程長，很多長距離列車的平均停站次數(shù)較多，增加了旅客(特別是長途旅客)的旅行時間；同時中小站的列車服務(wù)頻率偏低，換乘旅客的等待時間也較長.這些問題可以通過優(yōu)化列車停站方案解決，即減少部分列車的中小站停站次數(shù)，提高快車比例；并適當增加中小站的列車停站頻率，確保中小站旅客獲得足夠的站間通達性和換乘便捷性.由于互為矛盾，如何平衡好這兩者間的關(guān)系，是列車停站方案優(yōu)化面臨的一個問題.

對于列車停站優(yōu)化問題，國內(nèi)外有豐富的研究成果.Yu-Hern Chang[1]，Dung-Ying Lin[2]，Y.Ulusoy[3]針對臺灣和北美鐵路列車停站進行優(yōu)化，以鐵路和旅客出行的成本最低為目標；蒲松[4]基于客流需求波動建立列車開行方案魯棒優(yōu)化模型，可決策列車OD、開行對數(shù)和停站方案；牛豐[5]構(gòu)建不確定客流條件下的高速列車停站方案機會約束規(guī)劃模型，最小化區(qū)段內(nèi)開行列車的總停站次數(shù)；J.Qi[6]同時優(yōu)化列車開行區(qū)段、停站和客流分配，最小化列車空載席位和總停站次數(shù)；史峰[7]基于旅客時變需求優(yōu)化高速列車開行方案，并設(shè)計停站方案確定方法；畢明凱[8]基于隨機客流優(yōu)化市郊鐵路的停站方案，最小化列車總運行時間.

針對長距離高鐵，既有研究在優(yōu)化列車停站方案時，較少關(guān)注同時提升不同等級車站之間和不同出行距離旅客的出行效率.本文提出“減少部分列車的停站次數(shù)以提高大站間快車比例，同時增加相鄰大站間站站停列車以保障中小站列車服務(wù)頻率”的列車停站優(yōu)化措施，兼顧大站旅客快速直達，中小站旅客直達與換乘相結(jié)合的多種需求，減少旅客總出行時間損失.

1 問題描述與建模

1.1 高速鐵路列車停站方案優(yōu)化問題

本文立足提升我國高速鐵路旅客出行效率，旅客出行效率損失通過列車停站產(chǎn)生的旅客等待時間，以及旅客換乘的等待時間損失來衡量.結(jié)合現(xiàn)狀列車停站方案(作為初始方案)，通過減少部分列車的中小站停站次數(shù)，提高大站間快車比例、吸引大站客流；同時增加相鄰大站間站站停列車，確保中小站與鄰近大站之間有足夠的通達性和換乘便捷性.優(yōu)化過程中，根據(jù)現(xiàn)狀客流分布，將受停站調(diào)整影響的客流重新分配到其他列車上.問題的優(yōu)化目標為最小化所有旅客的時間損失.

對研究對象做出如下假設(shè)：①不調(diào)整初始方案中列車的起訖點、頻率和徑路；②初始方案中的列車帶流情況已知，由客票數(shù)據(jù)得出，僅對因取消停站不能被原列車服務(wù)的客流進行重新分配；③考慮旅客出行便捷性，規(guī)定旅客出行至多換乘1次；④列車停站時間設(shè)置為常數(shù)，旅客換乘時間假設(shè)為合理范圍內(nèi)的均值；⑤優(yōu)化方案可能因列車旅行時間縮短而吸引更多旅客，也可能因中小站列車停站次數(shù)減少，部分旅客流失；假設(shè)短期內(nèi)的客流量固定，暫不考慮客流誘增及流失情況.

1.2 優(yōu)化模型

模型中使用的符號含義如表1所示.

列車停站優(yōu)化模型為

表1 模型符號說明Table 1 Notations of model

目標函數(shù)：式(1)最小化所有旅客的時間損失，第1項表示列車中途停站給列車上旅客帶來的停站等待時間，第2項表示旅客由于換乘增加的等待時間.約束條件：式(2)和式(3)為目標函數(shù)線性化約束，作用是避免目標函數(shù)非線性化.式(4)～式(7)為客流守恒約束，當取消列車的某個停站時，與該停站相關(guān)的旅客既可以轉(zhuǎn)移到其他直達列車，也可以轉(zhuǎn)移到另外兩趟列車換乘出行；轉(zhuǎn)移客流量等于直達轉(zhuǎn)移與換乘轉(zhuǎn)移的客流之和，列車兩個停站之間的客流量等于原客流量與直達、換乘轉(zhuǎn)移來的客流量之和；其中，式(6)和式(7)為變量耦合約束.式(8)和式(9)為直達旅客上下車約束，當且僅當都等于1時，大于0，即列車能夠服務(wù)車站i與j之間的旅客.式(10)～式(13)為旅客選擇列車m、n換乘出行約束，當且僅當都等于1時，大于0，即列車能夠服務(wù)車站i與j之間并在t站換乘的旅客.式(14)～式(17)為列車停站約束，其中，式(14)為列車k在經(jīng)過的所有大站都必停(該約束也可以被松弛)；式(15)和式(16)表示列車k在其起訖點站必停；式(17)表示列車k在運行徑路上未經(jīng)過的車站不能停站.式(18)表示某列車經(jīng)過的任一區(qū)段，列車上的客流量不能大于該列車定員.式(19)～式(22)限制決策變量取值范圍.

2 遺傳算法設(shè)計

上述模型為混合整數(shù)線性規(guī)劃.當實例規(guī)模較大時，模型變量會急劇增加，直接求解難度很大.為提高求解效率，結(jié)合問題特點設(shè)計如下遺傳算法，流程如圖1所示.

圖1 遺傳算法求解流程Fig.1 Solving process of genetic algorithm

(1)編碼及初始化.

染色體按路網(wǎng)車站和列車直接編碼，將所有列車頭尾相連編為一行，形成染色體，每列列車編碼位數(shù)相同，為路網(wǎng)中車站個數(shù).例如，給定5個車站和4趟列車的停站方案，對列車停站方案的染色體編碼方式如圖2所示，其中，1表示停站，0表示不停站.從圖2可知，染色體長度為20位(4×5=20)，每條染色體為所有列車的一種停站組合.

圖2 染色體編碼形式Fig.2 Coding form of chromosome

將現(xiàn)狀列車停站方案和列車帶流情況作為初始解，利用鄰域搜索法生成限定規(guī)模的初始種群.以圖2染色體I為例，生成步驟如下：

Step 1將染色體隨機分成n個基因片段，確定每個基因片段的基準點，如圖3所示，n=3.

Step 2確定該點左右兩邊各m個點作為該基準點的鄰域，圖3中m=2.

Step 3通過隨機數(shù)控制各鄰域內(nèi)的點是否發(fā)生改變，遍歷鄰域內(nèi)每個點時生成0～1之間的隨機數(shù).若隨機數(shù)小于等于0.5，則發(fā)生改變；否則，不改變.

Step 4改變n、m取值及基準點位置，Step 1～Step 3操作，得到更多種群個體.

(2)解的可行化修復.

求解模型時直接調(diào)用Gurobi對轉(zhuǎn)移客流進行重新分配，保證不違背客流守恒、旅客上下車、變量取值等約束.故在遺傳算法求解過程中，主要存在新個體違背列車定員及停站約束的問題.

對于違背列車停站約束的個體，強制轉(zhuǎn)換列車停站狀態(tài)，使其滿足式(14)～式(17).對于違背列車定員約束的個體：一種可行化方法為放棄該染色體，繼續(xù)搜索其他可行方案；另一種方法為適當調(diào)低遺傳參數(shù)變異概率取值，防止某一車站多數(shù)列車的停站被取消，降低不可行解出現(xiàn)的概率.

圖3 鄰域搜索法生成初始種群Fig.3 Generation of original population using neighborhood search method

(3)適應(yīng)度評估.

式中：Fitness(x)為種群中個體x的適應(yīng)度值；Zmax為初始種群中目標函數(shù)值最大的個體的目標函數(shù)值；Zmin為預估的目標函數(shù)值下界；Z(x)為每代種群中個體x的目標函數(shù)值.式(23)為選取的適應(yīng)度函數(shù).

迭代過程中，若個體x1目標函數(shù)值Z(x1)大于Zmax，將該個體舍棄；若個體x2目標函數(shù)值Z(x2)小于Zmin，令Zmin=Z(x2)，重新計算當代種群中各個體的適應(yīng)度值.

(4)遺傳操作.

實例中，選擇操作采用輪盤賭方式，交叉操作選擇多點交叉算子，變異操作采用基本位變異法.

3 實例分析

選取京廣高鐵作為實例研究對象，總里程2 298 km，共36個車站，本文對下行方向(北京至廣州)的列車停站方案進行優(yōu)化.

3.1 數(shù)據(jù)準備

案例基于某年度11月某平峰日(周三)09:00-12:00時段內(nèi)的列車運行圖及客流數(shù)據(jù)，共有本線與跨線列車42列(跨線列車及其客流被預處理為本線區(qū)段列車和客流).車站按下行方向順序編號為1～36.列車停站時間損失θ=7 min(含起停車附加時分)，旅客換乘等待時間損失η=60 min，各列車定員按運行圖中列車的實際定員取值.

遺傳參數(shù)(種群規(guī)模、迭代次數(shù)、變異概率)取值對求解結(jié)果有較大影響.本文通過測試大量遺傳參數(shù)組合，平衡考慮求解效率與解的質(zhì)量，確定種群規(guī)模取10，迭代次數(shù)取100，變異概率取0.015.

3.2 模型求解

考慮是否松弛模型約束式(14)，以及是否增加相鄰大站間站站停列車，設(shè)計3個不同的列車停站調(diào)整方案，如表2所示，以便于進行方案優(yōu)化效果的對比.表中“相鄰大站間站站停列車”不是由算法產(chǎn)生的，是根據(jù)列車的起訖點設(shè)置條件與合理運距范圍預先指定的列車.

表2 列車停站調(diào)整方案Table 2 Strategies of adjusting train stops

應(yīng)用Python 2.7與Gurobi 7.5執(zhí)行遺傳算法，計算機配置為Intel(R)Core(TM)i7-6500U CPU(2.60 GHz)、8.00 GB.基于表2中的3個方案，對應(yīng)求解得到3個列車停站方案；限于篇幅僅展示方案3，如圖4所示，其尋優(yōu)收斂過程如圖5所示.各方案指標如表3所示.

圖4 優(yōu)化的列車停站方案(方案3)Fig.4 Optimized train stop plan(plan 3)

圖5 方案3尋優(yōu)收斂過程Fig.5 Convergence of plan 3 in process of optimization

3.3 優(yōu)化結(jié)果分析

與初始方案相比，3個優(yōu)化方案的列車總停站次數(shù)減少，分別為258，230，247次(初始方案為323次)；旅客時間損失較初始方案均顯著降低.方案3在增加相鄰大站間站站停列車(圖4中的“L”列車)后，與方案1相比，目標函數(shù)值進一步優(yōu)化，比初始方案旅客時間損失減少了40.08%.由于不限制列車在大站必停，方案2的優(yōu)化幅度最大，比初始方案旅客時間損失減少40.14%.

由于減少列車停站次數(shù)，約30%客流需轉(zhuǎn)移至其他列車.但換乘客流量并未增加很多(表3)，約占總客流的1%～4%；其中，方案3增加的站站停列車使中小站旅客換乘出行更便捷，所產(chǎn)生的換乘客流最多.

定義“大站間快車”為除大站外，在中小站總停站次數(shù)不超過設(shè)定數(shù)值σ的列車(如北京至廣州σ≤6的列車為大站間快車，σ取值與列車運距正相關(guān))，以此統(tǒng)計優(yōu)化方案的大站間快車數(shù).與初始方案相比，方案1和方案3中的“大站間快車”數(shù)分別增加70.9%和94.4%，大站之間的旅客有更多快車可以選擇.其中，方案3的列車停站時間損失最少，因此大站間快車數(shù)的增幅最高.

從模型目標函數(shù)值來看，方案2的優(yōu)化程度最高，但大站列車服務(wù)頻率被降低.方案3保證列車在大站都停站的基礎(chǔ)上，與方案2的目標函數(shù)值相近；雖然換乘客流較多，但每3 h開行1列相鄰大站間站站停列車，增加了中小站的列車停站頻率，不僅提升了車站之間的通達性，也可以較大程度地縮短旅客的換乘等待時間.

綜合上述分析，列車停站方案3具有較好的優(yōu)化效果.

表 3 列車停站方案優(yōu)化結(jié)果指標Table 3 Indicators of optimized train stop plans

4 結(jié)論

為提升我國長距離高速鐵路旅客的出行效率，本文基于減少列車中小站停站次數(shù)，增加相鄰大站間站站停列車策略，建立以最小化旅客時間損失為目標的列車停站方案優(yōu)化混合整數(shù)規(guī)劃模型，并設(shè)計了遺傳算法.

在京廣高鐵實例研究中，通過對比3個不同的優(yōu)化方案結(jié)果，驗證了“增加相鄰大站間站站停列車”策略最有助于減少長距離列車的停站次數(shù)，節(jié)省的列車停站時間最多且遠超出換乘時間的增加，使旅客出行效率指標較實際方案得到了明顯提升：增加大站間快車數(shù)，增幅達到94.4%，從旅行時間方面增強了高鐵競爭力；由于每3 h在相鄰大站之間增加開行站站停列車，中小站列車頻率至少為1列/(3h)，有助于引導部分旅客便捷換乘出行；旅客總體時間損失減少40.08%.

下一步研究可同時優(yōu)化列車起訖點、開行頻率和停站，進一步提高列車開行方案質(zhì)量；并通過鋪畫列車運行圖驗證方案的可實施性.