林禹童，曹成铉，柳雨彤，冯紫嫣

(北京交通大学 轨道交通控制与安全国家重点实验室，北京 100044)

城市轨道交通为市民提供了便利的出行方式，具有运行速度稳定、运输量大的特点。随着交通需求量的增加，城市轨道交通也面临着较大的运营压力。因此，设计一个与客流需求相匹配的列车时刻表和车底调度计划，对提高城市轨道交通的服务质量具有重要的现实意义。

在城市轨道交通列车调度问题的相关领域，国内外学者已经取得了很多研究成果，这些成果多以列车时刻表和客流需求匹配为目标。Schöbel[1]以乘客满意度为目标，将路线规划、时刻表制定和列车调度三个规划阶段整合进行综合规划。Wang等[2]提出了以客流需求为目标的混合整数非线性规划模型，求解和客流需求匹配的列车运行时刻表。Shi等[3]提出了以乘客满意度为目标的模型，该模型主要讨论在过饱和客流情形下，如何给出最优的列车时刻表和精确的客流控制策略。Robenek等[4]以乘客满意度为核心建立求解最优列车时刻表的混合整数线性规划模型。Robenek等[5]又对文献[4]的模型进行改进，引入乘客的随机需求要素，建立弹性需求模型。国内学者在相关研究领域也取得了一些成果。Yu等[6]和王世峰[7]提出了动态客流需求双层规划模型，并通过模型求解给出较优的列车时刻表和车底调度计划。薛彤[8]应用BP(back propagation)神经网络算法预测客流需求，对根据客流需求制定列车调度方案具有很大的参考价值。以上研究主要基于乘客需求建立模型，并进行求解，但未考虑城市轨道交通运行成本。

文献[9-11]以列车的最小运行时间为目标建立优化模型，得出最优列车车底调度方案，并对列车运行图的编制进行优化。周翔翔等[12]运用遗传算法，解决了轨道交通列车系统在以成本最低为目标时的最优列车开行方案。以上研究都是以城市轨道交通运营成本最小为目标给出解决方案。

目前的研究一般都是以乘客满意度或城市轨道交通运营成本最小为目标。本文在此基础上，在建模时综合考虑了乘客满意度和城市轨道交通成本两个要素，将两者结合构建目标函数。在模型求解上，运用模拟退火算法，设计出列车时刻表和车底调度方案，并通过数值算例验证模型的可行性。

1 模型建立

1.1 问题描述

在一个线状的线路中，有m个车站，车辆段位于线路的起终点站，线路如图1所示。列车运行路线有两个方向，分别是方向b1和b2，两个方向经过的车站完全相同，在线路中所有的站都需要停靠，其中，车站1为起点站，车站m为终点站。

列车运行方式为列车开始从某车辆段出发，到达某方向bi的起点站1站，然后沿方向bi出发，到达终点站m后，再进入对面的车辆段，从相反方向b3-i的起点站1站出发，执行新的运输任务(在该问题中有两个方向b1和b2，b1的相反方向为b2，b2的相反方向为b1，因此在一般性的描述中，用b3-i表示某方向bi的相反方向)。

图1 城市轨道线路图Fig.1 Urban rail transit line

1.2 模型假设

(1)两个方向的列车在各自的线路上，互不干扰。

(2)列车在所有中间车站均停车，且停车时间为定值。

(3)车底不属于特定的车辆段。

(4)列车到达中间站的下车率为定值。

(5)列车从某个车站发车到达另一个车站的时间为定值。

1.3 符号说明

模型中所使用的符号集合见表1，模型参数在表2中给出，模型变量见表3。

表1 符号集合

表2 模型参数Table 2 Parameters of model

表3 模型变量

1.4 模型构建

该模型的目标为综合目标，总共分为两个子目标，如下：

(1)降低运营成本

(2)降低乘客总等待时间

总乘客等待时间的计算方式，将总时间段分割成相等的离散时间段，对在每一个小的离散时间段内车站等待的乘客数进行计数，将每一个时间段内的乘客数相加，乘以离散时间段的时间单位得到总乘客等待时间。

设在方向b,车站i上的车次k和k+1的发车间隔为l，其中,

l=dk+1,i,b-dk,i,b。

(1)

单位时间段为Δt, 到达率定义为Δt内到站人数为λib，设将时间间隔分割成n个时间段，在k次列车发车后，有人数为wkib的乘客滞留在i站。其中，滞留的乘客在车次k和k+1之间的等待时间

