Bus rescheduling in rolling horizons for regularity-based services

Document Type

Journal Article

Publication Date


Subject Area

place - north america, place - urban, mode - bus, technology - intelligent transport systems, operations - capacity, operations - scheduling


bus service regularity, combinatorial optimization, passenger excess waiting times, periodic rescheduling


Given the unstable nature of the bus operations, the regularity of the bus services cannot be maintained throughout the day. Especially in densely populated areas, the inherent variability of the trip travel times affects the regularity of the daily services since the arrival times of several trips at stops might oscillate significantly from their expected values. Because of the high level of uncertainty, this work proposes a periodic rescheduling of the dispatching times of the daily bus trips to adjust continuously to the operational changes. A key differentiator from previous works is that a periodic rescheduling does not focus only on the running buses, but also reschedules the dispatching times of all remaining daily trips while considering operational constraints related to layover times and capacity limits. Typical scheduling problems (such as a bus scheduling problem) are NP-hard because of the discrete nature of the decision variables. Hence, the computational burden prohibits their solution with analytical methods. Catering for capacity limits increases further the complexity of our problem because it results in a non-smooth objective function which is not differentiable at every point of its domain. For this reason, this work proposes a sequential hill climbing method to search the solution space more efficiently and reschedule the dispatching times of trips in near real time. This approach is tested using real-time data from bus line 15 L in Denver, USA. Critical issues, such as to what extent can the periodic dispatching time rescheduling improve the regularity of daily operations, are investigated.


Permission to publish the abstract has been given by Taylor&Francis, copyright remains with them.