Synchronization of bus timetabling
Synchronization of bus timetabling
复制标题
DOI：
10.1016/j.trb.2012.01.006
复制
发表时间：
2012-06-01
影响因子：
6.8
通讯作者：
Rios-Solis, Yasmin A.
中科院分区：
文献类型：
--
作者：
Ibarra-Rojas, Omar J.;Rios-Solis, Yasmin A.
时刻表生成是公交线网战略规划中的一个子问题，其目的是确定每一次出行的发车时间。我们研究了墨西哥蒙特雷的公交网络，它与拉丁美洲其他城市的公交网络相似。这是一个大型的公交网络，乘客换乘必须受到青睐，几乎均匀间隔的发车是寻求，必须避免不同线路的公交车聚集。我们制定了这个网络的调度问题的目标是最大限度地提高同步的数量，以方便乘客转移，并避免巴士束沿着网络。我们将这些同步定义为在一个时间窗口内具有分离时间的两次旅行的到达，以进行灵活的表述。这种灵活性是公交网络的一个关键方面，因为旅行时间会因驾驶员速度、交通拥堵和事故等原因而变化。通过证明我们的问题是NP难的，我们回答了一个10年前的公开问题，即文献中类似问题的NP难性。接下来，我们分析了我们的模型的可行解空间的结构特性。这种分析导致了一个预处理阶段，消除了许多决策变量和约束。此外，这种预处理定义了可行的同步和到达时间窗口，用于一个新的元启发式算法。实证实验表明，我们提出的算法可以在不到一分钟的时间内获得实际大小实例的高质量解决方案。(C)2012爱思唯尔有限公司保留所有权利。
Timetable generation is a subproblem of bus network strategic planning, in which the departure time of each trip is determined. We study the bus network of Monterrey, Mexico, which is similar to those of other cities in Latin America. It is a large bus network where passenger transfers must be favored, almost evenly spaced departures are sought, and bus bunching of different lines must be avoided. We formulate the timetabling problem of this network with the objective of maximizing the number of synchronizations to facilitate passenger transfers and avoid bus bunching along the network. We define these synchronizations as the arrivals of two trips with a separation time within a time window to make a flexible formulation. This flexibility is a critical aspect for the bus network, since travel times vary because of reasons such as driver speed, traffic congestion, and accidents. By proving that our problem is NP-hard we answer a 10-year-old open question about the NP-hardness of similar problems present in literature. Next, we analyze the structural properties of the feasible solution space of our model. This analysis leads to a preprocessing stage that eliminates numerous decision variables and constraints. Moreover, this preprocessing defines feasible synchronization and arrival time windows that are used in a new metaheuristic algorithm. Empirical experimentation shows that our proposed algorithm obtains high-quality solutions for real-size instances in less than one minute. (C) 2012 Elsevier Ltd. All rights reserved.