基于不确定旅客需求的高速铁路鲁棒列车开行方案研究

张春田，戚建国，杨立兴，高原，高自友

(1.北京交通大学，a.交通运输学院，b.轨道交通控制与安全国家重点实验室，北京100044；2.北京理工大学，管理与经济学院，北京100081)

0 引言

铁路运输是交通运输的重要组成部分，与公路、水路、航空、管道等运输方式形成了综合运输体系。高速铁路因其载客量大、速度快、准时和安全等特点而广受欢迎。近年来，随着旅客出行需求的增加，铁路线网规模的扩大，如何充分利用铁路资源，编制基于旅客实际出行需求的高速铁路列车开行方案，为旅客提供高质量的运输服务已成为当前亟待解决的问题。

为了编制更加符合旅客出行特点的列车开行方案，部分学者在列车开行方案编制过程中充分考虑旅客需求特点，形成一系列的研究成果[1-3]。文献[1]构建了该问题的多目标双层规划模型，以同时最大化列车开行收益和旅客方便度。文献[2]在考虑旅客出行时变需求的基础上，构建了同时考虑列车运行时间与旅客出行时间的高速铁路列车开行方案优化模型。文献[3]以运营商利润和旅客出行需求满意度最大化为目标，构建了考虑需求、服务和资源的整合模型，并设计了拉格朗日松弛算法求解该模型。上述文献虽考虑了旅客的出行特点，但是以事先已知的计划旅客需求制定开行方案，并未充分考虑旅客需求不确定性的影响。事实上，由于旅客出行目的不同、天气变化等诸多因素的影响，旅客需求普遍存在不确定性，忽略旅客不确定性势必会导致某些情形下旅客需求得不到满足或者列车出现较大虚糜，因而降低优化方案的适用性。基于此，文献[4]考虑客流需求波动，建立了基于鲁棒性的开行方案优化模型，并设计了拉格朗日松弛算法求解该问题。文献[5]研究客运专线客流量不确定性的影响，基于不确定区间可调节鲁棒优化理论，构建了鲁棒性与经济性相协调的开行方案鲁棒优化模型。与使用随机变量、模糊变量等处理客流不确定性的方式相比，鲁棒优化不需要给出具体的不确定参数分布模型和不确定参数的模糊隶属函数，并且能取到较好的效果。在一般的鲁棒优化方法中，通常要求不确定参数在不确定集合内取任意元素时都严格保证约束成立，容易导致所得方案过于保守。本文拟采用文献[6]提出的轻鲁棒技术(Light Robustness，LR)来处理旅客需求的不确定性，其是一种可在既有模型基础上为所得方案加入一定鲁棒性保护的有效技术。轻鲁棒技术通过对与决策变量相关的不确定因素加入一定的期望保护水平来获得鲁棒性较强的决策方案，其允许对鲁棒性保护水平约束进行一定的松弛，因而可以更好地兼顾旅客与运营公司两方需求。此外，轻鲁棒技术还可在确保鲁棒优化模型复杂度增加较小的同时获得鲁棒性更好的开行方案。

在列车开行方案优化问题中，为了简化问题，诸多学者[7-9]基于“备选集”思想来优化列车开行方案。文献[7]指出“备选集”是所有可能开行列车的一个合理全集，列车开行方案优化时将从备选集中选取部分列车组合成最终方案。文献[8]采用备选集的思想解决了临客列车开行方案优化问题。文献[9]基于给定候选列车集构建弹性旅客出行网络，从而解决面向弹性需求的列车开行方案优化问题。上述文献为解决列车开行方案优化问题奠定了良好的理论基础，但给定备选集质量的优劣直接影响到后续列车开行方案的质量。与之不同的是，文献[1]和文献[2]分别通过决策某种类型列车是否发车以及列车发车频率来确定最终的列车开行方案，这种方式可免除生成备选集的程序，但大多数文献仍是给定每一列车始发和终到车站径路，来进一步确定列车停站与开行频率。然而，若提前预设的列车始发和终到车站径路不合理，可能会造成无可行解，或者列车资源浪费的现象发生。为了在满足旅客需求的前提下尽可能地节省铁路运营公司总运营成本，本文采用无需事先给出备选集的列车开行方案优化思想，并利用生成列车经过站点的方式确定列车的具体径路。

