黃志鵬，田志強(qiáng)，司曉鑫

時(shí)段偏好的高鐵開行方案的雙層規(guī)劃方法

黃志鵬1，田志強(qiáng)1，司曉鑫2

(1. 蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070；2. 中國鐵路蘭州局集團(tuán)有限公司 蘭州車務(wù)段，甘肅 蘭州 730050)

在一條擁擠的高速鐵路客運(yùn)走廊上，通常有多列平行車次的列車在不同的時(shí)段運(yùn)行，旅客在出行時(shí)具有較大的選擇空間。旅客對出行時(shí)段的偏好是影響旅客需求分布的最重要因素，最大限度地滿足旅客對出行時(shí)間的偏好需求，并合理制定列車開行方案引導(dǎo)旅客合理出行以避免出行擁擠是本文的研究目的。首先分析影響旅客出行時(shí)段偏好的2個重要因素，吸引度與擁擠度。據(jù)此構(gòu)建旅客出行阻抗函數(shù)，并建立一個雙層規(guī)劃模型，上層規(guī)劃是以運(yùn)營成本最小為目標(biāo)的整數(shù)規(guī)劃模型，用于確定列車停站方案和開行頻率；下層規(guī)劃是一個用戶平衡模型，用于計(jì)算客流在優(yōu)化的停站方案上基于用戶均衡的分配結(jié)果。最后，根據(jù)模型特點(diǎn)設(shè)計(jì)了嵌套Frank-Wolfe算法的啟發(fā)式算法，并通過仿真計(jì)算對模型和算法的可行性進(jìn)行了驗(yàn)證和分析。

高速鐵路；列車開行方案；雙層規(guī)劃；用戶平衡；啟發(fā)式算法

旅客選擇高鐵出行不僅僅是對傳統(tǒng)鐵路客運(yùn)核心產(chǎn)品——“位移”的需求，同時(shí)對旅客出行品質(zhì)提出了更高的要求，而出行時(shí)段的選擇則是旅客最關(guān)心的需求之一。旅客會根據(jù)自身的出行習(xí)慣、出行目的和出行經(jīng)驗(yàn)來選擇最理想的出行時(shí)段。在高鐵全天運(yùn)營的各個時(shí)段上，旅客出行需求具有不均衡特征，表現(xiàn)出明顯的時(shí)段偏好性。另一方面，鐵路部門在不同時(shí)段組織的各種停站方案的列車也是影響旅客出行選擇的關(guān)鍵因素。因此，基于旅客對出行時(shí)段的偏好，優(yōu)化各個出行時(shí)段列車的停站方案，使旅客出行需求與列車停站方案具有良好的耦合關(guān)系是本研究的主要目的。國外學(xué)者一般是將旅客列車停站方案作為列車時(shí)刻表(Train Timetable Problem, TTP)優(yōu)化問題的一個重要部分進(jìn)行研究。其中大部分是站在運(yùn)輸效益最大化角度進(jìn)行的研究。YUE等[1?2]用0-1決策變量表示列車在中間站是否停站，構(gòu)建了一個以運(yùn)輸收益最大為目標(biāo)的TTP模型求解了大規(guī)模網(wǎng)絡(luò)條件下高速鐵路列車停站優(yōu)化問題。QI 等[3]以列車空座位運(yùn)行距離和所有列車總停站數(shù)最小為目標(biāo)建立了一個多目標(biāo)線性規(guī)劃模型優(yōu)化列車停站方案。近十年來，綜合考慮旅客的出行質(zhì)量，將旅客出行時(shí)間或出行費(fèi)用優(yōu)化納入TTP優(yōu)化模型的研究較多。Jens等[4]建立了一個雙層規(guī)劃模型優(yōu)化旅客列車停站問題。SHANG等[5]通過構(gòu)造多商品流模型，優(yōu)化客流的分配和列車的停站方案?？紤]到列車停站次數(shù)對運(yùn)輸效益的影響，部分學(xué)者將列車停站次數(shù)作為優(yōu)化目標(biāo)或者約束條件。NIU等[6]以旅客總等待時(shí)間最小為目標(biāo)研究了時(shí)變條件下一條高鐵走廊的列車時(shí)刻表優(yōu)化問題。李得偉等[7]以總停站次數(shù)最少為目標(biāo)，將節(jié)點(diǎn)服務(wù)頻率、站間服務(wù)可達(dá)性、單個列車停站次數(shù)等作為主要約束條件，構(gòu)建列車停站方案的非線性規(guī)劃模型。張小炳等[8?10]從列車停站數(shù)量的均衡性和區(qū)間的可達(dá)性出發(fā)，建立高速鐵路列車停站方案的非線性多目標(biāo)優(yōu)化模型。趙杰群等[11]以列車停站費(fèi)用最小化為優(yōu)化目標(biāo)，建立了機(jī)會約束模型優(yōu)化了列車停站方案問題。劉璐等[12]基于旅客需求的時(shí)變特征，建立了時(shí)空狀態(tài)三維出行網(wǎng)絡(luò)，協(xié)同優(yōu)化了列車運(yùn)行圖和列車停站方案問題?？紤]到旅客出行需求與運(yùn)輸企業(yè)效益的博弈關(guān)系，一些學(xué)者試圖建立雙層規(guī)劃模型對該問題進(jìn)行數(shù)學(xué)描述，并取得了一定的成果。鄧連波等[13?15]通過建立雙層規(guī)劃模型優(yōu)化列車停站方案。模型的上層為旅客廣義出行費(fèi)用最小和列車?？空緮?shù)量限制，下層為多類用戶均衡客流分配模型。本文擬分析影響旅客出行時(shí)段偏好性的主要因素，建立一個雙層規(guī)劃模型來優(yōu)化一條高鐵線路上不同時(shí)段各種停站方案列車的開行數(shù)量，并依據(jù)用戶平衡規(guī)則將客流分配在各個出行時(shí)段上。論文的主要創(chuàng)新點(diǎn)：首先，將旅客的出行時(shí)段偏好與列車停站方案結(jié)合起來協(xié)同優(yōu)化，并將多OD客流需求分配在各個出行時(shí)段上。其次，不同于以往周期化的停站方案優(yōu) 化[16]，本文制定的停站方案按照出行時(shí)段分別優(yōu)化停站方案。

