Within day rescheduling microsimulation combined with macrosimulated traffic

The concept of rescheduling is essential to activity-based modeling in order to calculate effects of both unexpected incidents and adaptation of individuals to traffic demand management measures. When collaboration between individuals is involved or timetable based public transportation modes are chosen, rescheduling becomes complex. This paper describes a new framework to investigate algorithms for rescheduling at a large scale. The framework allows to explicitly model the information flow between traffic information services and travelers. It combines macroscopic traffic assignment with microscopic simulation of agents adapting their schedules. Perception filtering is introduced to allow for traveler specific interpretation of perceived macroscopic data and for information going unnoticed; perception filters feed person specific short term predictions about the environment required for schedule adaptation. Individuals are assumed to maximize schedule utility. Initial agendas are created by the FEATHERS activity-based schedule generator for mutually independent individuals using an undisturbed loaded transportation network. The new framework allows both actor behavior and external phenomena to influence the transportation network state; individuals interpret the state changes via perception filtering and start adapting their schedules, again affecting the network via updated traffic demand. The first rescheduling mechanism that has been investigated uses marginal utility that monotonically decreases with activity duration and a monotonically converging relaxation algorithm to efficiently determine the new activity timing. The current framework implementation is aimed to support re-timing, re-location and activity re-sequencing; re-routing at the level of the individual however, requires microscopic travel simulation.     

A parallel algorithm for train rescheduling

One of the crucial factors in achieving a high punctuality in railway traffic systems, is the ability to effectively reschedule the trains when disturbances occur. The railway traffic rescheduling problem is a complex task to solve both from a practical and a computational perspective. Problems of practically relevant sizes have typically a very large search space, making them time-consuming to solve even for state-of-the-art optimization solvers. Though competitive algorithmic approaches are a widespread topic of research, not much research has been done to explore the opportunities and challenges in parallelizing them. This paper presents a parallel algorithm to efficiently solve the real-time railway rescheduling problem on a multi-core parallel architecture. We devised (1) an effective way to represent the solution space as a binary tree and (2) a novel sequential heuristic algorithm based on a depth-first search (DFS) strategy that quickly traverses the tree. Based on that, we designed a parallel algorithm for a multi-core architecture, which proved to be 10.5 times faster than the sequential algorithm even when run on a single processing core. When executed on a parallel machine with 8 cores, the speed further increased by a factor of 4.68 and every disturbance scenario in the considered case study was solved within 6 s. We conclude that for the problem under consideration, though a sequential DFS approach is fast in several disturbance scenarios, it is notably slower in many other disturbance scenarios. The parallel DFS approach that combines a DFS with simultaneous breadth-wise tree exploration, while being much faster on an average, is also consistently fast across all scenarios.     

Rescheduling through stop-skipping in dense railway systems

Based on the analysis of the railway system in the Paris region in France, this paper presents a rescheduling problem in which stops on train lines can be skipped and services are retimed to recover when limited disturbances occur. Indeed, in such mass transit systems, minor disturbances tend to propagate and generate larger delays through the shared use of resources, if no action is quickly taken. An integrated Integer Linear Programming model is presented whose objective function minimizes both the recovery time and the waiting time of passengers. Additional criteria related to the weighted number of train stops that are skipped are included in the objective function. Rolling-stock constraints are also taken into account to propose a feasible plan. Computational experiments on real data are conducted to show the impact of rescheduling decisions depending on key parameters such as the duration of the disturbances and the minimal turning time between trains. The trade-off between the different criteria in the objective function is also illustrated and discussed.