第18卷第4期铁道科学与工程学报Volume18Number4 2021年4月Journal of Railway Science and Engineering April2021 DOI:10.19713/jki.43−1423/u.T20200562
双层规划方法
黄志鹏1，田志强1，司晓鑫2
(1.兰州交通大学交通运输学院，甘肃兰州730070；
2.中国铁路兰州局集团有限公司兰州车务段，甘肃兰州730050)
摘要：在一条拥挤的高速铁路客运走廊上，通常有多列平行车次的列车在不同的时段运行，旅客在出行时具有较大的选择空间。旅客对出行时段的偏好是影响旅客需求分布的最重要因素，最大限度地满足旅客对出行时间的偏好需求，并合理制定列车开行方案引导旅客合理出行以避免出行拥挤是本文的研究目的。首先分析影响旅客出行时段偏好的2个重要因素，吸引度与拥挤度。据此构建旅客出行阻抗函数，并建立一个双层规划模型，上层规划是以运营成本最小为目标的整数规划模型，用于确定列车停站方案和开行频率；下层规划是一个用户平衡模型，用于计算客流在优化的停站方案上基于用户均衡的分配结果。最后，根据模型特点设计了嵌套Frank-Wolfe算法的启发式算法，并通过仿真计算对模型和算法的可 行性进行了验证和分析。
关键词：高速铁路；列车开行方案；双层规划；用户平衡；启发式算法
中图分类号：U293.1文献标志码：A开放科学(资源服务)标识码(OSID)
文章编号：1672−7029(2021)04−0861−08
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,Lanzhou730070,China;
2.Lanzhou Railway Station Operation Depot,China Railway Lanzhou Group Co.,Ltd.,Lanzhou730050,China)
Abstract: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 congest
ion.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
收稿日期：2020−06−19
基金项目：国家自然科学基金资助项目(71761023)；甘肃省自然科学基金资助项目(18JR3RA110)
通信作者：黄志鹏(1983−)，男，河南长葛人，副教授，博士，从事交通运输规划与管理研究；E−mail：******************
铁道科学与工程学报2021年4月862
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.
Key words:high-speed rail;train stopping operation;bi-level programming model;user equilibrium;heur
istic algorithm
旅客选择高铁出行不仅仅是对传统铁路客运核心产品——“位移”的需求，同时对旅客出行品质提出了更高的要求，而出行时段的选择则是旅客最关心的需求之一。旅客会根据自身的出行习惯、出行目的和出行经验来选择最理想的出行时段。在高铁全天运营的各个时段上，旅客出行需求具有不均衡特征，表现出明显的时段偏好性。另一方面，铁路部门在不同时段组织的各种停站方案的列车也是影响旅客出行选择的关键因素。因此，基于旅客对出行时段的偏好，优化各个出行时段列车的停站方案，使旅客出行需求与列车停站方案具有良好的耦合关系是本研究的主要目的。国外学者一般是将旅客列车停站方案作为列车时刻表(Train Timetable Problem,TTP)优化问题的一个重要部分进行研究。其中大部分是站在运输效益最大化角度进行的研究。YUE等[1−2]用0-1决策变量表示列车在中间站是否停站，构建了一个以运输收益最大为目标的TTP模型求解了大规模网络条件下高速铁路列车停站优化问题。QI等[3]以列车空座位运行距离和所有列车总停站数最小为目标建立了一个多目标线性规划模型优化列车停站方案。近十年来，综合考虑旅客的出行质量，将旅客出行时间或出行费用优化纳入TTP优化模型的研究较多。Jens等[4]建立了一个双层规划模型优化旅客列车停站问题。SHANG等[5]通过构造多商品流模型，优化客流的分配和列车的停站方案。考虑到列车停站次数对运输效益的影响，部分学者将列车停站次数作为优化目标或者约束条件。NIU等[6]以旅客总等待时间最小为目标研究了时变条件下一条高铁走廊的列车时刻表优化问题。李得伟等[7]以总停站次数最少为目标，将节点服务频率
、站间服务可达性、单个列车停站次数等作为主要约束条件，构建列车停站方案的非线性规划模型。张小炳等[8−10]从列车停站数量的均衡性和区间的可达性出发，建立高速铁路列车停站方案的非线性多目标优化模型。赵杰等[11]以列车停站费用最小化为优化目标，建立了机会约束模型优化了列车停站方案问题。刘璐等[12]基于旅客需求的时变特征，建立了时空状态三维出行网络，协同优化了列车运行图和列车停站方案问题。考虑到旅客出行需求与运输企业效益的博弈关系，一些学者试图建立双层规划模型对该问题进行数学描述，并取得了一定的成果。邓连波等[13−15]通过建立双层规划模型优化列车停站方案。模型的上层为旅客广义出行费用最小和列车停靠站数量限制，下层为多类用户均衡客流分配模型。本文拟分析影响旅客出行时段偏好性的主要因素，建立一个双层规划模型来优化一条高铁线路上不同时段各种停站方案列车的开行数量，并依据用户平衡规则将客流分配在各个出行时段上。论文的主要创新点：首先，将旅客的出行时段偏好与列车停站方案结合起来协同优化，并将多OD客流需求分配在各个出行时段上。其次，不同于以往周期化的停站方案优化[16]，本文制定的停站方案按照出行时段分别优化停站方案。
1问题分析
1.1列车类型和时段划分
在一条高铁线路上，令S为车站集合，{1,2,,}
S m
=L，i,j用来标识车站，,i j S∈；列车按照停站方案来划分类型，即每一类列车对应一种停站序列，令H为列车类型集合，用h标记任一类列车，h H
∈；令T为出发时段集合，用来标识出发时段。
1.2旅客出发时段偏好
1.2.1出发时段的吸引度
旅客对各个出发时段的偏好性，表现为不同时段对旅客的吸引度有很大差异。这种差异是客观存在的，并受到多种客观因素的影响。如通勤客流占全部客流比重较大的车站，对旅客吸引度最高的时
第4期黄志鹏，等：时段偏好的高铁开行方案的双层规划方法863
段为早晚高峰时段；又如旅客总是期望在城市公交方便的白天时段出行等等，均为影响旅客选择出行时段的客观因素。
图1
出发时段吸引度的三角模糊数分布
Fig .1Triangular fuzzy number distribution of departing
period attractivity
采用一个模糊数()is C t 来量化第s 类旅客在时段t 从车站i 出发的偏好程度，即出发时段的吸引度。模糊数()is C t 可由()
,,E H L is is is T T T 决定。其中，E is T 和L
is T 分别表示第s 类旅客能够接受的最早和最晚
的出发时段；H
is T 表示第s 类旅客最期望出发的时
段。旅客出行时间偏好的三角模糊数分布如图1所示，其隶属度函数如式(1)所示。0
(),0
E is E E H
故宫门票价格is is is H E is is
is L H
L
is is is L H
is is
L
is t T t T T t T T T C t i s T t T t T T T t T ⎧⎪-⎪<⎪-⎪=∀⎨
-⎪<⎪-⎪⎪>⎩≤≤≤(1)
()is C t 的取值范围为[0,1]。
本文以第s 类别旅客占车站i 所有旅客的比例ηis 为权重，通过式(2)可得到车站i 旅客对出发时段t 的总体吸引度()i C t 。
()()
i is is s
C t C t i η=⋅∀∑(2)
1.2.2出发时段的拥挤度
旅客对各个出行时段的偏好性，还表现为旅客对不同时段拥挤度的选择。当某个出行时段的吸引度较大时，大量的旅客均期望在这个时段出行。这时，这个时段的拥挤度也会大大提高。如旅客选择在吸引度较大的时段出行时，有可能因时段需求旺盛而未能购得车票；或者旅客为了确保能够在这个时段出行，必须提前很久购票，使得旅客的出行灵活性降低，带来很大的不便。
根据客流调查的数据分析，随着客流量t i x 与车
站服务能力t i n 比值的增大，拥挤度()t i i D x 也随之增
大，并符合幂函数的分布特征。令出发时段t 的拥挤度在无流量加载时为0i d ，当有流量加载时，可用式(3)表示，其中α和β是通过数据拟合标定的参数。
0()1t t i i i i t i x
D x d n βα⎡⎤⎛⎫⎢⎥
=⋅+⋅ ⎪⎢⎥⎝⎭⎣⎦
(3)
1.2.3
出发时段偏好的量化
综上所述，旅客会根据出行经验，在时段吸引
度和拥挤度之间进行博弈。博弈的结果是部分旅客偏好于时段吸引度，容忍了拥挤度；部分旅客对拥挤度敏感，选择在吸引度较低的时段出行。最终形成一个UE 平衡状态[17]，即旅客选择出行的任意时段，其出行阻抗都是一样的。本文综合考虑了出发时段的吸引度和拥挤度，构造了式(4)来量化旅客在出发时段t 出行的偏好程度(出行阻抗()i f t )。
()()()
t i i i i i f t D x C t θ=-⋅(4)
其中，θi 是调节系数，表示车站i 旅客对出发时段吸引度和拥挤度的敏感程度，如通勤客流较大车站，
旅客对时段吸引度的敏感程度远高于时段拥挤度。时段出行阻抗()i f t 与()t i i D x 成正比，与()i C t 成反比。当时段t 的吸引度()i C t 较大时，期望该时段出行的旅客较多，会导致该时段流量t i x 的增大，进而使得该时段拥挤度()t i i D x 的增大。而旅客选择在
出行吸引度较小的时段t '出行时，该时段的拥挤度()t i i D x '也较小。这样，旅客在拥挤度和吸引度间不
断的博弈选择，最终达到任意时段的出行阻抗()i f t 均相等的平衡状态。
2模型和算法
2.1数学模型2.1.1
符号定义
1)参数：ij q 为车站i j →的客流需求量；t i C 为车站i 在第t 时段无流量加载时的时段阻抗；t i N 为在第t 时段能够分配给车站i 的最大客票数；R h 为第h 种停站方案列车的开行成本；F t 为始发站在第t 时段的发车能力；h i θ为第h 种停站方案的列车分配给车站i 的票额比例；Y 为列车定员数。
铁道科学与工程学报
2021年4月
8642)中间变量：t
ij g 为车站i j →的客流被分配到
第t 个时段的客流量；h t ε为0～1变量，代表第t 时段第h 种停站方案列车是否开行。
3)决策变量：下层规划中，t i x 表示第t 时段在车站i 上车的客流量；上层规划中，h t u 表示第t 时段按照第h 种停站方案开行的列车数量。2.1.2
上层规划
上层规划的目标是铁路运输企业的运营成本最小。不同停站方案的列车由于能耗和占用沿途车站设备的因素，其运营成本是不相同的。
min h
h t h
t
去泰国需要护照吗
E R u =⋅∑∑(
h t t
h H
u F t
∈∀∑≤(6)
h h t
t i i h H
Y u x t
θ∈⋅⋅∀∑≥(7)0h t u ≥且为整数
(8)
上层规划的目标如式(5)所示。式(6)表示第t 时段开行的各种停站方案的列车数量不应大于该时段的发车能力；式(7)表示各个时段列车提供的座位数应大于分配在该时段的客流数量。其中，h t Y u ⋅表
示第h 类停站方案列车的全部坐席数量，h h t i Y u θ⋅⋅表示第h 类列车提供给车站i 的客票数。t i x 为下层规划的决策变量，表示当前方案下的流量分配结果，在上层规划中是下层给上层提供的参数，并非变量；式(8)为非负及整数约束。2.1.3
下层规划
下层规划是一个符合Wardrop 第一原理的用户平衡配流模型。
min ()d t i x t i S t T
Z f a a
∈∈=∑∑⎰
(
,t
ij
ij
t T
g q i j
∈=∀∑三亚景点图片大全图片
(10)0
,,1
t ij g t i m j ∀≠≠≥(11),t t i ij
j S
x g i t
∈=∀∑(12)
式(9)为目标函数，其本身没有物理意义，是平衡配流基于“Beckman 变换”后的形式。式(10)满足了客流守恒条件，即客流需求被分配到了阻抗最
小的各个时段；式(11)表示车站i j →的客流被分配在第t 时段流量为正值；式(12)表示任意第t 时段车站i 出发的客流量由多个到达站j 的客流构成。2.1.4
上、下层的联系
如图2所示，上层规划决策的列车开行数量h t u 可以得到列车服务能力t i n ，进而影响出行阻抗()i f ⋅。
下层模型根据阻抗函数可以得到流量分配结果t
ij g ，进而得到各时段的累加流量t i x ，而t i x 作为
上层模型约束条件的重要参数重新影响上层决策h t u 。
图2
上下层规划的数据交换
Fig.2Data exchange between upper and lower planning
这样，上层规划的列车开行方案和下层规划的客流分配结果之间，会循环反复的调整，直至达到满意
解为止。2.2
算法设计
论文所建模型是一个双层规划问题，它被公认为是求解极其困难的NP 完全问题。本文设计了嵌套Frank-Wolfe 方法的启发式算法进行求解。算法流程如下。
Step 1初始化：随机生成规模为popsize 的初始停站方案(h t ε)的可行解种，其中每条染体共有m 个基因片段，表示m 个时段；每个基因片段又有n 个基因位置，采用0-1编码，表示相应类别停站方案的列车是否开行。置上层规划最优目标E *=0；置最优停站方案集Ω*为零向量；迭代次数b =0。Step 2检查和判断：为了保证任意OD 对i j →的旅客均有可选择乘坐的列车出行，需要检查初始种中各条染体是否能够满足所有OD 旅客的出行需求。依次检查各染体上每个基因片段(时段t )上所有非“0”的基因位置所对应的列车停站方案是否在车站i 和j 均停车，如果满足，将时段t 纳入i j →的客流出行时段备选集，直至所有OD 对均有相应
第4期黄志鹏，等：时段偏好的高铁开行方案的双层规划方法865
的出行时段备选集，转下一步；如果不满足，即当前染体不能满足所有OD 客流需求，返回Step 1。Step 3用户平衡配流：对于当前开行方案Ω(i)，用Frank-Wolfe 算法求解下层规划，得到符合Wardrop 第一准则的t i x ，并记录所有可行解对应的平衡配流结果和阻抗值。
Step 4整数编码：对Step 1产生的0～1编码染体中“1”的基因位置随机赋一个整数值，并满足式(6)和式(7)的约束。
Step 5遗传操作：对列车开行数量(h t u )的初始种进行选择、交叉和变异操作，搜寻当前种中适应度最高的可行解Ω(b)，并更新最优停站方案集
Ω=Ω*(b)；迭代次数1b b =+。
Step 6终止检验：如果迭代次数b 等于迭代上限
Ge ，输出优化解Ω*，否则转Step 5。
3算例
3.1
参数设置
本文以兰州西—西安北高铁为例。为了方便表示，将兰州西站编号为1，按照列车上行方向依次编号，其中兰州西、西安北为始发、终到车站，必停车；另外在4个区域中心所在的定西北站、天水南
站、宝鸡南站、咸阳秦都站必停车；铁路运输部门将列车在其他车站的停车次数设置为0～2次，则全部备选停站方案共11种，如图3所示。
图3列车停站备选方案Fig.3Alternative plans of train stop
该高铁上所有起讫点(OD)间的客流需求如表1所示。本文以1h 为一个时段，将高铁全天的发车时间(6:00～22:00)划分为16个时段，并将6:00～7:00标记为时段1，按照时间顺序依次编号2,3,…,16。各出发时段的吸引度，如表2所示。其中，距离始发站较远的车站，每日首列车到达该站时的时段会相应延迟，如车站3到9，将其吸引度设置为0。
其他相关参数设置如下：不同停站方案列车的开行成本如表3所示；将相同车站在不同时段的服务能力设置为相同，各出发站的服务能力如表4所
示；将相同车站的初始拥挤度设置为相同，0
1i d =；
流花湖公园景点介绍相同车站的调节系数也设置为相同，0.5i θ=；列车定员Y =1440，调节系数α=0.15，β=4；各时段的最大发车能力F t 均为12列。种规模popsize=200，交叉概率P c =0.95，变异概率P m =0.05，最大停滞迭代次数为10，最大迭代次数为100代。
表1OD 客流需求
Fig.1OD passenger flow demands
千人上车站下车站
合计
2345678910
16 1.83
9.6
9成人自考报名入口
3
2.4
3
10.248
2—0.80.7 1.20.80.30.30.4 1.5
6
3——0.20.30.20.10.10.20.4 1.5
4———0.40.20.10.10.30.4 1.55————20.20.30.57106—————1 1.5 1.5487——————0.50.5128———————0.52
2.5
9
—
—
—
—
—
—
—
—
0.50.5
3.2计算结果
莫干山民宿价格通过matlab2014a 软件编程，对该算例进行求
解，下层规划计算结果如表5所示。各上车站的