1 問題分析

1.1 列車類型和時(shí)段劃分

1.2 旅客出發(fā)時(shí)段偏好

1.2.1 出發(fā)時(shí)段的吸引度

旅客對各個出發(fā)時(shí)段的偏好性，表現(xiàn)為不同時(shí)段對旅客的吸引度有很大差異。這種差異是客觀存在的，并受到多種客觀因素的影響。如通勤客流占全部客流比重較大的車站，對旅客吸引度最高的時(shí)段為早晚高峰時(shí)段；又如旅客總是期望在城市公交方便的白天時(shí)段出行等等，均為影響旅客選擇出行時(shí)段的客觀因素。

圖1 出發(fā)時(shí)段吸引度的三角模糊數(shù)分布

1.2.2 出發(fā)時(shí)段的擁擠度

旅客對各個出行時(shí)段的偏好性，還表現(xiàn)為旅客對不同時(shí)段擁擠度的選擇。當(dāng)某個出行時(shí)段的吸引度較大時(shí)，大量的旅客均期望在這個時(shí)段出行。這時(shí)，這個時(shí)段的擁擠度也會大大提高。如旅客選擇在吸引度較大的時(shí)段出行時(shí)，有可能因時(shí)段需求旺盛而未能購得車票；或者旅客為了確保能夠在這個時(shí)段出行，必須提前很久購票，使得旅客的出行靈活性降低，帶來很大的不便。

1.2.3 出發(fā)時(shí)段偏好的量化

2 模型和算法

2.1 數(shù)學(xué)模型

2.1.1 符號定義

2.1.2 上層規(guī)劃

上層規(guī)劃的目標(biāo)是鐵路運(yùn)輸企業(yè)的運(yùn)營成本最小。不同停站方案的列車由于能耗和占用沿途車站設(shè)備的因素，其運(yùn)營成本是不相同的。

2.1.3 下層規(guī)劃

下層規(guī)劃是一個符合Wardrop第一原理的用戶平衡配流模型。

2.1.4 上、下層的聯(lián)系

圖2 上下層規(guī)劃的數(shù)據(jù)交換

這樣，上層規(guī)劃的列車開行方案和下層規(guī)劃的客流分配結(jié)果之間，會循環(huán)反復(fù)的調(diào)整，直至達(dá)到滿意解為止。

2.2 算法設(shè)計(jì)

