付慧伶，胡懷賓，武 鑫

(北京交通大學(xué)交通運(yùn)輸學(xué)院，北京100044)

0 引 言

鐵路旅客周期性列車(chē)開(kāi)行方案確定一個(gè)周期時(shí)間內(nèi)(如1 h 或2 h)的列車(chē)起訖點(diǎn)、停站、開(kāi)行頻率及編組定員等，相同種類的列車(chē)按一定周期時(shí)間間隔重復(fù)開(kāi)行，在1 d各個(gè)周期內(nèi)呈現(xiàn)基本相同的停站和運(yùn)行時(shí)分特征.其編制要求是列車(chē)起訖點(diǎn)、停站方式種類不能過(guò)多，列車(chē)運(yùn)距不能太長(zhǎng).將單周期的方案擴(kuò)展到全天后，列車(chē)具有服務(wù)頻率高、開(kāi)行間隔均勻、停站規(guī)律的特征.

周期性列車(chē)開(kāi)行方案和運(yùn)行圖，既方便旅客出行又利于運(yùn)輸組織.歐洲很多國(guó)家，日本及我國(guó)臺(tái)灣地區(qū)都有成功的實(shí)踐，也有很多理論研究，例如M.T.Claessens[1]，S.Scholl[2]，M.Goerigk[3]，Yu-Hern Chang[4]等學(xué)者，在鐵路成本或旅客效益最優(yōu)目標(biāo)下決策一個(gè)周期內(nèi)的列車(chē)組合.國(guó)內(nèi)學(xué)者也開(kāi)始關(guān)注列車(chē)的周期組織方式：汪波[5]優(yōu)化了京津城際鐵路的周期開(kāi)行方案；顏穎[6]分析了高速鐵路周期化列車(chē)開(kāi)行方案編制過(guò)程；肖龍文[7]研究了鐵路列車(chē)公交化開(kāi)行，針對(duì)廣深線兩站之間的列車(chē)開(kāi)行對(duì)數(shù)、停車(chē)次數(shù)進(jìn)行優(yōu)化；W.Zhou[8]，李天琦[9]等研究了周期性列車(chē)運(yùn)行圖優(yōu)化問(wèn)題.既有周期性列車(chē)開(kāi)行方案的研究特點(diǎn)是：針對(duì)較小型線網(wǎng)，列車(chē)密度不高、運(yùn)距短、停站少、容易組織站站停列車(chē)，多采用1 h周期；旅客運(yùn)程較短，優(yōu)化滿足旅客單一方面的需求，如使所有旅客的乘車(chē)時(shí)間最短[4]或換乘次數(shù)最少[2].

我國(guó)高速鐵路周期性列車(chē)開(kāi)行方案優(yōu)化更加復(fù)雜：一是在旅客直達(dá)化目標(biāo)下，很多高鐵線長(zhǎng)站多、列車(chē)密度大、長(zhǎng)車(chē)比例高，考慮線路能力，不宜開(kāi)行旅速低的長(zhǎng)距離多站或站站停列車(chē)，需要停站次數(shù)受限、速差小的多種隔站停列車(chē)，相互配合提高站間直達(dá)率；二是為了使一個(gè)周期容納增多的列車(chē)隔站停方式，要求周期時(shí)間長(zhǎng)于1 h，如2 h或更長(zhǎng)，因此起訖點(diǎn)和停站組合規(guī)模變大；三是不同車(chē)站旅客的乘車(chē)距離、時(shí)空分布，對(duì)列車(chē)頻次、旅速、直達(dá)與中轉(zhuǎn)等服務(wù)水平的接受程度差別明顯，旅客需求的異質(zhì)程度更高，在周期能力制約下，要實(shí)現(xiàn)用少量列車(chē)更好地匹配多類客流需求.

針對(duì)這些復(fù)雜特點(diǎn)，除了考慮減少鐵路成本和旅客乘車(chē)時(shí)間目標(biāo)，研究在一個(gè)周期內(nèi)，以大站停和多種隔站停列車(chē)為主優(yōu)化列車(chē)組合，最大程度保證站間直達(dá)率、滿足旅客異質(zhì)需求.由此提出一個(gè)新模型，并設(shè)計(jì)可求解大規(guī)模實(shí)際問(wèn)題的算法.

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

1.1 優(yōu)化問(wèn)題及定義

(1)問(wèn)題描述.