综上所述，本文拟在既有研究的基础上，考虑旅客需求的不确定性，结合轻鲁棒技术和线性化技术，以极小化铁路运营公司总运营成本为目标，构建不确定旅客需求下高速铁路鲁棒整数线性规划模型，生成鲁棒的列车开行方案，在确定性旅客需求得到满足的前提下，进一步为额外的波动性旅客需求提供一定水平的运输服务。

1 问题描述

列车开行方案的编制是基于旅客需求确定列车起讫点OD、经由线路、停站、服务频率、列车等级、编组等要素。图1 为一个包含3 座车站的高速铁路线路示意图，并在线路图下方给出了所有可能的列车运行径路，其中，d1和d2为铁路区段的距离，k1、k2、k3和k4为不同类型的列车。

图1铁路网络中，可开行4种不同类型的列车，分别为不同OD类型旅客提供服务。显然，不同的列车开行组合可为旅客提供不同的运输服务，需要花费不同的运营成本。如何在尽可能满足旅客需求的前提下，生成运营成本较小的列车开行组合至关重要。在上述铁路网络中，给出包含3 种OD 类型的旅客需求矩阵为

图1 铁路线路以及对应列车运行的径路Fig.1 A railway corridor and its possible lines set

假设列车容量为600人·列-1，开行每列列车固定运营成本为f万元，可变成本为v万元·km-1。图2给出3种不同的可行列车开行方案。

图2 示例对应的不同开行方案及其运营成本Fig.2 An illustration of different train operation plans and their operating costs

方案1仅考虑满足旅客需求，列车出现较大虚糜，导致需要最高的列车运营成本。方案2通过合理设置列车停站策略，最大限度地利用列车容量，但仍需要开行3列列车。考虑到开行1列列车需要较高的固定成本，方案3 给出进一步的优化策略，只需开行2列列车便可满足总的旅客需求。显然，方案3是最优的选择。值得说明的是，如若在给定备选集合中只包含k1、k2和k4，而未包含k3列车，则基于备选集的列车开行方案将无法得到该示例中最优方案。基于以上分析，本文将研究如何在尽可能满足旅客需求的基础上，考虑旅客需求的不确定性，生成合理的列车开行组合，以极小化铁路运营公司的总运营成本。

2 模型构建

2.1 确定性优化模型

由于本文拟采用轻鲁棒技术来提高列车开行方案的鲁棒性，而鲁棒优化模型是以确定性旅客需求的列车开行方案优化模型为基础，故先介绍确定性优化模型。

2.1.1 模型假设

为了更好地描述该模型，给出以下假设：

(1)假设不考虑列车长度，两车站之间的距离假定为列车运行距离。

(2)假定旅客中间不进行换乘，即假定旅客只能乘坐在其始发站和终到站同时停靠的列车。

(3)假定具有相同OD 的旅客需求由于受列车运力限制，可选择不同的列车出行。

2.1.2 模型的相关符号

设候选列车集合为K，以k为索引；列车站点集合为N，以i、i′和j为索引；车站对应区段集合为S，以s为索引；列车k定员数量为Ck；车站i到j的确定性旅客需求为Dij；区段s的距离为ds；区段s所需通过的最少列车数为Ps；最大列车停站总数量X；开行1 列列车的固定费用为fk；列车单位里程运行成本为vk。

设yk为0-1 决策变量，若列车k被选择，yk=1；若不被选择，yk=0。设xk,i为0-1决策变量，若列车k在车站i停车，xk,i=1；若不停车，xk,i=0。设Zk,s为0-1决策变量，若列车k通过区段s，Zk,s=1；若不通过，则Zk,s=0。

设rk,ij为预计分配到列车k上由车站i出发到达车站j的旅客人数，rk,ij≥0。

2.1.3 模型构建

基于上述参数和决策变量，构建基于确定性旅客需求的高速铁路列车开行方案整数线性规划模型为

目标函数式(1)极小化铁路运营公司总运营成本，其中第1 项和第2 项分别是列车开行固定成本和变动成本，O代表确定性优化模型的目标函数。式(2)保证列车上的旅客数量不超过每列列车的载客量。式(3)保证确定性情况下的旅客需求可被满足。式(4)和式(5)确保旅客只能乘坐在其始发站和终到站同时停靠的列车。式(6)和式(7)确保只有当列车k被选择，该列车才有可能在车站i停靠和通过区段s。式(8)和式(9)通过借助0-1 决策变量xk,i，来确保只有当列车k通过区段s，才有Zk,s=1成立。通过分析两个决策变量之间的关系，式(8)可等价转换为

通过引入两个额外的0-1辅助变量αk,s和βk,s，式(9)可等价转换为

