公交系统在人们的出行活动中占据着重要的地位. 一个有效的公交系统不仅节省公交运营者的运营成本,还能吸引更多的乘客选择公交方式出行,从而减轻城市的交通拥堵. 公交线路时刻表设计是公交系统规划中最基本的活动之一^[1]. 然而,由于车辆行驶时间具有不确定性,造成车辆实际到站时刻与时刻表设定的到站时刻偏差较大,从而增加了公交时刻表的不可靠性^[2]. 不可靠的时刻表不但困扰乘客,还导致乘客对公交服务的整体印象变坏,这将极大地降低公交出行方式的吸引力^[1].

为实现公交车辆到站时刻的准时性,一些公交运营者将公交线路上的某几个站点作为时间控制站点来降低车辆实际到站时刻与时刻表的偏差^[3]. 这些站点一般是乘客对车辆到站时刻的准时性要求较高的站点,如在学校或公司附近的公交站点. 在采用时间控制站点的策略下,车辆发车时间不得早于时刻表设定的时刻. 为了克服车辆在相邻时间控制站点间路段的行驶时间的不确定性,有些学者提出在公交时刻表中加入松弛时间，从而为车辆提供充足的行驶时间^[4].

单线路公交时刻表设计就是在计划时段内设定各车次的车辆到达时间控制站点的时刻.文献[5, 6]采用解析方法或仿真模型来决策加入时刻表的松弛时间,使得系统成本最小.文献[7]同时考虑了随机的乘客需求和车辆行驶时间,在一个库存优化模型的框架下优化发车频率. 文献[8]将该问题描述为一个Knapsack问题,并设计了蚁群和遗传算法进行求解. 文献[9]在文献[3]的基础上进一步分析了四种不同运营策略对公交时刻表设计的影响,并给出了适用范围.

本文从可靠性视角来设计公交时刻表,考虑运营者的主观偏好对时刻表设计的影响,并采用了Monte Carlo仿真和不等式约束的方法将提出的期望值模型转化为线性规划模型.

设一条公交线路有M个时间控制站点，为不失一般性,线路第一个站点和最后一个站点分别作为时间控制站点1和时间控制站点M. 路段i(i=1,2,…,M-1) 是指从时间控制站点i到时间控制站点i+1的路段. 车辆从时间控制站点1驶向时间控制站点M,车辆在路段i的行驶时间服从某个概率分布函数 (包含乘客在时间控制站点上下车的时间^[4]). 如果车辆晚于时刻表设定的时刻到达时间控制站点,服务完乘客上下车后立刻出发;若早到达控制站点,车辆则在时刻表设定的发车时刻离开. 针对这一场景,要解决的单线路时刻表设计问题就是: 在给定的线路行驶时间约束下,如何分配各路段的车辆行驶时间,使得车辆实际到站时刻与时刻表的偏差和车辆超时行驶时间的权重之和最小.

在计划时段内,假设乘客需求均匀;在相同路段,车辆行驶时间服从相同的概率分布;各车次都按时从时间控制站点1出发. 基于这些假设,模型只需考虑一个车次的场景.

图 1描述了某个车次车辆的行驶时间过程,图中的符号含义如下.

图 1(Figure 1)

Fig. 1

图 1 一个车次车辆的行驶时间过程 Fig. 1 Running process of a single bus trip

1) 参数.t为一个车次可用的线路行驶时间 (min);M为时间控制站点数目;ξ_i为车辆在路段i (i =1,2,…,M-1) 的行驶时间 (min),是服从某个概率分布的随机变量;α_i为运营者对晚于时刻表到达站点i (i =2,3,…,M) 的时间偏差的单位惩罚系数;则设早于时刻表到达时间控制站点的时间偏差的单位惩罚系数为1;β为运营者对车辆超时行驶时间的单位惩罚系数.

2) 决策变量.X_i为路段i分配的车辆行驶时间 (min).

3) 辅助变量.A_i为时刻表设定的车辆到达时间控制点i (i =1,2,…,M) 的时刻 (min),其中已知A₁,不妨设A₁=0;W_i为车辆晚于时刻表到达时间控制站点i(i=2,3,…,M) 的时间偏差;L为车辆早于时刻表到达时间控制站点的总时间偏差;O为车辆超时行驶时间.

期望值模型P可描述如下:

通过该优化模型,求解出各路段的最优车辆行驶时间X=[X₁,X₂,…,X_M-1],则优化的时刻表中时间控制站点 i (i =2,3,…,M) 的车辆到站时刻可由式 (7) 求得.

在期望模型P中,约束(2)~(5) 是W_i,L,O取得非负值的表达式,使得模型P不易求解. 由于模型P是最小化模型,引入不等式约束(10)~(14) 来替代约束(2)~(5). 因此,模型P可等价为