基于高峰客流確定高峰周期方案.為滿足旅客的多樣需求，一個(gè)周期內(nèi)既開(kāi)行停站少、旅速高的大站停快車(chē)，也開(kāi)行隔站停的相對(duì)中低速列車(chē)，站站停列車(chē)只考慮在較短區(qū)段內(nèi)開(kāi)行.在生成列車(chē)時(shí)，從一個(gè)備選列車(chē)集合中優(yōu)選一部分列車(chē)方案線(每條方案線是起訖點(diǎn)、停站和編組的一種組合)，決策選出方案線的開(kāi)行頻率，以最低列車(chē)開(kāi)行成本滿足旅客需求.

(2)車(chē)站、列車(chē)、客流的層級(jí)劃分.

對(duì)一條高鐵線的車(chē)站采取3 級(jí)劃分：1 級(jí)節(jié)點(diǎn)為大站，2 級(jí)節(jié)點(diǎn)為中等車(chē)站，3 級(jí)節(jié)點(diǎn)為小站.大站之間開(kāi)行的為“1層級(jí)列車(chē)”(簡(jiǎn)寫(xiě)為I-列車(chē))，大、中站都?？康臑椤? 層級(jí)列車(chē)”(II-列車(chē))，在小站有停站的為“3 層級(jí)列車(chē)”(III-列車(chē))，對(duì)應(yīng)定義3 個(gè)層級(jí)的客流，即I-客流，II-客流和III-客流.

(3)備選列車(chē)集合生成規(guī)則.

備選列車(chē)方案線的停站組合按特定的規(guī)則來(lái)枚舉生成.規(guī)則為：按運(yùn)距，確定列車(chē)停站次數(shù)上限；考慮停站布點(diǎn)均衡性，起訖點(diǎn)內(nèi)所有大站區(qū)段至少有一次停站；設(shè)定列車(chē)連續(xù)停站次數(shù)上限；III-列車(chē)要保證一定數(shù)量比例的小站停等.

1.2 優(yōu)化模型

(1)集 合.

U——高鐵線網(wǎng)中所有客流OD對(duì)集合，每個(gè)客流OD記作u；

UH——I-客流OD對(duì)集合；

UM——II-客流OD對(duì)集合；

UTF——不提供直達(dá)列車(chē)服務(wù)的客流OD對(duì)集合；

L——備選列車(chē)集合，每條列車(chē)方案線記作l；

LH——備選的I-列車(chē)集合；

LM——備選的II-列車(chē)集合；

Lu——能服務(wù)客流OD對(duì)u的備選列車(chē)集合，集合中l(wèi)u表示列車(chē)l可以服務(wù)客流OD對(duì)u；

S——其每個(gè)元素s(l)為每列車(chē)l通過(guò)沿途停站能服務(wù)的客流OD對(duì)集合，?s(l)=U；

E——鐵路區(qū)間集合，每個(gè)區(qū)間為e，任意客流OD對(duì)u必定覆蓋一個(gè)或多個(gè)區(qū)間，u覆蓋e時(shí)記為e∈u；

Le——運(yùn)行徑路覆蓋區(qū)間e的列車(chē)集合，集合中l(wèi)e表示列車(chē)l覆蓋區(qū)間e，Le=?{e∈s(le)|le∈L} ；

V——高鐵線網(wǎng)的車(chē)站集合，每個(gè)車(chē)站為v；

Vu——客流OD對(duì)u之間的1、2級(jí)節(jié)點(diǎn)車(chē)站集合，u的起點(diǎn)站為v′u，終點(diǎn)站為v″u.

(2)參 數(shù).

wl——列車(chē)l的開(kāi)行成本；

T——規(guī)劃的周期時(shí)間長(zhǎng)度(h)；

Fu——在T內(nèi)，客流OD對(duì)u的列車(chē)服務(wù)頻率需求；

Qu——在T內(nèi)，客流OD對(duì)u的客流量；

φl(shuí)u——可服務(wù)客流OD 對(duì)u的列車(chē)lu對(duì)于u所在區(qū)段內(nèi)的停站時(shí)間損失(min)；

τl——列車(chē)方案線l的停站總次數(shù)；

——在T內(nèi)，區(qū)間e的列車(chē)通過(guò)能力；

——在T內(nèi)，經(jīng)驗(yàn)下可采用的停站方式總數(shù)；

dl——列車(chē)l的運(yùn)行距離(km)；

——列車(chē)l的單位運(yùn)行距離成本(元/km)；

——列車(chē)l由于在中間站停站所產(chǎn)生的成本(元)；

——列車(chē)l的固定運(yùn)行成本(元)；clu——可服務(wù)客流OD 對(duì)u的列車(chē)lu對(duì)于u所在區(qū)間(段)內(nèi)列車(chē)的定員；

θ——列車(chē)客座率，一般θ≤1.0.

(3)決策變量.

