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

黃志鵬，田志強，司曉鑫

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

黃志鵬1，田志強1，司曉鑫2

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

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

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

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

1 問題分析

1.1 列車類型和時段劃分

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

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

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

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

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

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

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

2 模型和算法

2.1 數(shù)學模型

2.1.1 符號定義

2.1.2 上層規(guī)劃

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

2.1.3 下層規(guī)劃

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

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

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

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

2.2 算法設計

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

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

3 算例

3.1 參數(shù)設置

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

圖3 列車停站備選方案

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

表1 OD客流需求

3.2 計算結果

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

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

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

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

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

表5 各時段的流量分配結果

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

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

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

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

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

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

4 結論

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

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

3) 本文構建的雙層規(guī)劃模型能夠描述旅客出行決策和高鐵列車開行方案優(yōu)化的動態(tài)博弈過程。 本文只研究了一個開行區(qū)段的高鐵走廊，后續(xù)將研究多個運行區(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é)點服務的高速鐵路列車停站方案優(yōu)化模型[J]. 鐵道學報, 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] 張小炳, 倪少權, 潘金山. 基于均衡性和可達性的高速鐵路列車停站方案優(yōu)化[J]. 計算機應用研究, 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] 牛豐, 戚建國, 秦進. 基于不確定客流的高速鐵路列車停站方案優(yōu)化方法[J]. 鐵道學報, 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] 黃志鵬. 基于旅行時間滿意度的城際列車開行方案[J]. 蘭州交通大學學報, 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]. 鐵道科學與工程學報, 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] 劉璐, 孟令云, 李新毅, 等. 考慮旅客需求的停站方案與列車運行圖一體化模型與算法[J]. 鐵道科學與工程學報, 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] 鄧連波, 史峰, 周文梁. 旅客列車停站設置方案優(yōu)化[J]. 中國鐵道科學, 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]. 鐵道科學與工程學報, 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]. 鐵道運輸與經濟, 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

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

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

(編輯 陽麗霞)