高效的公交系统不仅节省运营成本,还能吸引更多的乘客选择公交出行,从而缓解交通拥堵.公交规划是提高公交系统效率的重要手段之一,它包括4个子问题: 线路设计、 时刻表设计、 车辆调度及司售人员调度^{[1, 2]}.公交网络时刻表设计是公交规划过程中最为关键和复杂的问题之一.它确定各线路车次从始发站的发车时间,使不同线路的车辆协同到达换乘站点,以便乘客及时换乘.如果设计的时刻表没有使车辆协同到达换乘站点,必造成较长的乘客换乘等待时间^[3].这将降低乘客对公交服务质量的满意度,导致有些乘客放弃公交出行.

因此,公交网络时刻表设计问题受到了学者们的极大关注.Cevallos等^[4]构建了固定发车间隔下的公交时刻表设计问题的整数规划模型.Shafhi等^[5]提出了一个更加实际的固定发车间隔下的公交时刻表设计问题,给出了乘客平均换乘等待时间的数学表达式，构建了以乘客总换乘等待时间最小为目标的混合整数规划模型.Ceder等^[6]以最大化车辆协同到达换乘站点次数为目标,建立了求解不均匀发车间隔下的公交网络时刻表问题的混合整数规划模型.Eranki^[7]将车辆协同方式重新定义为不同线路的车辆到达换乘站点的时间差在一个给定的时间窗内.Ibarra-Rojas等^[8]在文献[6, 7]的基础上,建立了一个以车辆协同到达换乘站点次数最大为优化目标的混合整数规划模型.Parbo等^[9]研究了固定发车间隔下的双层公交时刻设计问题.Wu等^[10]研究了车辆随机行驶时间情况下的公交网络时刻表设计问题.然而,未见有文献同时考虑不均匀发车间隔和以最小化乘客总换乘等待时间为目标的公交网络时刻表设计问题.该问题的难点是如何使用数学表达式精确描述不均匀发车间隔下乘客的换乘等待时间.本文考虑同时具有这些特征的公交网络时刻表设计问题,定义了车辆在换乘站点的灵活协同方式; 构建了求解该问题的混合整数规划模型; 设计了求解该模型的预处理方法.通过计算不同的算例,验证了求解方法和模型的有效性.

在一个公交网络中,乘客出行经常面临换乘的情况.在某时段内,每条线路具有固定的发车车次,相邻车次发车间隔具有最小值和最大值.本文研究的问题是如何设计各线路车次的发车时间,从而使乘客在换乘站点经历较短的换乘时间.为避免不同线路的车辆在换乘站点发生串车现象^[8],乘客要换乘的车辆与乘客先前乘坐的车辆先后到达换乘站点的时间间隔要大于预先设定的值,并且换乘等待时间要小于预先设定的值.

图 1所示为由两条线路组成的一个简单的公交网络.在7:00-8:00时段内,线路i和线路j发车次数都为5.线路i和线路j的最小发车间隔和最大发车间隔都分别为15和20 min.线路i和线路j从始发站到换乘站点b的车辆行驶时间分别为10和30 min.假设乘客从线路i(或线路j)的某个车次换乘到线路j(或线路i),则这两个车次的车辆到达换乘站点b的时间间隔要大于2 min,且乘客的换乘等待时间要小于6 min.要解决的问题就是在满足上述条件下,如何设计每条线路各车次的发车时间,从而使乘客的总换乘等待时间最小.

图1(Fig. 1)

图1 由两条线路组成的简单公交网络 Fig. 1 Simple bus network with two lines

1) 仅考虑网络中的换乘站点:对任意站点,车次从始发站到该站点的运行时间等于该路段站点间的运行时间和在各站点停留时间之和.

2) 仅考虑计划阶段的时刻表设计问题:在计划时间段内车辆在站点间的运行时间是固定的; 不考虑随机的车辆行驶时间.

3) 在计划时间段内,乘客的需求是均匀的.

1) 索引集:i,j为线路的索引集; p,q为车次的索引集; b为换乘站点的索引集; I为线路集合; J_i为与线路i在换乘站点存在车次协同的线路集合; B^ij为线路i∈I和j∈J_i的车辆所经过换乘站点的集合.

2) 参数:T为计划时段长度,则计划时间段可标准化为[0,T]; F_i为线路i的发车次数; H_minⁱ为线路i的最小发车间隔; H_maxⁱ为线路i的最大发车间隔; t_bⁱ为线路i到换乘站点b的行驶时间; M为一个较大的正数; w_b为车辆在换乘站点b协同时间窗的下界; W_b为车辆在换乘站点b协同时间窗的上界或最大换乘等待时间; P_pb^ij为在换乘站点b,从线路i的第p个车次换乘到线路j的平均乘客数.

3) 决策变量:X_pⁱ为线路i的第p个车次从始发站的发车时间; Y_pqb^ij为在换乘站点b,乘客是否能从线路i的第p个车次换乘到线路j的第q个车次,如果是,则Y_pqb^ij=1; 否则为0.