論文所建模型是一個雙層規(guī)劃問題，它被公認(rèn)為是求解極其困難的NP完全問題。本文設(shè)計(jì)了嵌套Frank-Wolfe方法的啟發(fā)式算法進(jìn)行求解。算法流程如下。

Step 4整數(shù)編碼：對Step 1產(chǎn)生的0～1編碼染色體中“1”的基因位置隨機(jī)賦一個整數(shù)值，并滿足式(6)和式(7)的約束。

3 算例

3.1 參數(shù)設(shè)置

本文以蘭州西—西安北高鐵為例。為了方便表示，將蘭州西站編號為1，按照列車上行方向依次編號，其中蘭州西、西安北為始發(fā)、終到車站，必停車；另外在4個區(qū)域中心所在的定西北站、天水南站、寶雞南站、咸陽秦都站必停車；鐵路運(yùn)輸部門將列車在其他車站的停車次數(shù)設(shè)置為0～2次，則全部備選停站方案共11種，如圖3所示。

圖3 列車停站備選方案

該高鐵上所有起訖點(diǎn)(OD)間的客流需求如表1所示。本文以1 h為一個時(shí)段，將高鐵全天的發(fā)車時(shí)間(6:00～22:00)劃分為16個時(shí)段，并將6:00～7:00標(biāo)記為時(shí)段1，按照時(shí)間順序依次編號2,3,…,16。各出發(fā)時(shí)段的吸引度，如表2所示。其中，距離始發(fā)站較遠(yuǎn)的車站，每日首列車到達(dá)該站時(shí)的時(shí)段會相應(yīng)延遲，如車站3到9，將其吸引度設(shè)置為0。

表1 OD客流需求

3.2 計(jì)算結(jié)果

通過matlab2014a軟件編程，對該算例進(jìn)行求解，下層規(guī)劃計(jì)算結(jié)果如表5所示。各上車站的OD客流被分配在各個時(shí)段上出行，各時(shí)段客流具有明顯的波動性。同一車站旅客出行的阻抗值旅客出行阻抗?jié)M足UE平衡法則，在誤差范圍內(nèi)均相等，符合Wardrop第一原理[17]。

表2 各個車站在各出發(fā)時(shí)段的吸引度參數(shù)

表3 不同停站方案列車的開行成本

表4 各出發(fā)站的服務(wù)能力

通過下層規(guī)劃的配流結(jié)果和上層規(guī)劃開行方案的迭代，最終經(jīng)過100代的進(jìn)化篩選，得到滿意解。共開行95列車，其中，第12時(shí)段開行列車數(shù)量最多，為9列，第7，16時(shí)段開行列車數(shù)量最少，均為4列。各個時(shí)段列車開行數(shù)量的分布情況如圖4所示。其中，在非必停站，3站、4站、7站、8站停車次數(shù)分別為36，32，25和38次。從圖4中不難發(fā)現(xiàn)，各時(shí)段列車開行數(shù)量分布與各時(shí)段的吸引度分布(圖4中僅列出1站和5站的吸引度作為示例來說明。)總體保持波峰波谷趨勢一致。但是又不完全符合旅客的對各出發(fā)時(shí)段的吸引度。主要有2個原因：第一，高峰時(shí)段由于擁擠會分流部分旅客；第二，不同出行時(shí)段對各車站旅客的吸引度不同。

表5 各時(shí)段的流量分配結(jié)果

圖4 各時(shí)段列車開行數(shù)量

16個時(shí)段11種列車的分布情況，如圖5所示。各類列車均有開行，能夠服務(wù)沿途所有車站的旅客乘降，服務(wù)于各OD對的列車數(shù)量如表6所示，對于客流量較小的OD對，服務(wù)于該OD對的列車數(shù)量也相應(yīng)較少，如OD對(3,4)、(4,7)等，從而降低了列車停站成本。但是各類列車的分布不均勻，如表7所示。其中，第3，8類列車開行數(shù)量最多，第10類列車開行數(shù)量最少。由于不同列車能夠服務(wù)的OD客流是不同的，而不同OD客流量大小也有差異，這直接影響了優(yōu)化后的列車開行方案。然而，不可否認(rèn)的是，本文采用的啟發(fā)式算法并不能完全尋找到最優(yōu)解，因此，本算例計(jì)算的列車開行方案必然有等效方案。

圖5 各時(shí)段各種停站方案列車的開行數(shù)量

