Railway systems occasionally get into a state of being out-of-control, meaning that barely any train is running, even though the required resources (infrastructure, rolling stock and crew) are available. Because of the large number of affected resources and the absence of detailed, timely and accurate information, currently existing disruption management techniques cannot be applied in out-of-control situations. Most of the contemporary approaches assume that there is only one single disruption with a known duration, that all information about the resources is available, and that all stakeholders in the operations act as expected. Another limitation is the lack of knowledge about why and how disruptions accumulate and whether this process can be predicted. To tackle these problems, we develop a multidisciplinary framework combining techniques from complexity science and operations research, aiming at reducing the impact of these situations and—if possible—avoiding them. The key elements of this framework are (i) the generation of early warning signals for out-of-control situations, (ii) isolating a specific region such that delay stops propagating, and (iii) the application of decentralized decision making, more suited for information-sparse out-of-control situations.

Oct 2021

EP*

A self-organizing policy for vehicle dispatching in public transit systems with multiple lines

From time to time, large disruptions cause heavily utilized railway networks to get into a state of out-of-control, in which hardly any trains are able to run as the result of a lack of accurate and up-to-date information available to dispatchers. In this paper, we develop and test disruption management strategies for dealing with these situations. First, we propose an algorithm that finds an alternative line plan that can be operated in the affected part of the railway network. As the line plan should be feasible with respect to infrastructural and resource restrictions, we integrate these aspects in the algorithm in a Benders-like fashion. Second, to operate the railway system within the disrupted region, we propose several local train dispatching strategies requiring varying degrees of flexibility and coordination. Computational experiments based on disruptions in the Dutch railway network indicate that the algorithm performs well, finding workable and passenger-oriented line plans within a couple of minutes. Moreover, we also demonstrate in a simulation study that the produced line plans can be operated smoothly without depending on central coordination.

Oct 2020

A New Sequential Approach to Periodic Vehicle Scheduling and Timetabling

Paul Bouman,

Alexander Schiewe,

and Philine Schiewe

In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

When evaluating the operational costs of a public transport system, the most important factor is the number of vehicles needed for operation. In contrast to the canonical sequential approach of first fixing a timetable and then adding a vehicle schedule, we consider a sequential approach where a vehicle schedule is determined for a given line plan and only afterwards a timetable is fixed. We compare this new sequential approach to a model that integrates both steps. To represent various operational requirements, we consider multiple possibilities to restrict the vehicle circulations to be short, as this can provide operational benefits. The sequential approach can efficiently determine public transport plans with a low number of vehicles. This is evaluated theoretically and empirically demonstrated for two close-to real-world instances.

Oct 2018

Vehicle Scheduling Based on a Line Plan

Rolf N. van Lieshout,

and Paul C. Bouman

In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

We consider the following problem: given a set of lines in a public transportation network with their round trip times and frequencies, a maximum number of vehicles and a maximum number of lines that can be combined into a vehicle circulation, does there exist a set of vehicle circulations that covers all lines given the constraints. Solving this problem provides an estimate of the costs of operating a certain line plan, without having to compute a timetable first. We show that this problem is NP-hard for any restriction on the number of lines that can be combined into a circulation which is equal to or greater than three. We pay special attention to the case where at most two lines can be combined into a circulation, which is NP-hard if a single line can be covered by multiple circulations. If this is not allowed, a matching algorithm can be used to find the optimal solutions, which we show to be a 16/15-approximation for the case where it is allowed. We also provide an exact algorithm that is able to exploit low tree-width of the so-called circulation graph and small numbers of vehicles required to cover single circulations.

Oct 2018

Dynamic programming approaches for the traveling salesman problem with drone

During the past decades, the modelling of transport demand by activity based methods has gained considerable attention from the scientific community. Such demand models offer a greater modelling flexibility than traditional models, by modelling transport demand as a phenomenon which emerges from the desire to perform activities at different locations, as opposed to more traditional models where an origin destination demand matrix of trips is distributed over different routes and modes. One of the drawbacks of the activity based paradigm is that data related to activities is more difficult to collect than traffic counts. Modern technologies, such as smart card ticketing systems and smart phones, allow us to collect more detailed accounts of the movements of individual passengers. This gives us the possibility to analyse consecutive journeys and therefore the time a passenger spends in a certain location. This information can be very useful from an activity based modelling perspective. In this paper we take an exploratory approach to derive important activity time intervals from smart card data. We apply a clustering algorithm on the intervals observed at individual stations to detect which time intervals capture enough activities. We then construct a tree-based labelling algorithm that allows us to label the activities and analyse activity chains of individual passengers. We count pairs of consecutive activity labels, visualise the results as a network and calculate which triplets of consecutive activities occur most often. Using this approach, we are able to identify activity patterns that differ from the typical time windows associated with home-work activities.

Nov 2012

Recognizing Demand Patterns from Smart Card Data for Agent-Based Micro-simulation of Public Transport

Paul Bouman,

Milan Lovric,

Ting Li,

Evelien van der Hurk,

Leo Kroon,

and Peter Vervest

In Proceedings of the Seventh Workshop on Agents In Traffic and Transportation