模型P中目标函数的期望项使得问题很难求解. Monte Carlo仿真方法是求解该类问题可供选择的方法之一. 通过采样,随机行驶时间ξ_i的概率分布可以通过该分布函数随机产生样本大小为K的离散分布近似代替. Monte Carlo采样最大的优点是产生近似解的质量取决于抽样样本的规模. 模型P中目标函数的期望项可以表达为K次抽样目标之和的均值. 因此,模型P可近似转化为如下的线性规划模型 LP.

采用文献[3]中的公交线路1 W作为算例进行计算分析. 该条公交线路有4个时间控制站点,分别是站点1、站点8、站点13和站点19. 线路平均行驶时间为47.35 min. 表 1给出了车辆在各路段的行驶时间的拟合对数正态分布. μ_i 和σ_i 分别为路段i上车辆随机行驶时间的对数均值与方差.

表 1

Table 1

表 1(Table 1)

表 1 车辆随机行驶时间的拟合对数正态分布 Table 1 Fitting lognormal distribution of bus travel times 路段i 站点范围 拟合的对数正态分布参数 μi σi 1 1~8 2.917 0.112 2 8~13 2.525 0.162 3 13~19 2.776 0.136

表 1 车辆随机行驶时间的拟合对数正态分布 Table 1 Fitting lognormal distribution of bus travel times

其他参数的设置如下:T=50 min,M=4,α₂=α₃=α₄=3,β=5,K=5 000. 在以下计算分析中,如没有特别说明,参数值不变. 算法采用Visual C^#编写,调用CPLEX 12.4求解模型 LP. 运行算法的计算机配置为2 GB RAM,2.27 GHz CPU,Windows 7. 所有计算实验的算法运行时间都不超过3 s.

该算例的计算结果: 站点1,8,13和19的最优到站时间分别为 0,18.85,32.41,50 min;目标函数值为14.956.

本节对模型P中参数T,α_i=α(i=2,3,4),β,σ_i=σ(i=1,2,3)进行灵敏度分析. 在T,α,β和σ的取值范围分别为[47,62],[0.01,4.0],[0.01,5.0] 和[0.001,1.0] 的情况下进行计算. 线路最优行驶时间等于各路段最优行驶时间之和,也就是时间控制站点M的最优到站时间A_M.

1) T灵敏度分析.由图 2知,增大T,目标函数值,晚于时刻表和超时行驶时间惩罚值都减小至不变,而早于时刻表的偏差惩罚值增大至不变. 各路段分配的行驶时间随T增大而增大. 线路最优行驶时间最大值为53 min.

图 2(Figure 2)

Fig. 2

图 2 不同T下目标函数值、时刻表偏差惩罚值和超时行驶时间惩罚值、各路段最优行驶时间和线路最优行驶时间的变化 Fig. 2 Changes of objective value,schedule deviation value,overtime running value,optimal running time for each segment and route travel time with different T values

2)α灵敏度分析.由图 3可知,当α大于2时,α与目标函数值成线性关系;α对晚于时刻表的偏差惩罚值的影响最大;各路段分配的最优行驶时间随α增大至不变;线路最优行驶时间最大值为50 min.

图 3(Figure 3)

Fig. 3

图 3 不同α下目标函数值、时刻表偏差惩罚值和超时行驶时间惩罚值、各路段最优行驶时间和线路最优行驶时间的变化 Fig. 3 Changes of objective value,schedule deviation value,overtime running value,optimal running time for each segment and route travel time with different α values

3) β灵敏度分析.由图 4可知,β与目标函数值成线性关系;β对超时行驶时间惩罚值的影响最大;β对各路段的最优行驶时间影响较小;线路最优行驶时间不随β而变化.

图 4(Figure 4)

Fig. 4

图 4 不同β下目标函数值、时刻表偏差惩罚值和超时行驶时间惩罚值、各路段最优行驶时间和线路最优行驶时间的变化 Fig. 4 Changes of objective value,schedule deviation value,overtime running value,optimal running time for each segment and route travel time with different β values

4) σ灵敏度分析.由图 5知,增大σ,目标函数值呈指数增长,晚于时刻表的偏差惩罚值和车辆超时行驶时间惩罚值呈指数增长,早于时刻表的偏差惩罚值变化较小. 路段2分配的最优行驶时间随着σ增加而增加，而路段1和3呈下降趋势;线路最优行驶时间基本保持不变.

图 5(Figure 5)

Fig. 5

图 5 不同σ下目标函数值、时刻表偏差惩罚值和超时行驶时间惩罚值、各路段最优行驶时间和线路最优行驶时间的变化 Fig. 5 Changes of objective value,schedule deviation value,overtime running value,optimal running time for each segment and route travel time with different σ values

本文从可靠性的角度,建立了一个考虑车辆随机行驶时间的单线路公交时刻表设计期望值模型，模型中考虑了公交运营者主观偏好，采用Monte Carlo仿真和不等式约束的方法将期望值模型转化为线性规划模型. 通过一个实例,分析了模型中参数的灵敏度. 结果发现,车辆运行时间的不确定性将极大地增加公交系统的运营成本,系统总成本是随机运行时间方差的凸函数.