高铁车站接运公交时刻表与车辆调度综合优化

郭小乐， 宋 瑞， 何世伟， 黎浩东， 孙 杨， 张英群

(1. 北京交通大学 综合交通运输大数据应用技术交通运输行业重点实验室, 北京 100044；2. 交通运输部科学研究院, 北京 100029)

近年来，我国高速铁路发展迅速，大部分新建高铁站位于城市郊区或新城[1]。相当数量城市的高铁站尚未接入城市轨道交通，或城市轨道交通覆盖地区较小。而且随着高铁运营时间的延长，存在部分高铁列车在城市轨道交通结束运营后抵达高铁站的问题。在这些情况下，高铁站接运公交是集散高铁客流的重要交通方式，这对高铁站接运公交与高铁站的衔接提出了较高要求。高铁站接运公交主要服务于高铁客流的集散。合理的接运公交时刻表可以实现客流的快速集散与输送乘客数的最大化，吸引更多高铁乘客选择公共交通出行，降低社会成本。合理的车辆调度计划可以有效减少运用车辆数，降低企业运营成本。时刻表和车辆调度问题相关性较强，对两个问题进行综合优化兼顾了社会和公交企业的利益，更具现实意义。

部分学者对公交时刻表与车辆调度综合优化问题进行了研究。文献[2-5]研究了等发车间隔时刻表与车辆调度综合优化问题。高铁到达客流在时间分布上集中度高，同时还具有一定的不均匀性，高铁站接运公交的发车时刻应与高铁列车到站时刻适当配合，等发车间隔时刻表并不适用于高铁站接运公交。文献[6-11]建立数学规划模型求解不等发车间隔时刻表与车辆调度综合优化问题，但均未考虑浪涌式大客流对运营调度的影响。实际运营中，在高铁客流到达高峰期时，可能会出现乘客不能及时换乘的现象，大量客流瞬时积聚，给城市交通系统和高铁站造成巨大压力。另外，过长的候车时间也可能造成公交客流流失。针对这一现象，文献[12]考虑了快速公交首站和地铁接驳换乘大客流常态化导致客流损失的情况，对快速公交的发车间隔进行决策；文献[13]考虑了受公交车辆的运能限制而发生乘客在换乘站点滞留的现象，建立数学模型以调整公交线路的发车时刻和发车间隔。但上述文献均未考虑时刻表与车辆调度综合优化问题。

本文针对客流高峰期高铁站接运公交时刻表与车辆调度综合优化问题，以流失乘客数最少、使用的公交车辆数最少为优化目标，以车辆满载率、乘客等待时间、最大可用公交车辆数、公交车辆执行车次的顺序等为约束条件，建立了时刻表与车辆调度综合优化模型，设计了非支配排序遗传算法对该模型进行求解，并用算例验证了模型和算法的正确性与有效性。

1 问题描述

某高铁站附近往往存在多条接运公交线路的首站。公交车辆从首站出发，沿线路行驶至最远端车站后按原路线返回首站，再执行下一车次。公交车辆仅可在首站跨线执行其他线路的车次，即车辆在不同线路间的空驶距离为0。对于这些线路实施区域调度可以实现资源的优化配置，提高公交车辆运营效率，因此本文采用区域调度模式对所有公交车辆进行统一调度。

高铁客流到发集中度高，在时间分布上具有瞬时性与不均匀性[14]。在高铁客流到达高峰期时，接运公交首站的客流需求激增，可能出现大量客流积聚，给高铁站和城市交通系统造成巨大压力。高铁乘客具有时间价值高的特点，到达后往往希望快速出站换乘市内交通，导致接运公交首站经常出现浪涌式大客流。另外，较高的时间价值也意味着过长的候车时间会造成乘客的流失。

因此，在客流高峰期高铁站接运公交主要起到疏散高铁到站乘客的作用。由于高铁列车到站时刻分布不均匀，并且高铁客流具有集中到达的特点，为实现高效的客流疏散，减轻高铁站乘客积聚压力，高铁站接运公交的发车时刻应适当与高铁列车到站时刻相配合，而不适用等发车间隔时刻表。增加发车次数可以疏散更多高铁到站乘客，但往往意味着用车数的增加。决策者需要在发车次数与用车数之间权衡，以实现社会成本与企业成本的最小化。本文研究如何合理编制高铁站接运公交发车时刻表与车辆调度计划，从运营角度实现高铁站接运公交与高铁列车的有效衔接，运送高铁到站客流由接运公交首站向目的地疏散的客流运输过程。

2 数学模型