4) 变量:WT_pqb^ij为在换乘站点b,乘客从线路i的第p个车次换乘到线路j的第q个车次的等待时间.

假设乘客从线路i的第p个车次换乘到线路j的某个车次，图 2定义了两线路的车辆到达换乘站点的灵活协同方式.线路i的第p个车次到达换乘站点b的时刻为8:13,线路j的第q个车次到达换乘站点b的时刻为8:15.这两个车次到达换乘站点b的时间间隔为2 min,在时间窗[w_b,W_b]=[2,6]内,所以线路i的第p个车次上的乘客可以换乘到线路j的第q个车次,且换乘等待时间为2 min (小于W_b).如果线路j的第q个车次到达换乘站点b的时间与线路i的第p个车次到达换乘站点b的时间间隔在时间窗[w_b,W_b]=[2,6]内,称这两个车次的车辆能够灵活协同到达换乘站点b.因此,线路i的第p个车次不能与线路j的第q+1个车次协同到达.但是,线路j的第q+1个车次与线路i的第p+1个车次协同到达换乘站点b.

图2(Fig. 2)

图2 车辆到达换乘站点的灵活协同方式定义 Fig. 2 Definition of flexible synchronization of buses arriving at transfer node

本文将乘客等待第一个可换乘车次的时间作为换乘等待时间,并且乘客只能换乘到一个车辆.图 3定义了线路i的第p个车次上乘客换乘到线路j的等待时间.因为线路j的第q个车次之前的车次早于线路i的第p个车次到达换乘站点,所以乘客不可能换乘到这些车次,相应的换乘等待时间为零.按照2.3的定义,线路i的第p个车次上的乘客换乘到线路j的第q个车次,换乘等待时间为这两个车次的到站时间差.虽然乘客也可以换乘到线路j的第q个之后的车次,由于乘客只能换乘到第q个车次的车辆,所以相应的换乘等待时间应为零.线路i的第p个车次的乘客换乘到线路j的第q个车次的等待时间见式(1)~(4)：

图3(Fig. 3)

图3 换乘等待时间定义 Fig. 3 Definition of passenger transfer waiting time

不等式(1)，(2)定义线路i的第p个车次可以换乘到线路j的车次.如果(X_q^j+t_b^j)-(X_pⁱ+t_bⁱ)≥w_b,则Y_pqb^ij=1,否则Y_pqb^ij=0.结合图 3可以得出Y_pqb^ij=1,Y_p1b^ij=0,…,Y_p(q-1)b^ij=0和Y_p(q+1)b^ij=1,…,Y^ij_pFjb=1.在不等式(1)~(3)和最小化目标函数的共同作用下,将使得WT_pqb^ij=(X_q^j+t_b^j)-(X_pⁱ+t_bⁱ),线路i的第p个车次换乘到线路j其他车次的等待时间为零.不等式(4)为换乘等待时间不大于W_b.因此,不等式(1)~(4)准确地描述了乘客的换乘等待时间.

以最小化乘客总换乘等待时间为目标的混合整数规划模型P:

Odijk^[11]研究了固定发车间隔下的公交网络时刻表设计问题的一个特例，通过类比顶点着色(vertex-coloring)问题,证明了该时刻表设计问题是NP-complete问题.Ibarra-Rojas^[8]进一步证明了不固定发车间隔下,以最大化车辆协同达到换乘站点次数的公交时刻表设计问题是NP-hard问题.所以,本文研究的考虑不均匀发车间隔和以乘客换乘总等待时间最小为目标的公交时刻表设计问题是一个NP-hard问题.

基于文献[8]的思路,通过对模型P中约束(6)~(8)的分析,得到线路各车次发车时间X_pⁱ的发车时间窗.分析步骤如下:

步骤1 设线路i的第一个车次发车时间为零时刻,即X₁ⁱ=0,则线路i的第p个车次的最早发车时间为(p-1)H_minⁱ;

步骤2 设线路i的第一个车次X₁ⁱ=H_maxⁱ,则线路i的第p个车次的最晚发车时间为min{T,pH_maxⁱ};

步骤3 设线路i的最后一个车次Xⁱ_Fi=T-H_maxⁱ,则线路i的第p个车次的最早发车时间为max{0,T-(F_i-(p-1))H_maxⁱ};

步骤4 设线路i的最后一个车次Xⁱ_Fi=T，则线路i的第p个车次的最晚发车时间为T-(F_i-p)H_minⁱ.

因此,可以得到线路i的第p个车次X_pⁱ的发车时间窗D_pⁱ为

定义线路i的第p个车次到达换乘站点b的到达时间的时间窗A_pbⁱ为

如果线路i的第p个车次要与线路j的第q个车次满足2.3定义的灵活协同换乘,则线路j的第q个车次的发车时间要满足