xs(l)——子集s(列車(chē)l)被選擇時(shí)xs(l)=1，否則xs(l)=0；

fl——在T內(nèi)，列車(chē)l的開(kāi)行頻率，該整數(shù)變量決定u被直達(dá)列車(chē)服務(wù)的次數(shù).

(4)模 型.

模型包括兩個(gè)優(yōu)化目標(biāo)，一是總列車(chē)開(kāi)行成本最低，即

式(1)中每列車(chē)的成本包括固定成本和變動(dòng)成本，變動(dòng)成本與其運(yùn)行距離、停站次數(shù)成正比，即

二是旅客乘車(chē)時(shí)的停站損失時(shí)間最小，即

對(duì)于給定高鐵線網(wǎng)，旅客運(yùn)程和列車(chē)區(qū)間運(yùn)行速度是固定的，旅客乘車(chē)時(shí)間長(zhǎng)短取決于列車(chē)在途經(jīng)車(chē)站的停站時(shí)間(包括起停附加時(shí)分)和次數(shù).目標(biāo)函數(shù)式(3)使1、2 級(jí)節(jié)點(diǎn)旅客由列車(chē)停站而產(chǎn)生的時(shí)間損失最少，縮短總乘車(chē)時(shí)間.

求解多目標(biāo)問(wèn)題時(shí)可以統(tǒng)一量級(jí)，再根據(jù)目標(biāo)的重要度，設(shè)置權(quán)重系數(shù)λ，將其轉(zhuǎn)化為單目標(biāo)規(guī)劃問(wèn)題.

客流OD 的列車(chē)服務(wù)頻率是衡量服務(wù)水平的一個(gè)重要指標(biāo)，生成列車(chē)開(kāi)行方案時(shí)應(yīng)滿足各客流OD的服務(wù)頻率需求下限，即

還需要保證區(qū)間(段)列車(chē)席位能力不能低于區(qū)間(段)客流密度，即

如果加入層級(jí)索引，式(4)和式(5)可以共同約束用某種等級(jí)的列車(chē)服務(wù)對(duì)應(yīng)層級(jí)的客流，即I-列車(chē)、II-列車(chē)、III-列車(chē)分別服務(wù)I-客流、II-客流、III-客流.利用式(4)，針對(duì)I-客流，按距離別對(duì)Fu設(shè)置較大值，意味著向大站旅客提供I-列車(chē)的“高速度、高直達(dá)頻次”服務(wù)；針對(duì)II-客流，F(xiàn)u值適當(dāng)降低，向中等車(chē)站旅客提供II-列車(chē)的“較高速度、較高直達(dá)頻次”服務(wù)；針對(duì)III-客流，F(xiàn)u設(shè)置最低值或?yàn)?，向小站旅客保證III-列車(chē)的“一定頻次的直達(dá)或中轉(zhuǎn)”服務(wù).

在規(guī)劃周期時(shí)間T內(nèi)，要保證經(jīng)過(guò)各區(qū)間的總列車(chē)數(shù)不能超過(guò)該區(qū)間通過(guò)能力上限，即

受周期能力限制，如果III-列車(chē)不能保證小站旅客全部直達(dá)，則部分需要中轉(zhuǎn)(即部分Fu值為0).要保證這些旅客能夠在小站有機(jī)會(huì)乘坐列車(chē)，到某個(gè)換乘條件良好的1、2級(jí)節(jié)點(diǎn)實(shí)現(xiàn)一次中轉(zhuǎn).

考慮到列車(chē)方案線之間的異質(zhì)性(由停站次數(shù)不同體現(xiàn))影響運(yùn)行圖能力，在T內(nèi)可以限制列車(chē)停站方式的總數(shù).當(dāng)區(qū)間通過(guò)能力緊張時(shí)，通過(guò)調(diào)節(jié)N(T)值，鋪畫(huà)運(yùn)行圖，可以評(píng)估停站結(jié)構(gòu)對(duì)能力的影響.

決策變量的關(guān)系約束為

式中：M為較大正整數(shù).

限制fl為非負(fù)整數(shù)的約束為

限制xs(l)為0或1的約束為

2 交叉熵算法

上述模型是線性整數(shù)規(guī)劃，當(dāng)備選列車(chē)集合規(guī)模很大時(shí)求解困難.結(jié)合模型特點(diǎn)設(shè)計(jì)基于交叉熵的算法(Cross Entropy Algorithm，CE算法).

CE 算法基于概率函數(shù)產(chǎn)生初始樣本，隨歷次迭代縮小 ||L規(guī)模.通過(guò)提取每次迭代后解集中重要樣本的參數(shù)特征，更新概率函數(shù)參數(shù)，不斷迭代收斂得到優(yōu)化解.基本步驟為：