为方便建模，添加1条虚拟公交线路l′，2个虚拟发车时刻i′、i′′。该虚拟公交线路的全程走行时间为0，仅可能在i′、i′′发车。需要决策的变量如下：

(5) 公交车辆执行车次顺序的0-1决策变量zlmij，当存在公交车辆执行完公交线路l在时刻i发出的车次后紧接着执行公交线路m在时刻j发出的车次时，则zlmij=1，否则zlmij=0。

构建如下高铁站接运公交时刻表和车辆调度综合优化模型。

( 1 )

( 2 )

s.t.

∀i∈I,l∈L

( 3 )

( 4 )

∀i∈I,l∈L,g∈G

( 5 )

∀i∈I,l∈L,g∈G

( 6 )

( 7 )

∀i,j∈I,gtj

( 8 )

( 9 )

(10)

(11)

∀j∈I,m∈L

(12)

(13)

∀i,j∈I,l,m∈L

(14)

(15)

(16)

(17)

(18)

∀i,j∈I∪i′∪i″,l,m∈L∪l′,g∈G

式( 1 )为目标函数，表示最小化流失乘客数；式( 2 )为目标函数，表示最小化使用公交车辆数。模型中的约束条件：式( 3 )表示乘客只能换乘在时刻ti发车的公交车次，且换乘至某公交车次上的总乘客数须满足公交线路的最大、最小满载率约束；式( 4 )为乘客只能换乘时间条件允许的公交车次，且某列车上换乘至某公交车次的乘客数须满足公交线路的最大满载率约束；式( 5 )、式( 6 )分别为乘客只能换乘在其所在的列车到达高铁站之后以及在其因等待时间过长而放弃换乘之前发车的公交车次；式( 7 )为所有到达的乘客或者换乘成功，或者因等待时间过长而放弃换乘；式( 8 )为某时刻到达的乘客必须等在其之前到达的乘客换乘完毕才能开始换乘；式( 9 )为某时刻到达的乘客在超过最长等待时间之前不会流失；式(10)为决策变量关系约束；式(11)为流失的乘客总数不能超过要求的最大流失乘客数；式(12)为某公交车辆在执行某实际公交车次之前和之后分别只能执行1个公交车次；式(13)为实际使用的公交车辆数不能超过最大可用的公交车辆数；式(14)为某公交车辆必须完成上一公交车次后才能开始执行下一公交车次；式(15)为公交车辆只能执行实际发出的公交车次；式(16)、式(17)分别为换乘成功和放弃换乘的乘客人数非负约束；式(18)为0-1决策变量约束。

3 模型求解算法

本文构建的模型为多目标优化模型，采用产生式方法求解问题的Pareto解集，向决策者提供多个时刻表与车辆调度方案更具现实意义。另外，车辆调度问题(Vehicle Scheduling Problem)属于NP-hard问题[15]，因此公交时刻表与车辆调度综合优化问题也属于NP-hard问题，问题复杂程度较大，很难使用精确算法在有限时间内求得最优解。本文基于NSGA-Ⅱ算法设计求解算法。NSGA-Ⅱ算法是一种较为成熟的多目标智能优化算法，在城市公共交通领域，NSGA-Ⅱ已得到广泛应用[16-19]，取得了良好效果，其详细介绍可以参见文献[20]。

3.1 个体编码方式

个体编码方式见图1。各线路时刻表采用0-1编码方式，0表示该线路在某时刻不发车，1表示发车。

3.2 个体适应度评价

采用模型的目标函数即流失的最少乘客数和所需的最少公交车辆数对个体进行评价。假设每个车次只能发出1辆车，则当车辆容量、各时段最大、最小满载率、乘客最长等待时间以及各高铁列车上的换乘需求确定时，最少流失乘客数即可通过求解模型M1求得。

M1：minFTT(X)

s.t.

式( 3 )～式(11)

式(16)～式(17)

∀i∈Ip,p∈P,l∈L,g∈G

(19)

同理，当各公交线路的全程走行时间和最大可用公交车辆数确定时，所需的最少公交车辆数可通过求解模型M2求得。

M2：minFVS(X)

s.t.

式(12)～式(15)

zlmij∈{0,1}

∀i∈Ip,j∈Iq,p,q∈P,l,m∈L

(20)

模型M1、M2均为线性规划模型，可通过调用ILOG CPLEX数学优化引擎进行求解。

3.3 不可行解的处理方法

由于本文建立的多目标优化模型约束较多，随机生成的初始种群极易产生不可行个体。另外，算法交叉、变异过程的随机性导致在寻优过程中也极易产生不可行个体。大量不可行解的存在将极大影响算法的寻优效率与效果，本文采取以下方法解决这一问题。