t1=wkibl。

(2)

计算车次k和k+1次之间进站的乘客等待时间。由于乘客进站率为定值，每一个小时间段人数都增加lλib/n，则进站乘客的等待时间

(3)

在乘客达到率为定值的情形下，可以视为连续到达，则取极限

(4)

则有在该时间区间内，乘客总等待时间t总

(5)

在初始发车前的时间，滞留乘客数为0，所以乘客总等待时间为

(6)

将两个目标乘以一定的系数求和后形成一个综合目标，并以该目标函数最小化为最优目标。

在约束条件中，需要充分考虑要素：客流的分布情况；可调用的车底数量；列车乘客容量；最小停车间隔；客流状态平衡的约束，其中起点站乘客下车率为0，终点站为100%。

该模型的综合表述如下：

(7)

s.t.

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

2 算法设计

图2 算法流程图Fig.2 Flow chart of algorithm

在大规模问题中，找到较优列车调度方案的方法是先根据总的客流需求情况找到一个初始的运行方案，再根据每一时刻具体的客流状况沿着一定路径进行调整，逐渐找到较优的运行方案。由于该问题的混合整数规划模型由0-1决策变量组成，理论上可以使用枚举法找到最优解。但如果模型规模较大，则枚举法并不可行，而模拟退火算法可以提高寻找最优解的效率且可有效避免陷入局部最优解的困境，因此该模型的求解应用模拟退火算法。算法流程图如图2所示，应用该算法的具体步骤如下：

步骤1：初始化。给出初始温度T0、终止温度Tf,以及迭代次数n,第一步令T=T0,n=0,转步骤2。

步骤2：随机生成一个优化方案X′ 。判断此方案能否满足约束，若满足，则X′是可行的，令X′=X0，转步骤3继续迭代；若不满足，则对未满足约束条件的方案进行随机调整，直到生成一个可行方案，得到初始可行解，转至步骤3。

步骤3：对该方案进行随机扰动，直到得到一个符合约束的新方案X,并计算该方案和原可行方案X0的目标函数的增量Δf=f(X)-f(X0)，转至步骤4。

步骤 4：若Δf<0，则令X=X0，即接受路径X为新的路径；若Δf≥0，计算p=exp (-Δf/T0)，若p为大于(0,1)的随机数，令X=X0，让X成为新路径，转至步骤5，否则转至步骤3。

步骤 5：进行终止条件判断，满足则给出可行方案，结束迭代；否则更新T0，令n=n+1转至步骤3。

3 数值案例

图3 数值案例线路图Fig.3 Transit line in numerical case

表4 算例参数

表5 乘客需求

根据表4算例参数和表5乘客需求状况，应用模拟退火算法，得到的较优解对应的时刻表如表6所示。城市轨道交通列车运行图如图4所示。

表6 列车运行时刻表

图4 城市轨道交通列车运行图Fig.4 Diagram of timetable planning in urban transit line

在该时间段内，由于方向b1的乘客需求大，因此和方向b2比，发车频率较高。在目标函数中考虑降低乘客总等待时间和列车运行成本后，其发车频率更加合理。若仅考虑降低乘客总等待时间，则成本的增加量高于乘客总等待时间的降低量后，目标函数值会增加。在建立目标函数时，综合考虑乘客等待时间和运营成本，可得到一个和客流需求匹配，且能够节约成本的列车运行计划。

4 结论

本文根据乘客需求，以最小化乘客总等待时间和城市轨道交通系统运营成本为综合目标，建立混合整数规划模型。在模型求解时，运用模拟退火算法得到较优的列车时刻表和车底调度方案，并通过算例分析对模型进行验证，结果证明该较优解是符合客流需求的。

本文数值算例的计算结果与预期一致。相比目标函数中仅考虑单一要素，本文考虑综合要素后给出的列车调度方案，发车频率保持在一个合理的范围，且和客流需求更加匹配，不会出现列车发车频率过高或者过低的情况。而保持一个合理的发车频率，既可以降低乘客等待时间，提高乘客满意度，又可以降低列车运营成本。

但是该模型是在列车停站时间及客流下车率为定值的假设下提出的，缺乏灵活性，如果乘客下车率在不同车站不同时段是变动的，则对于该优化问题中模型提出了更多的改进要求，这也是下一步的工作方向。