表6 服務(wù)于各OD客流的列車數(shù)量

在客流高峰時(shí)段，列車開行數(shù)量的最大值為9列，小于發(fā)車能力12列。本算例計(jì)算結(jié)果表明在客流高峰時(shí)段滿負(fù)荷發(fā)車并不能完全滿足所有旅客的出行需求，旅客并不會機(jī)械的完全按照出發(fā)時(shí)間吸引度的高峰時(shí)段出行，部分旅客會選擇在低峰時(shí)段出行，應(yīng)增加低峰時(shí)段的列車開行數(shù)量。

表7 不同停站方案列車的開行數(shù)量

4 結(jié)論

1) 旅客對出發(fā)時(shí)段的偏好性是一個動態(tài)平衡的過程，與客觀的時(shí)段吸引度成正比，與動態(tài)的擁擠度成反比。

2) 不同車站的出行阻抗也是不同的，該值與各時(shí)段對旅客的吸引度相關(guān)。

3) 本文構(gòu)建的雙層規(guī)劃模型能夠描述旅客出行決策和高鐵列車開行方案優(yōu)化的動態(tài)博弈過程。 本文只研究了一個開行區(qū)段的高鐵走廊，后續(xù)將研究多個運(yùn)行區(qū)段的列車開行方案。

[1] YUE Y, WANG S, ZHOU L, et al. Optimizing train stopping patterns and schedules for high-speed passenger rail corridors[J]. Transportation Research Part C Emerging Technologies, 2016, 63(2): 126?146.

[2] LIN D, KU Y. Using genetic algorithms to optimize stopping patterns for passenger rail transportation[J]. Computer-aided Civil & Infrastructure Engineering, 2014, 29(4): 264?278.

[3] QI J, YANG L, DI Z, et al. Integrated optimization for train operation zone and stop plan with passenger distributions[J]. Transportation Research Part E Logistics & Transportation Review, 2018, 109: 151?173.

[4] Jens Parbo, Otto A Nielsen, Carlo G Prato. Reducing passengers’ travel time by optimising stopping patterns in a large-scale network: A case-study in the Copenhagen Region[J]. Transportation Research Part A Policy and Practice, 2018, 113: 197?212.

[5] SHANG Pan, LI Ruimin, LIU Zhiyong, et al. Equity- oriented skip-stopping schedule optimization in an oversaturated urban rail transit network[J]. Transportation Research Part C Emerging Technologies, 2018, 89: 321? 343.

[6] NIU H, ZHOU X, GAO R. Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints[J]. Transportation Research Part B, 2015, 76(jun.): 117?135.

[7] 李得偉, 韓寶明, 李曉娟, 等. 基于節(jié)點(diǎn)服務(wù)的高速鐵路列車停站方案優(yōu)化模型[J]. 鐵道學(xué)報(bào), 2013, 35(6): 1?5. LI Dewei, HAN Baoming, LI Xiaojuan, et al. High-speed railway stopping schedule optimization model based on node service[J]. Journal of the China Railway Society, 2013, 35(6): 1?5.

[8] 張小炳, 倪少權(quán), 潘金山. 基于均衡性和可達(dá)性的高速鐵路列車停站方案優(yōu)化[J]. 計(jì)算機(jī)應(yīng)用研究, 2017, 34(7): 1962?1965. ZHANG Xiaobing, NI Shaoquan, PAN Jinshan. Optimization of high speed railway stop schedule plan based on balance and accessibility[J]. Application Research of Computers, 2017, 34(7): 1962?1965.

[9] 牛豐, 戚建國, 秦進(jìn). 基于不確定客流的高速鐵路列車停站方案優(yōu)化方法[J]. 鐵道學(xué)報(bào), 2016, 38(7): 1?7. NIU Feng, QI Jianguo, QIN Jin. Optimization model for train stopping plan on high-speed railway corridor with uncertain passenger demands[J]. Journal of the China Railway Society, 2016, 38(7): 1?7.

[10] 黃志鵬. 基于旅行時(shí)間滿意度的城際列車開行方案[J]. 蘭州交通大學(xué)學(xué)報(bào), 2018, 37(1): 27?32, 40. HUANG Zhipeng. Intercity Passenger Train operation based on travel time satisfaction[J]. Journal of Lanzhou Jiaotong University, 2018, 37(1): 27?32, 40.