Step 1樣本群初始化.

構(gòu)造m個(gè)初始樣本L1,L2,…,Li,…,Lm，每個(gè)樣本中有n條列車(chē)方案線，初始樣本群為一個(gè)m×n矩陣.決策變量xs(l)服從伯努利分布，第t次迭代時(shí)備選集中方案線l對(duì)應(yīng)變量xs(l)的取值概率函數(shù)為為概率函數(shù)參數(shù).t=1 時(shí)，利用Pl(1)為xs(l)隨機(jī)賦值，xs(l)=1 表示方案線l被選中；驗(yàn)證t=1 時(shí)隨機(jī)產(chǎn)生的樣本群，保證滿足預(yù)設(shè)的客流OD直達(dá)約束.

Step 2優(yōu)化模型求解.

基于xs(l)賦值，利用模型求解每組樣本中被選中方案線的頻率fl，記錄目標(biāo)函數(shù)值Zi(1 ≤i≤m).

Step 3精英樣本提取.

將模型目標(biāo)函數(shù)值Zi作為每組樣本的評(píng)價(jià)函數(shù)，構(gòu)造評(píng)價(jià)函數(shù)矩陣Z=(Z1,Z2,…,Zm)，并對(duì)Zi排序，選取一定比例σ的評(píng)價(jià)函數(shù)值較小樣本作為精英樣本.

Step 4新樣本群生成.

利用精英樣本特征更新第t+1次迭代時(shí)概率函數(shù)，即當(dāng)時(shí)，利用伯努利概率函數(shù)繼續(xù)為新樣本賦值，并與第t次迭代時(shí)保留的精英樣本群合并，作為新樣本群進(jìn)入第t+1次迭代.

Step 5迭代終止.

當(dāng)樣本的評(píng)價(jià)函數(shù)值Zi均相同時(shí)，說(shuō)明收斂到(局部)最優(yōu)解，可終止迭代；也可設(shè)置迭代次數(shù)或時(shí)間上限.不滿足迭代終止條件時(shí)轉(zhuǎn)Step 2.

3 案例計(jì)算與結(jié)果分析

3.1 案例設(shè)計(jì)

選取車(chē)站分布和客流特征區(qū)別明顯的兩條線路，即京滬高鐵和滬昆高鐵(滬湘段)，優(yōu)化本線區(qū)段的周期性列車(chē)開(kāi)行方案，驗(yàn)證模型與算法.京滬高鐵全長(zhǎng)1 318 km，途經(jīng)23 個(gè)車(chē)站，1、2 級(jí)節(jié)點(diǎn)客流比重較大；滬昆高鐵滬湘段里程1 083 km，途經(jīng)28個(gè)車(chē)站，3級(jí)節(jié)點(diǎn)小站數(shù)目多達(dá)19個(gè)，方案中的III-列車(chē)比例要高于京滬高鐵.

案例均基于實(shí)際客流數(shù)據(jù)，模型參數(shù)設(shè)置如表1所示，限于篇幅，省略Fu、Qu及φl(shuí)u等大矩陣列表，案例中對(duì)N(T)暫不做限制.令UTF為空集，驗(yàn)證能力限制下，能否實(shí)現(xiàn)所有客流OD之間有直達(dá)列車(chē)服務(wù)；為保證較高直達(dá)率，T應(yīng)長(zhǎng)于1 h，通過(guò)測(cè)試，T=2 h.

表1 模型參數(shù)設(shè)置Table1 Model parameter setting

3.2 結(jié)果分析

(1)方案結(jié)果.

對(duì)京滬、滬昆高鐵兩個(gè)案例，均先利用CPLEX 12.3 軟件直接求解，再利用CE 算法求解，借助以2.00 GHz運(yùn)行的Intel Xeon E7處理器運(yùn)算.執(zhí)行CE 算法時(shí)，設(shè)置48 個(gè)樣本群，計(jì)算時(shí)間上限4 000 s，σ=0.5.

為保證各個(gè)區(qū)間(段)列車(chē)與客流在層級(jí)上的精確匹配，求解時(shí)針對(duì)各層級(jí)客流分別生成方案.案例求解指標(biāo)如表2所示，以京滬案例為例展示結(jié)果，如圖1所示，線旁數(shù)字為頻率.

對(duì)比表2指標(biāo)，京滬案例驗(yàn)證了CE 算法的正確性，滬昆案例驗(yàn)證了CE算法在III-列車(chē)比例高、大規(guī)模變量決策復(fù)雜的情形下，方案求解具有可行性.

表2 案例求解指標(biāo)Table2 Indicators of solutions