定义S_pbⁱ= [left(A_pbⁱ)+w_b;right(A_pbⁱ)+W_b]为与线路i的第p个车次在换乘站点b满足灵活协同到达的时间窗.根据公式(11)~(13),公式(14)可以推广为

基于以上分析,结合不等式(1)~(3)和约束(6)~(8),线路i的第一个车次不可能与线路j的最后一个车次协同到达.如果线路i的第p个车次可以换乘到线路j的第q个车次,即Y_pqb^ij=1,则Y_p(q+1)b^ij=1,…,Y^ij_pFjb=1.因此,得到Y_pqb^ij具有图 4所示的特殊结构.

图4(Fig. 4)

图4 在换乘站点b线路i和线路j∈Ji车次间关系的Ypqbij具有的特殊结构 Fig. 4 Typical structure of Ypqbij related to lines i and j∈Ji at transfer node b

基于3.2节的分析,算法1计算每个车次所有可行的发车时间、 到站时间和协同到达时间窗.根据公式(15),删除每对不可能协同到达的两车次对应的决策变量和约束,从而缩减了问题的求解空间.

算法1 预处理方法 (模型P)

采用算例的参数设置如下: T=200 min,3条线路,每条线路的发车次数F_i=20,3个换乘站点,线路1和线路2分别在换乘站点1和2相互换乘; 线路1和线路3在换乘站点3相互换乘.每个站点的协同时间窗为[w_b,W_b]=[2,6],线路始发站到换乘站点的车辆行驶时间在[1,20]范围内产生.为了与文献[8]中模型相比较,设P_pb^ij=1.每个算例的参数[H_minⁱ;H_maxⁱ]取值不同.在Visual Studio 2008编译环境下,C#语言编写预处理方法和调用CPLEX 12.4求解模型.除了计算时间设为1 800 s外,其他参数为默认设置.

分别求解模型P和使用预处理方法处理后的模型P′,计算结果如表 1所示.表 1说明预处理方法能够较大程度地缩减可行解空间,减少了求解时间.使用CPLEX求得的解与相应的松弛模型的最优解的gap为0,说明得到模型的最优解.从求解时间和解的质量上,说明本文采用的预处理方法是有效的.

表1(Table 1)

表1 分支定界算法求解模型P和P′的结果 Table 1 Results of models P and P′ solved by branch and bound algorithm [Hmini;Hmaxi] 模型P 模型P′ 缩减求解空间分数/% 与松弛模型的gap /% 求解时间/s 与松弛模型的gap /% 求解时间/s [9; 11] 0 9.6 0 4.16 78.2 [8; 12] 0 14.5 0 5.80 68.7 [7; 13] 0 22.9 0 9.46 60.1 [6; 14] 0 24.3 0 9.22 52

表1 分支定界算法求解模型P和P′的结果 Table 1 Results of models P and P′ solved by branch and bound algorithm

采用乘客总换乘等待时间和最大车辆协同达到次数两个指标,分析本文模型P的有效性.表 2和表 3分别是求解模型P和文献[8]中模型的结果.从表 2和表 3可以看出,与文献[8]的模型相比,本文提出的模型不仅求得最优的车辆协同达到次数,而且求得的乘客总换乘等待时间还较短.说明了本文模型的有效性.同时本文模型的求解时间较短,且所有的算例都能求得最优解.

表2(Table 2)

表2 采用分枝定界和预处理方法求解模型P的结果 Table 2 Results of model P solved by branch and bound with preprocessing algorithm [Hmini;Hmaxi] 总换乘等待时间/min 车辆协同达到次数 与松弛模型的gap/% 求解时间 s [9; 11] 562 117 0 4.16 [8; 12] 554 117 0 5.80 [7; 13] 548 117 0 9.46 [6; 14] 542 117 0 9.22

表2 采用分枝定界和预处理方法求解模型P的结果 Table 2 Results of model P solved by branch and bound with preprocessing algorithm

表3(Table 3)

表3 采用分支定界算法求解文献[8]的模型 Table 3 Results of model in literature [8] solved by branch and bound algorithm [Hmini;Hmaxi] 总换乘等待时间/min 车辆协同达到次数 与松弛模型的gap/% 求解时间 s [9; 11] 579 117 0 1 297 [8; 12] 570 115 110.26 1 800 [7; 13] 562 113 194.57 1 800 [6; 14] 566 115 268.26 1 800

表3 采用分支定界算法求解文献[8]的模型 Table 3 Results of model in literature [8] solved by branch and bound algorithm

本文研究了不均匀发车间隔情况下的公交网络时刻表设计问题,构建了以乘客总换乘等待时间最小化为目标的混合整数规划模型,分析了求解模型的复杂性和可行解的空间结构.基于模型特征分析,设计了缩减求解空间的预处理方法.通过计算不同算例,验证了求解方法和模型的有效性.本文以乘客总换乘等待时间最小为目标的模型比文献中以最大车辆协同到达换乘站点次数为目标的模型更有效.设计有效求解大规模问题的算法是今后的研究方向之一.