其中，αk,s≥xk,1,αk,s≥xk,2,…,αk,s≥xk,s且βk,s≥xk,s+1,βk,i≥xk,s+2,…,βk,s≥xk,N，当且仅当αk,s和βk,s同时取1，Zk,s=1才成立。

式(10)和式(11)为结合实际运营需求和运营公司决策偏好对区段通过列车数量以及总列车停站数量的限制。从理论层面来讲，式(10)和式(11)可合理缩小解的搜索空间，加快模型求解的速度。从实际应用层面来讲，在结合实际需求获得区间最少通过列车数量以及列车最多停站数量的基础上，式(10)和式(11)的构建可将运营公司决策偏好考虑在内，是对模型进行的一定扩展。在实际中，上述两个参数可根据旅客需求计算得出，也可以通过铁路运营公司的实际需求或者专家经验给出。

通过对上述模型进行线性化，可以得到确定性列车开行方案整数线性规划模型，记为NM(Nominal Model)。与以往研究有所不同，本文未事先给出线路备选集，而是由模型自动搜索列车开行方案。

2.2 基于旅客需求的鲁棒优化模型

为构建鲁棒优化模型，增加符号Δij表示车站i到车站j的额外旅客需求服务保护水平。通常情况下，该值与额外波动性旅客需求分布和决策者偏好相关(如95%的额外波动旅客需求需要得到满足)，也可被视为车站i与车站j之间的期望鲁棒性保护水平。相应的，引入松弛变量λij来保证所构建鲁棒优化模型的可行性，其中，λij代表车站i与j之间由于列车容量限制而未被满足的期望鲁棒性保护水平。构建基于旅客需求的鲁棒优化模型为

s.t.式(2)、式(4)～式(7)和式(10)～式(16)

目标函数式(17)为极小化所有未被满足的额外旅客需求，用R来表示。式(18)和式(19)替代了NM模型中的式(3)，用来表示列车所能满足的旅客需求。式(18)首先保证满足确定性旅客需求，此外还允许利用冗余的列车容量服务额外波动旅客需求。式(19)表示额外的旅客需求被满足的情况。具体来讲，当目标松弛变量λij之和取0 时，表明所有额外旅客需求均能被满足；当松弛变量λij与Δij相等时，表明所有额外旅客需求均未被满足。第1种极端情况的出现是由于未考虑因鲁棒性加入而导致的运营成本增加，这显然有悖于运营公司的初衷。因此，在求解NM模型得出确定性方案最优目标O*的基础上，利用约束条件式(20)，以α⋅O*(α≥1)作为运营公司能够承担的最大成本支出，通过调节参数α的值对鲁棒方案目标恶化程度进行控制。同样的，式(21)可对最大列车数量进行限制，其中，K∗为确定性优化模型求解出的最优列车数量，β为控制参数，β≥1。

综上所述，式(2)、式(4)～式(7)以及式(10)～式(22)即为基于不确定旅客需求的鲁棒列车开行方案优化模型，记为DRM(Demand based Robust Model)。该模型首先确保了确定性旅客需求得到满足，并通过引入参数Δij为额外的波动性旅客需求提供必要的运输服务保障，以确保整个铁路系统的服务质量。

3 算例分析

为验证本文所构建鲁棒优化模型的有效性，以图3武广高铁为背景，设计数值实验。

图3 武汉-广州高速铁路走廊图示Fig.3 Map of Wuhan-Guangzhou high-speed railway corridor

3.1 模型输入数据

在实际运营中，一般较小的车站只作为中间车站来提供服务，较大的关键车站才允许被选择作为列车的始发或终到车站。为使模型具有一般适用性，本文在原有模型的基础上进一步添加限定关键车站才可作为始发或者终到站的相关约束。具体地，假定可以作为始发站和终到站的关键车站集合分别为Nd={1,2}={武汉,长沙南} 和Na={1,2}={郴州西,广州南}。此外，引入集合D(i)表示集合Nd到集合N的映射(i∈Nd)，则有D(1)=1以及D(2)=6 成立。同样地，引入集合A(i)表示集合Na到集合N的映射(i∈Na)，则有A(1)=11 以及A(2)=16 成立。为使模型具有更好的适用性，需在原有模型的基础上进一步添加如下约束：当，有与成立；当，有与成立；否则，有与成立。图4 为每座车站需要发送的总旅客需求示例，其中括号内第1 个数值和第2 个数值分别代表确定性旅客需求数量和额外的旅客需求数量，单位为人。根据生成的旅客需求OD 矩阵，提前设定确定性优化模型中最大列车停站总数量X=380，鲁棒优化模型中最大列车停站总数量X=422，区段s需通过的最少列车数Ps={19,23,24,27,27,31,31,31,31,31,28,24,24,23,22}。此外，假定候选列车总数为35 列，列车容量为600 人·列-1，列车固定运营成本为10 万元，可变成本为0.01 万元·km-1。值得说明的是，由于数据保护需要，本文实验所采用数据根据经验和实际规律给出。