圖1 京滬高鐵高峰周期列車(chē)開(kāi)行方案Fig.1 Peak-hour periodic line plan of Beijing-Shanghai high-speed railway

(2)服務(wù)指標(biāo).

在案例設(shè)置參數(shù)Fu、T與τl組合下，列車(chē)開(kāi)行方案均滿足區(qū)間能力限制，實(shí)現(xiàn)了客流OD之間100%的直達(dá)率.再以京滬案例為例，統(tǒng)計(jì)方案的主要服務(wù)指標(biāo)，如表3所示.

優(yōu)化方案利用8個(gè)起訖點(diǎn)、20種停站方式的列車(chē)服務(wù)于253 個(gè)OD 的旅客.向大站旅客提供的是“高速度、高直達(dá)頻次”的列車(chē)服務(wù)，列車(chē)頻率分布符合中短距離旅客出行頻次一般高于長(zhǎng)距離旅客的現(xiàn)實(shí).小站列車(chē)服務(wù)頻率最低，但旅客不僅都能乘坐直達(dá)列車(chē)，并且每隔一個(gè)周期時(shí)間有相同的列車(chē).總體上，列車(chē)服務(wù)質(zhì)量體現(xiàn)差異化，隨客流層級(jí)的增高而提升.

由于3 個(gè)層級(jí)列車(chē)均滿足對(duì)應(yīng)層級(jí)的客流需求，各區(qū)間的總列車(chē)席位有富余，占用了較高的區(qū)間能力20(列/2 h).本文也對(duì)全部層級(jí)客流整體生成方案進(jìn)行了測(cè)試，區(qū)間能力最高占用為17，且列車(chē)開(kāi)行成本降低14.8%.但節(jié)省線路能力和成本是以犧牲服務(wù)質(zhì)量為代價(jià)的，部分大站客流由II-列車(chē)或III-列車(chē)輸送，將增加乘車(chē)時(shí)間.若希望繼續(xù)節(jié)省能力和成本，可讓部分小站客流中轉(zhuǎn)(令UTF不為空集)，或同時(shí)減小τl值；更多能力、成本與服務(wù)水平之間的博弈關(guān)系，本文不再詳細(xì)分析.

表3 京滬案例服務(wù)指標(biāo)Table3 Line plan performance of Beijing-Shanghai high-speed railway

將圖1方案擴(kuò)展到全天(平峰時(shí)段適當(dāng)減少列車(chē))，與實(shí)際非周期列車(chē)開(kāi)行方案對(duì)比，兩方面指標(biāo)有明顯改進(jìn).一是優(yōu)化方案中，各區(qū)間I-列車(chē)比例都在40%以上，而實(shí)際方案平均約為21%；大站?？燔?chē)比例提升有利于增強(qiáng)京滬高鐵競(jìng)爭(zhēng)力；二是中小站之間列車(chē)頻率普遍提高，例如定遠(yuǎn)—丹陽(yáng)北實(shí)際方案1 d只有2趟列車(chē)，且相隔近8 h，優(yōu)化方案每2 h有1～3趟列車(chē)，列車(chē)開(kāi)行間隔縮短且規(guī)律，相對(duì)于非周期列車(chē)不規(guī)律開(kāi)行更易于吸引客流.

4 結(jié) 論

針對(duì)我國(guó)高鐵周期性列車(chē)開(kāi)行方案問(wèn)題的復(fù)雜性，建立優(yōu)化模型，決策周期時(shí)間內(nèi)大站停和多種隔站停列車(chē)組合.設(shè)計(jì)CE算法，通過(guò)實(shí)例求解，驗(yàn)證了算法有效性.京滬高鐵優(yōu)化方案在2 h時(shí)周期內(nèi)利用3個(gè)服務(wù)水平層級(jí)、8個(gè)起訖點(diǎn)之間20種停站方式的列車(chē)，實(shí)現(xiàn)253個(gè)客流OD之間100%直達(dá)，滿足了多樣化客流需求；列車(chē)旅速、節(jié)點(diǎn)與OD列車(chē)服務(wù)頻率等指標(biāo)均較優(yōu)，與實(shí)際方案對(duì)比也取得良好優(yōu)化效果.

本文模型針對(duì)高鐵本線列車(chē)開(kāi)行方案優(yōu)化，如果結(jié)合跨線列車(chē)將涉及本線外其他銜接線路上的列車(chē)結(jié)構(gòu)、客流、能力等約束，是一個(gè)聯(lián)動(dòng)多線、多流的網(wǎng)絡(luò)化復(fù)雜問(wèn)題，將在后續(xù)展開(kāi)研究.