[11] 趙杰群, 李夏苗, 茍敏. 基于區(qū)間數(shù)的高鐵列車停站方案優(yōu)化方法[J]. 鐵道科學(xué)與工程學(xué)報(bào), 2017，14(6): 24?30. ZHAO Jiequn, LI Xiamiao, GOU Min. Optimization of high-speed train stopping plan based on interval numbers [J]. Journal of Railway Science and Engineering, 2017, 14(6): 24?30.

[12] 劉璐, 孟令云, 李新毅, 等. 考慮旅客需求的停站方案與列車運(yùn)行圖一體化模型與算法[J]. 鐵道科學(xué)與工程學(xué)報(bào), 2019, 16(2): 518?527. LIU Lu, MENG Lingyun, LI Xinyi, et al. Integrated optimization of stopping pattern and train timetable for passenger demand[J]. Journal of Railway Science and Engineering, 2019, 16(2): 518?527.

[13] 鄧連波, 史峰, 周文梁. 旅客列車停站設(shè)置方案優(yōu)化[J]. 中國鐵道科學(xué), 2009, 30(4): 102?107. DENG Lianbo, SHI Feng, ZHOU Wenliang. Stop schedule plan optimization for passenger train[J]. China Railway Science, 2009, 30(4): 102?107.

[14] 龍品秀, 史峰, 胡心磊, 等. 不同需求日高鐵列車開行方案協(xié)同優(yōu)化方法[J]. 鐵道科學(xué)與工程學(xué)報(bào), 2019, 16(2): 310?318. LONG Pinxiu, SHI Feng, HU Xinlei, et al. The collaborative optimization of multi-day line plannings for high-speed railway[J]. Journal of Railway Science and Engineering, 2019, 16(2): 310?318.

[15] 陳路鋒, 宋瑞, 何世偉, 等. 基于雙層規(guī)劃模型的高速鐵路列車開行方案優(yōu)化研究[J]. 鐵道運(yùn)輸與經(jīng)濟(jì), 2013, 35(6): 18?23. CHEN Lufeng, SONG Rui, HE Shiwei, et al. Study on optimization of high-speed railway train working diagram based on bi-level programming model[J]. Railway Transport and Economy, 2013, 35(6): 18?23.

[16] HUANG Z, NIU H. A bilevel programming model to optimize train operation based on satisfaction for an intercity rail line[J]. Discrete Dynamics in Nature and Society, 2014, 2014(2): 1?7.

[17] Wardrop J G. Some theoretical aspects of road traffic research[C]// Proc Inst Civ Eng, 1952, Part II: 325?378.

A bi-level programming approach of period-preferred train operations for high-speed railways

HUANG Zhipeng1, TIAN Zhiqiang1, SI Xiaoxin2

(1. School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China; 2. Lanzhou Railway Station Operation Depot, China Railway Lanzhou Group Co., Ltd., Lanzhou 730050, China)

There are a few trains running parallelly on a congested high-speed railway corridor at different periods daily. Hence passengers can choose freely among them. Their preference of departing period choice is the main factor determining the distribution of passenger demands. The objective of this paper was to meet, to the maximum extent possible, the passengers’ preference demands of departing periods and to work out reasonable train stopping operations to avoid congestion. Firstly, two vital affecting factors, attractivity and congestion, were analyzed. Meanwhile, the passenger travel impedance function was established, and a bi-level programming model was constructed. The upper integer planning model regarded the minimum operation cost as the goal to decide train stopping operations and its running frequency. The lower model was a user-equilibrium one aimed at distributing passenger flows scheme based on the optimal train stopping operation. Finally, a heuristic algorithm embedded with Frank-Wolfe algorithm was designed based on model characteristics, and a simulation calculation was carried outto verify both the model and the algorithm.

high-speed rail; train stopping operation; bi-level programming model; user equilibrium; heuristic algorithm

10.19713/j.cnki.43?1423/u.T20200562

U293.1

A

1672 ? 7029(2021)04 ? 0861 ? 08

2020?06?19

國家自然科學(xué)基金資助項(xiàng)目(71761023)；甘肅省自然科學(xué)基金資助項(xiàng)目(18JR3RA110)

黃志鵬(1983?)，男，河南長葛人，副教授，博士，從事交通運(yùn)輸規(guī)劃與管理研究；E?mail：huangzp@mail.lzjtu.cn

(編輯 陽麗霞)