图4 每座车站需发送的旅客需求Fig.4 Number of passengers to be sent at each station

3.2 开行方案计算分析

通过将模型转化为整数线性规划模型，在CPU为i5-8265U、内存为8 G 的电脑中，使用MATLAB调用GUROBI优化软件对所构建的模型进行求解。

在本文给出的参数设置条件下，为对比分析确定性优化模型和鲁棒优化模型，首先基于确定性旅客需求，求解NM 模型，可获得对应的最优列车开行方案。其中，最优目标O*=615.600，K∗=31。进一步，将确定性旅客需求和额外的旅客需求进行加和，求解NM 模型得到最大使用列车数量为34列，运营成本为677.670万元。

在确定性列车开行方案优化模型已求解的基础上，令β⋅K∗=34 对α进行灵敏度分析。不同的α值对应于不同的额外旅客需求满足程度。本文将α设为1.00，1.01，1.02，…，1.09。DRM模型的求解结果如表1所示，其中，G1、G2、G3 和G4 分别代表武汉开往广州南、武汉开往郴州西、长沙南开往广州南、长沙南开往郴州西的列车。表1 中第1 行与最后一行为上述NM 模型对应于满足确定性旅客需求与可能的最大旅客需求情况下所得到的解。

表1 鲁棒优化模型计算结果Table 1 Computational results of robust model

随着参数α取值的不断增加，未被满足的额外旅客需求R*逐渐减小。值得注意的是，当α取值为1 时，即在保证NM 模型求解所得运营成本不变的情况下，可以进一步分析列车是否还有冗余容量运输一定的额外旅客需求。通过表1 中第2 行(α=1)的结果可看出，在保证运营成本为615.600不变的情况下，还可进一步多运输1625 名旅客。具体地，给出α=1时求解鲁棒优化模型得到的开行方案，如图5所示。

图5 鲁棒优化模型α=1时列车开行方案示意图Fig.5 An illustration of train operation plan based on robust model with α=1

事实上，在保证运营成本不变的情况下，鲁棒优化模型通过改变列车的停站方案可进一步服务于部分除确定性旅客需求之外的额外旅客需求，这表明鲁棒优化模型获得的开行方案具有强的抵抗旅客需求随机波动干扰的能力。此外，由表1还可看出，得到的开行方案中大多数列车为由武汉开往广州南的长距离列车，这也与实际运营情况相符。值得注意的是，当α取1.04 与1.05 时，未被满足的旅客数量相同，并且所开行列车数量相同，因此在本文给出的参数设置下认为α取1.04优于1.05，同样的道理适用于α取1.07 和1.08 的情况。由此可见，通过合理选择α值可在满足相同旅客需求的条件下，最大限度节省运营成本。清晰起见，图6 给出每种α取值下未被满足的旅客数量，其中，未被满足的旅客需求同样以每座车站需发送的旅客需求为基础给出。由图6 可直观的看出，随着参数α取值的不断增大，未被满足的额外旅客需求逐渐减少，直至减小为零。这表明，如果铁路运营公司愿意承担更大的运营成本，便可更好地应对旅客需求的不确定性。

图6 不同参数α 值下未被满足的旅客数量Fig.6 Number of unsatisfied passenger demand under different values of parameter α

3.3 附加对比实验

为了更好地说明本文提出方法的有效性，进一步增加两部分附加对比数值实验。具体地，第1部分设计使用既有鲁棒优化方法求解列车开行方案的一系列数值实验；第2部分设计提前给定列车始发和终到车站径路的一系列数值实验。

3.3.1 附加实验1:鲁棒对等模型

同样地，仍然在确定性优化模型NM 的基础上，首先对旅客需求进行不确定性处理，通过参考文献[4,10]构建Bertsimas和Sim鲁棒对等模型。为构建鲁棒优化模型，使用表示旅客需求的不确定扰动项，因而NM模型中的式(3)可以替换为