(1) 在算法的交叉、变异的过程中松弛模型中的式(11)，也允许不满足模型其他约束的不可行解存在，对于不满足除模型中的式(11)以外的其他约束的不可行解，将其流失乘客数或所需的公交车辆数设为一个较大值。

(2) 为提高算法效率，在保证个体满足除式(11)以外的其他约束的前提下随机生成初始种群。为达此目的，可采用如下规则产生初始种群个体。

Step1随机生成一个个体。

Step2求解模型M1(不含式(11))，M2，若模型M1，M2均可求得最优解，则M1，M2的最优解目标值分别为该个体的流失乘客数与所需车辆数，规则终止；否则转Step3。

Step3随机选择该个体编码值为1的某个基因位，令其编码值为0，转Step2。

(3) 如前所述，由于在种群初始化及交叉、变异过程中暂未考虑模型中的式(11)，在上述过程中产生的个体的流失乘客数可能多于最大流失乘客数。为尽快获得满足最大流失乘客数约束的可行解，缩短运算时间，引入“车次插入”算子，规则如下。

Step1设置“车次插入”概率p′、种群规模Z，令k=0。

Step2若k=Z，规则终止；否则对当前种群中的个体k生成随机数rk，若rk>p′或个体k流失乘客数不多于最大流失乘客数，转Step5；否则转Step3。

Step3随机选择该个体编码值为0的某个基因位n，令其编码值为1，求解模型M1，M2。

Step4若模型M1，M2均可求得最优解，则更新该个体的流失乘客数与所需车辆数分别为M1，M2的最优解目标值，转Step2；否则令基因位n的编码值为0，求解模型M1，M2，更新该个体的流失乘客数和所需车辆数，以其替换当前种群中随机选择的某个体。

Step5k=k+1。

3.4 算法流程

高铁站接运公交线路发车时刻表和用车数计算步骤如下。

Step1初始化。令s=0，确定种群规模Z、交叉概率pc、变异概率pm和最大迭代次数S，随机生成父代种群P0，计算P0所有个体的最少流失乘客数与所需的最小公交车辆数。

Step2对Ps执行快速非支配排序操作，得到所有个体的非支配排序值。

Step3对Ps执行选择、交叉、变异操作，生成规模为Z的子代种群Qs，计算Qs所有个体的最少流失乘客数与所需的最小公交车辆数。

Step4将Ps和Qs合并为规模为2Z的新种群Rs，对Rs执行快速非支配排序操作，得到所有个体的非支配排序值。

Step5精英保留。令Ps+1=∅，r=1。

如果Ps+1与Rs中非支配排序值为r的个体数之和不大于Z，则将Rs中非支配排序值为r的个体全部放入Ps+1；如果Ps+1与Rs中非支配排序值为r的个体数之和大于Z，则计算Rs中非支配排序值为r的个体的拥挤距离，将这些个体按照拥挤距离从大到小依次放入Ps+1，直至Ps+1中的个体数为Z为止。

Step6执行“车次插入”算子。

Step7对Ps+1执行快速非支配排序操作，得到所有个体的非支配排序值。

Step8更新Pareto解集。Ps+1中非支配排序值为1的个体即为最新的Pareto解集。

Step9终止检验。若s=S，则输出Pareto解集，终止算法；否则令s=s+1，转Step3。

4 算例分析

4.1 算例说明

某高铁站共有4条接运公交线路接入，其首站均设在该高铁站附近。各线路全程走行时间见表1。运营时间段为21:00—23:00，在该时间段内共有8列高铁列车到达高铁站，各次列车到站时间及各次列车上需要换乘各接运公交线路的乘客数见表2，各次列车均为虚拟车次。

表1 接运线路全程走行时间

表2 列车到站时间及换乘需求

从21:00开始，以5 min间隔设置可能的发车时刻，可能的发车时刻的最大、最小满载率要求见下表。

表3 满载率要求

公交车辆额定载客数C取100人/辆，乘客最长等待时间W取15 min，流失乘客数上限Nr为700人，最大可用公交车辆数Nv为30辆。

4.2 算例结果及分析

算法设计的参数设置如下：种群规模Z=20，最大迭代次数S=100，交叉概率pc=0.9，变异概率pm=0.3，“车次插入”概率p′=0.4。机器配置为2.27 GHz CPU和4 GB内存，采用C#语言编程，并调用ILOG CPLEX 12.4实现本文设计的算法。某次计算过程用时56.38 min，共获得8个Pareto近似最优解(不含式(11))，其中流失乘客数不超过流失乘客数上限的Pareto近似最优解3个。各Pareto解的流失乘客数与使用公交车辆数见表4。各Pareto近似最优解的最少流失乘客数为370人(占换乘需求总数的9.81%)，表5～表9分别给出了解2对应的各接运公交线路的时刻表与使用的最少公交车辆数的车辆调度方案、使得各接运公交线路流失乘客数最少的换乘各车次的乘客数(表5中每一发车时刻下的数字为执行该车次的车辆编号)。

