, 唐加福11. 东北大学 信息科学与工程学院, 辽宁 沈阳 110819;
2. 江苏科技大学 经济管理学院, 江苏 镇江 212003
收稿日期: 2015-03-11
基金项目: 国家创新研究群体科学基金资助项目(71021061).
作者简介: 吴影辉(1986-), 男, 安徽阜阳人, 东北大学博士研究生; 唐加福(1965-), 男, 湖南东安人, 东北大学教授, 博士生导师.
摘要: 公交网络时刻表设计就是通过优化各线路车次的发车时间, 使不同线路的车辆协同到达换乘站点, 以方便乘客换乘. 研究了不均匀发车间隔情况下公交网络时刻表设计问题. 使用数学不等式描述了乘客的换乘等待时间, 构建了以最小化乘客总换乘等待时间为目标的混合整数规划模型, 分析了该模型的计算复杂性和可行解的空间结构特征. 基于模型特征分析, 设计了能缩减求解空间的预处理方法. 采用CPLEX优化软件对预处理后的模型进行求解. 通过计算不同算例, 验证了求解方法和模型的有效性.
关键词: 公交时刻表不均匀发车间隔换乘等待时间混合整数规划模型预处理方法
Optimization Model for Bus Network Timetabling with Uneven Headway
WU Ying-hui1,2
, TANG Jia-fu11. School of Information Science & Engineering, Northeastern University, Shenyang 110819, China;
2. Economics & Management School, Jiangsu University of Science and Technology, Zhenjiang 212003, China
Corresponding author: WU Ying-hui, E-mail: neuyhwu@gmail.com
Abstract: The bus network timetabling is to optimize the departure time of each trip of all lines to make buses from different lines synchronously arrive at transfer nodes, so that passengers have smooth transfers. A bus network timetabling problem with uneven headways was studied. The waiting time for transferring were formulated by using mathematical inequalities. A mixed integer programming model was proposed to minimize the total waiting time of transferring passengers. The computational complexity of the model and the spatial structural characteristics of the feasible solution were analyzed. Then, a preprocessing approach was designed to reduce the solution space. An optimization software CPLEX was used to solve the preprocessed model. The results of different instances showed the effectiveness of the proposed model and the solving method.
Key words: bus timetablinguneven headwaytransfer waiting timemixed integer programming modelpreprocessing approach 高效的公交系统不仅节省运营成本,还能吸引更多的乘客选择公交出行,从而缓解交通拥堵.公交规划是提高公交系统效率的重要手段之一,它包括4个子问题: 线路设计、 时刻表设计、 车辆调度及司售人员调度[1, 2].公交网络时刻表设计是公交规划过程中最为关键和复杂的问题之一.它确定各线路车次从始发站的发车时间,使不同线路的车辆协同到达换乘站点,以便乘客及时换乘.如果设计的时刻表没有使车辆协同到达换乘站点,必造成较长的乘客换乘等待时间[3].这将降低乘客对公交服务质量的满意度,导致有些乘客放弃公交出行.
因此,公交网络时刻表设计问题受到了学者们的极大关注.Cevallos等[4]构建了固定发车间隔下的公交时刻表设计问题的整数规划模型.Shafhi等[5]提出了一个更加实际的固定发车间隔下的公交时刻表设计问题,给出了乘客平均换乘等待时间的数学表达式，构建了以乘客总换乘等待时间最小为目标的混合整数规划模型.Ceder等[6]以最大化车辆协同到达换乘站点次数为目标,建立了求解不均匀发车间隔下的公交网络时刻表问题的混合整数规划模型.Eranki[7]将车辆协同方式重新定义为不同线路的车辆到达换乘站点的时间差在一个给定的时间窗内.Ibarra-Rojas等[8]在文献[6, 7]的基础上,建立了一个以车辆协同到达换乘站点次数最大为优化目标的混合整数规划模型.Parbo等[9]研究了固定发车间隔下的双层公交时刻设计问题.Wu等[10]研究了车辆随机行驶时间情况下的公交网络时刻表设计问题.然而,未见有文献同时考虑不均匀发车间隔和以最小化乘客总换乘等待时间为目标的公交网络时刻表设计问题.该问题的难点是如何使用数学表达式精确描述不均匀发车间隔下乘客的换乘等待时间.本文考虑同时具有这些特征的公交网络时刻表设计问题,定义了车辆在换乘站点的灵活协同方式; 构建了求解该问题的混合整数规划模型; 设计了求解该模型的预处理方法.通过计算不同的算例,验证了求解方法和模型的有效性.
1 问题描述在一个公交网络中,乘客出行经常面临换乘的情况.在某时段内,每条线路具有固定的发车车次,相邻车次发车间隔具有最小值和最大值.本文研究的问题是如何设计各线路车次的发车时间,从而使乘客在换乘站点经历较短的换乘时间.为避免不同线路的车辆在换乘站点发生串车现象[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 |
2 考虑不均匀发车间隔的公交网络时刻表设计模型2.1 问题假设1) 仅考虑网络中的换乘站点:对任意站点,车次从始发站到该站点的运行时间等于该路段站点间的运行时间和在各站点停留时间之和.
2) 仅考虑计划阶段的时刻表设计问题:在计划时间段内车辆在站点间的运行时间是固定的; 不考虑随机的车辆行驶时间.
3) 在计划时间段内,乘客的需求是均匀的.
2.2 数学符号1) 索引集:i,j为线路的索引集; p,q为车次的索引集; b为换乘站点的索引集; I为线路集合; Ji为与线路i在换乘站点存在车次协同的线路集合; Bij为线路i∈I和j∈Ji的车辆所经过换乘站点的集合.
2) 参数:T为计划时段长度,则计划时间段可标准化为[0,T]; Fi为线路i的发车次数; Hmini为线路i的最小发车间隔; Hmaxi为线路i的最大发车间隔; tbi为线路i到换乘站点b的行驶时间; M为一个较大的正数; wb为车辆在换乘站点b协同时间窗的下界; Wb为车辆在换乘站点b协同时间窗的上界或最大换乘等待时间; Ppbij为在换乘站点b,从线路i的第p个车次换乘到线路j的平均乘客数.
3) 决策变量:Xpi为线路i的第p个车次从始发站的发车时间; Ypqbij为在换乘站点b,乘客是否能从线路i的第p个车次换乘到线路j的第q个车次,如果是,则Ypqbij=1; 否则为0.
4) 变量:WTpqbij为在换乘站点b,乘客从线路i的第p个车次换乘到线路j的第q个车次的等待时间.
2.3 车辆灵活协同方式的定义假设乘客从线路i的第p个车次换乘到线路j的某个车次，图 2定义了两线路的车辆到达换乘站点的灵活协同方式.线路i的第p个车次到达换乘站点b的时刻为8:13,线路j的第q个车次到达换乘站点b的时刻为8:15.这两个车次到达换乘站点b的时间间隔为2 min,在时间窗[wb,Wb]=[2,6]内,所以线路i的第p个车次上的乘客可以换乘到线路j的第q个车次,且换乘等待时间为2 min (小于Wb).如果线路j的第q个车次到达换乘站点b的时间与线路i的第p个车次到达换乘站点b的时间间隔在时间窗[wb,Wb]=[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 ofbuses arriving at transfer node |
2.4 换乘等待时间的数学描述本文将乘客等待第一个可换乘车次的时间作为换乘等待时间,并且乘客只能换乘到一个车辆.图 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的车次.如果(Xqj+tbj)-(Xpi+tbi)≥wb,则Ypqbij=1,否则Ypqbij=0.结合图 3可以得出Ypqbij=1,Yp1bij=0,…,Yp(q-1)bij=0和Yp(q+1)bij=1,…,YijpFjb=1.在不等式(1)~(3)和最小化目标函数的共同作用下,将使得WTpqbij=(Xqj+tbj)-(Xpi+tbi),线路i的第p个车次换乘到线路j其他车次的等待时间为零.不等式(4)为换乘等待时间不大于Wb.因此,不等式(1)~(4)准确地描述了乘客的换乘等待时间.
2.5 数学模型以最小化乘客总换乘等待时间为目标的混合整数规划模型P:
式中：i∈I,j∈Ji,b∈Bij,p∈{1,…,Fi},q∈{1,…,Fj},目标函数(5)是最小化乘客总换乘等待时间; 约束(6)表示线路的第一个车次的发车时间分布在计划时间段的前面部分; 约束(7)表示线路的最后一个车次的发车时间分布在计划时间段的后面部分; 约束(8)表示相邻车次的发车时间间隔满足最小和最大发车间隔要求; 约束(9)定义乘客的换乘等待时间; 约束(10)为决策变量的取值范围.3 模型分析3.1 计算复杂性Odijk[11]研究了固定发车间隔下的公交网络时刻表设计问题的一个特例，通过类比顶点着色(vertex-coloring)问题,证明了该时刻表设计问题是NP-complete问题.Ibarra-Rojas[8]进一步证明了不固定发车间隔下,以最大化车辆协同达到换乘站点次数的公交时刻表设计问题是NP-hard问题.所以,本文研究的考虑不均匀发车间隔和以乘客换乘总等待时间最小为目标的公交时刻表设计问题是一个NP-hard问题.
3.2 解的空间特征基于文献[8]的思路,通过对模型P中约束(6)~(8)的分析,得到线路各车次发车时间Xpi的发车时间窗.分析步骤如下:
步骤1 设线路i的第一个车次发车时间为零时刻,即X1i=0,则线路i的第p个车次的最早发车时间为(p-1)Hmini;
步骤2 设线路i的第一个车次X1i=Hmaxi,则线路i的第p个车次的最晚发车时间为min{T,pHmaxi};
步骤3 设线路i的最后一个车次XiFi=T-Hmaxi,则线路i的第p个车次的最早发车时间为max{0,T-(Fi-(p-1))Hmaxi};
步骤4 设线路i的最后一个车次XiFi=T，则线路i的第p个车次的最晚发车时间为T-(Fi-p)Hmini.
因此,可以得到线路i的第p个车次Xpi的发车时间窗Dpi为
那么,线路i的第p+1个车次的发车时间与Xpi的关系可以描述为
定义线路i的第p个车次到达换乘站点b的到达时间的时间窗Apbi为
如果线路i的第p个车次要与线路j的第q个车次满足2.3定义的灵活协同换乘,则线路j的第q个车次的发车时间要满足
定义Spbi= [left(Apbi)+wb;right(Apbi)+Wb]为与线路i的第p个车次在换乘站点b满足灵活协同到达的时间窗.根据公式(11)~(13),公式(14)可以推广为
基于以上分析,结合不等式(1)~(3)和约束(6)~(8),线路i的第一个车次不可能与线路j的最后一个车次协同到达.如果线路i的第p个车次可以换乘到线路j的第q个车次,即Ypqbij=1,则Yp(q+1)bij=1,…,YijpFjb=1.因此,得到Ypqbij具有图 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.3 预处理方法基于3.2节的分析,算法1计算每个车次所有可行的发车时间、 到站时间和协同到达时间窗.根据公式(15),删除每对不可能协同到达的两车次对应的决策变量和约束,从而缩减了问题的求解空间.
算法1 预处理方法 (模型P)
4 计算结果及分析4.1 实验算例采用算例的参数设置如下: T=200 min,3条线路,每条线路的发车次数Fi=20,3个换乘站点,线路1和线路2分别在换乘站点1和2相互换乘; 线路1和线路3在换乘站点3相互换乘.每个站点的协同时间窗为[wb,Wb]=[2,6],线路始发站到换乘站点的车辆行驶时间在[1,20]范围内产生.为了与文献[8]中模型相比较,设Ppbij=1.每个算例的参数[Hmini;Hmaxi]取值不同.在Visual Studio 2008编译环境下,C#语言编写预处理方法和调用CPLEX 12.4求解模型.除了计算时间设为1 800 s外,其他参数为默认设置.
4.2 结果分析分别求解模型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
| 表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
| 表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
| 表3 采用分支定界算法求解文献[8]的模型 Table 3 Results of model in literature [8] solved by branch and bound algorithm |
5 结 论本文研究了不均匀发车间隔情况下的公交网络时刻表设计问题,构建了以乘客总换乘等待时间最小化为目标的混合整数规划模型,分析了求解模型的复杂性和可行解的空间结构.基于模型特征分析,设计了缩减求解空间的预处理方法.通过计算不同算例,验证了求解方法和模型的有效性.本文以乘客总换乘等待时间最小为目标的模型比文献中以最大车辆协同到达换乘站点次数为目标的模型更有效.设计有效求解大规模问题的算法是今后的研究方向之一.
参考文献
| [1] | Ceder A.Public transit planning and operation:theory,modeling and practice[M].Oxford:Elsevier,2007.( 1) |
| [2] | Desaulniers G,Hickman M.Public transit[J].Handbooks in Operation Research and Management Science,2007,14:69-120.(1) |
| [3] | Wong R C W,Yuen T W Y.Optimizing timetable synchroni-zation for rail mass transit[J].Transportation Science,2008,42 (1):57-69.(1) |
| [4] | Cevallos F,Zhao F.Minimizing transfer times in public transit network with genetic algorithm[J].Transportation Research Record,2006,1971:74-79.(1) |
| [5] | Shafhi Y,Khani A.A practical model for transfer optimization in a transit network:model formulations and solutions[J].Transportation Research Part A:Policy and Practice,2010,44(6):377-389.(1) |
| [6] | Ceder A,Golany B,Tal O.Creating bus timetable with maximal synchronization[J].Transportation Research Part A:Policy and Practice,2001,25(10):913-928.(2) |
| [7] | Enraki A.A model to create bus timetable to attain maximum synchronization considering waiting times at transfer stops[D].Tampa:University of South Florida,2004.(2) |
| [8] | Ibarra-Rojas O J,Rios-Solis Y A.Synchronization of bus timetabling[J].Transportation Research Part B:Methodological,2012,46 (5):599-614.(7) |
| [9] | Parbo J .User perspectives in public transport timetable optimization[J].Transportation Research Part C:Emerging Technologies,2014,48:269-284.(1) |
| [10] | Wu Y H,Tang J F,Yu Y,et al.A stochastic optimization model for transit network timetable design to mitigate the randomness of traveling time by adding slack time[J].Transportation Research Part C:Emerging Technologies,2015,52:15-31.(1) |
| [11] | Odijk M A.A constraint generation algorithm for the construction of periodic railway timetables[J].Transportation Research Part B:Methodological,1996,30 (6):455-464.(1) |
本文献在全文中的定位：
... ,它包括4个子问题: 线路设计、 时刻表设计、 车辆调度及司售人员调度[1, 2].公交网络时刻表设计是公交规划过 ...
1
本文献在全文中的定位：
... 表设计、 车辆调度及司售人员调度[1, 2].公交网络时刻表设计是公交规划过程中最为关键和复杂的问题之一.它 ...
1
本文献在全文中的定位：
... 的时刻表没有使车辆协同到达换乘站点,必造成较长的乘客换乘等待时间[3].这将降低乘客对公交服务质量的满意度,导致有些乘客放弃公交出 ...
1
本文献在全文中的定位：
... 此,公交网络时刻表设计问题受到了学者们的极大关注.Cevallos等[4]构建了固定发车间隔下的公交时刻表设计问题的整数规划模型.Shafhi ...
1
本文献在全文中的定位：
... 了固定发车间隔下的公交时刻表设计问题的整数规划模型.Shafhi等[5]提出了一个更加实际的固定发车间隔下的公交时刻表设计问题,给出了 ...
2
本文献在全文中的定位：
... ，构建了以乘客总换乘等待时间最小为目标的混合整数规划模型.Ceder等[6]以最大化车辆协同到达换乘站点次数为目标,建立了求解不均匀发车间 ...
... 的时间窗内.Ibarra-Rojas等[8]在文献[6, 7]的基础上,建立了一个以车辆协同到达换 ...
2
本文献在全文中的定位：
... 求解不均匀发车间隔下的公交网络时刻表问题的混合整数规划模型.Eranki[7]将车辆协同方式重新定义为不同线路的车辆到达换乘站点的时间差在一 ...
... 在文献[6, 7]的基础上,建立了一个以车辆协同到达换乘站点次数最大为优化目标的混合 ...
7
本文献在全文中的定位：
... 同线路的车辆到达换乘站点的时间差在一个给定的时间窗内.Ibarra-Rojas等[8]在文献 ...
... 点经历较短的换乘时间.为避免不同线路的车辆在换乘站点发生串车现象[8],乘客要换乘的车辆与乘客先前乘坐的车辆先后到达换乘站点的时间间 ...
... 色(vertex-coloring)问题,证明了该时刻表设计问题是NP-complete问题.Ibarra-Rojas[8]进一步证明了不固定发车间隔下,以最大化车辆协同达到换乘站点次数 ...
... 基于文献[8]的思路,通过对模型P中约束(6)~(8)的分析,得到线路各车次发车时 ...
... 始发站到换乘站点的车辆行驶时间在[1,20]范围内产生.为了与文献[8]中模型相比较,设Ppbij=1.每个算例的参 ...
... 是求解模型P和文献[8]中模型的结果.从 ...
... 采用分支定界算法求解文献[8]的模型 ...
1
本文献在全文中的定位：
... 车辆协同到达换乘站点次数最大为优化目标的混合整数规划模型.Parbo等[9]研究了固定发车间隔下的双层公交时刻 ...
1
本文献在全文中的定位：
... 了固定发车间隔下的双层公交时刻设计问题.Wu等[10]研究了车辆随机行驶时间情况下的公交网络时刻表设计问题.然而,未见 ...
1
本文献在全文中的定位：
... Odijk[11]研究了固定发车间隔下的公交网络时刻表设计问题的一个特例，通过类 ...