式中：zij，pij为对偶变量；Γij为取值为[0,1]的参数，表示保守程度。因而，式(1)～式(2)、式(4)～式(7)、式(10)～式(16)、式(18)以及式(24)～式(27)即为列车开行方案的鲁棒对等模型，记为RCM(Robust Counterpart Model)。

为了与本文提出的DRM 模型进行对比，取多组不同的参数Γij值来求解RCM 模型，结果如表2所示。表2 中Γ为每一个约束中Γij的取值，其中第1组Γ=0.00 表示所有OD对均只存在名义值扰动，此时约束变为名义问题；第2组表示每个OD对的波动值均在[0.00,0.50]之间随机选取；最后一组表示所有的旅客需求都应当被满足。此外，O*和R分别表示求解RCM 模型的最优目标值(运营成本)和未被满足的旅客数量。

表2 RCM模型计算结果Table 2 Computational results of robust counterpart model

由表2 可知，RCM 模型亦能在较短的时间内获得鲁棒的列车开行方案。值得注意的是，在求解RCM 模型时，参数Γij的取值具有很大的随机性和主观性，且对结果有较大影响。比较表1 和表2 可知，在相同的运营成本下，基于轻鲁棒技术构建的模型得到未被满足旅客数量(R)更少，这表明在运营公司承担相同的运营成本时，本文构建的DRM 模型可以得到更鲁棒的开行方案。此外，由于RCM 模型要求在不确定集合下所有约束条件均应当被满足，在某些极端情况下，可能会导致某些列车仅仅运输极少数旅客，造成列车存在较大的虚糜。

3.3.2 附加实验2:给定每一列列车的始发和终到车站

现有关于列车开行方案的研究大多预先给定每一列列车的始发和终到站，而本文只给定线路可能的起始和终到车站，由模型确定每一列列车的具体起始和终到车站。为了对本文设计方法和现有方法的区别进行分析，基于给定每一列列车的始发和终到站设计了一系列数值实验。同样地，考虑最大使用列车数量为34列，给定不同的列车(G1，G2，G3和G4)开行组合。为了更好地进行对比，假定未被满足的旅客数量不能超过1100 人；若对运营成本进行限制，则假定成本不可超过646.380(α⋅O*=1.05⋅O*=646.380)。值得注意的是，由于提前给定列车的始发和终到站，往往不容易找到可行解，故设计了限制总运营成本和不限制总运营成本的两类数值实验。相应的计算结果如表3所示。

表3 预先给定始发和终到车站的计算结果Table 3 Computational results obtained by setting candidate origin and destination stations

表3 中第1 列代表不同列车的开行组合，其中[24,4,4,2]表示G1，G2，G3 和G4 类型的列车分别有24，4，4和2列。显然地，第2组开行列车组合只可以在不限制总运营成本的前提下找到可行解；然而，第1组列车开行组合在不限制总运营成本的前提下也无法寻找到可行解。此外，通过对比表1和表3 可知，在限制总运营成本的前提下，当给定的列车开行集合包含了最优列车组合时，预先给定每一列列车的始发和终到站的设置情况也可以寻找到最优解，但是在实际运营中，最优列车组合往往不容易预先判别。综上所述，若提前预设的列车组合不合理，可能造成无法找到可行解(例如第1 组)或者列车资源浪费(例如最后一组)的现象。因此，完全由模型搜索列车始发和终到站的研究具有更大的优势。值得说明的是，本文所构建模型是更为一般化的模型，可通过给定部分决策变量的值来确定部分列车的具体径路以满足实际运营中的特殊需求。

4 结论

本文针对现实中旅客需求的不确定性，建立不确定旅客需求下高速铁路鲁棒列车开行方案优化模型。通过案例验证得到如下结论：

(1)通过借助线性化技术，使用商业优化软件求解NM 和DRM 模型，可分别获得该两类模型下列车开行方案。分析案例发现，在保证运营成本不变的情况下，鲁棒优化模型可通过改变列车停站方案进一步为部分确定性旅客需求之外的额外旅客需求提供服务，这表明鲁棒优化模型获得的开行方案对客流量的随机波动抗干扰能力更强。此外，相较于求解NM 模型，求解DRM 模型的时间并没有过多的增加，说明所构建的鲁棒优化模型具有较强的实用性。

(2)通过对参数α进行灵敏度分析发现，如果铁路运营公司愿意承担更大的运营成本，可更好地应对旅客需求的不确定性。因此，决策者在制定列车开行方案时，可综合衡量以上两因素，从而得出系统较优的运营方案。