表4 各Pareto解的目标值

由表4可知，本文设计的算法运行一次可得到多个Pareto近似最优解。决策者可根据偏好选择一个Pareto近似最优解作为最终的高铁站接运公交时刻表，当其偏重企业成本时，可选择解3；当其偏重社会成本时，可选择解1；当其同时看重两个目标时，可选择解2。

表5 各接运公交线路时刻表及车辆调度方案(解2)

表6 接运线路1换乘方案(解2)

表7 接运线路2换乘方案(解2)

表8 接运线路3换乘方案(解2)

表9 接运线路4换乘方案(解2)

将各Pareto近似最优解映射至坐标平面，见图2。

合理选取优化目标对于多目标优化问题至关重要。对于2个优化方向均为最小化的目标，如果它们之间存在正相关关系，则这2个优化目标是不冲突的，即只有其中1个优化目标有效。由图2可知，各Pareto近似最优解中，解的流失乘客数越少，则使用公交车辆数越多，即流失乘客数与使用公交车辆数是2个相互冲突的目标。因此本文选取流失乘客数与使用公交车辆数作为优化目标较为合理。

4.3 最大可用公交车辆数灵敏度分析

将最大可用公交车辆数在20～30辆范围内调整，最少流失乘客数见图3。

由图3可知，当最大可用公交车辆数为20辆时，最少流失乘客数多于流失乘客数上限；在20～26辆之间时，随着最大可用公交车辆数的增加，最少流失乘客数逐渐减少。当最大可用公交车辆数大于26辆时，随着最大可用公交车辆数的增加，最少流失乘客数不再发生变化。

运送乘客总数与发车次数之比即为每车次运送的平均乘客数，根据每车次运送的平均乘客数和公交车辆额定载客数可以计算每车次的平均满载率，该指标可以反映乘客的乘车舒适度。随着最大可用公交车辆数的增加，车次平均满载率逐渐降低，当最大可用公交车辆数超过26辆时，由于最优解均相同，运送乘客总数与发车次数均不再变化，因此车次平均满载率不再变化。因此当最大可用公交车辆数为26辆时，继续增加最大可用公交车辆数在增加运营成本的同时已无法降低最少流失乘客数和车次平均满载率，即无法提高服务水平和乘客舒适度。决策者可在权衡企业与乘客成本的前提下对最大可用公交车辆数进行决策。

4.4 接运公交时刻表与高铁到达客流一致性分析

以10 min为单位时段统计21:00—23:00内各时段的换乘需求和发车次数，见图4。

由图4可知，各接运公交线路各时段的发车次数与换乘需求一致性较高。各接运公交线路各时段的发车次数的变化趋势较换乘需求的变化趋势具有一定的滞后性，这是因为乘客可以等待一定时间(最长15 min)，本时段到达的乘客可能需等待至下一时段被运送。对于高铁站接运公交线路，各时段发车次数无周期规律，不同时段的发车次数差异较大，这符合高铁站客流到达规律，以及降低车辆运用数量的目的，但需要铁路运输部门与城市公交运营管理部门在客流数据方面有更好的交流共享机制。

5 结论

本文针对客流到达高峰期高铁站接运公交时刻表与车辆调度综合优化问题，考虑因等待时间过长导致的乘客流失，以流失乘客数最少和使用公交车辆数最少为优化目标，以车辆满载率、乘客等待时间、最大可用公交车辆数、公交车辆执行车次的顺序等为约束条件，构建了高铁站接运公交时刻表与车辆调度综合优化模型，并用带精英策略的非支配排序遗传算法NSGA-Ⅱ求解获得了近似Pareto最优解集。算例的计算结果表明，通过该模型及算法可以在有限的时间内获得多个较优的接运公交时刻表与车辆调度方案，供决策者选择，验证了模型及算法的有效性。实际工作中，接运公交除承担了高铁客流的集散任务外，还需满足线路沿线其他车站的出行需求，因此考虑以高铁站为起、终点的双方向客流以及线路其他车站出行需求优化时刻表和车辆调度方案将是今后研究的一个重点。另外，车辆在行驶途中可能发生延误，如何在考虑车辆延误的情况下保证车辆接续也将是未来研究的一个方向。