許若曦，聶 磊，付慧伶*

(1.北京宇恒未來(lái)規(guī)劃設(shè)計(jì)有限公司，北京100022；2.北京交通大學(xué)交通運(yùn)輸學(xué)院，北京100044)

0 引言

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

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

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

1 問(wèn)題描述與建模

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

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

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

1.2 優(yōu)化模型

模型中使用的符號(hào)含義如表1所示.

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

表1 模型符號(hào)說(shuō)明Table 1 Notations of model

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

2 遺傳算法設(shè)計(jì)

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

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

(1)編碼及初始化.

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

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

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

Step 1將染色體隨機(jī)分成n個(gè)基因片段，確定每個(gè)基因片段的基準(zhǔn)點(diǎn)，如圖3所示，n=3.

Step 2確定該點(diǎn)左右兩邊各m個(gè)點(diǎn)作為該基準(zhǔn)點(diǎn)的鄰域，圖3中m=2.

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

Step 4改變n、m取值及基準(zhǔn)點(diǎn)位置，Step 1～Step 3操作，得到更多種群個(gè)體.

(2)解的可行化修復(fù).

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

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

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

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

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

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

(4)遺傳操作.

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

3 實(shí)例分析

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

3.1 數(shù)據(jù)準(zhǔn)備

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

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

3.2 模型求解

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

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