An Efficient Solution for One-to-Many Multi-Modal Journey Planning

On the Multi-Kind BahnCard Problem

Faster preprocessing for the Trip-Based Public Transit Routing algorithm

Integrating ULTRA and Trip-Based Routing

Determining all integer vertices of the PESP polytope by flipping arcs

A New Sequential Approach to Periodic Vehicle Scheduling and Timetabling

Analyzing a family of formulations for cyclic crew rostering

Time-Dependent Alternative Route Planning

To our knowledge, this is the first work that deals with the time-dependent setting in the framework of alternative routes.

Based on preprocessed minimum travel-time information between a small set of nodes and all other nodes in the graph, our algorithm carries out a collection phase for candidate alternative routes, followed by a pruning phase that cautiously discards uninteresting or low-quality routes from the candidate set.

Our experimental evaluation on real time-dependent road networks demonstrates that the new algorithm performs much better (by one or two orders of magnitude) than existing baseline approaches.

In particular, the entire alternative graph can be computed in less than $0.384$sec for the road network of Germany, and in less than $1.24$sec for that of Europe. TDAG also provides ``quick-and-dirty'' results of descent quality, in about 1/300 of the above mentioned query times for continental-size instances.

Customizable Contraction Hierarchies with Turn Costs

A Strategic Routing Framework and Algorithms for Computing Alternative Paths

the algorithms have exponential running time in the worst case.

Framing Algorithms for Approximate Multicriteria Shortest Paths

We propose in this article new algorithms to compute approximated Pareto paths in any dimension. For d = 2, we exhibit the first approximation algorithm, called Frame, whose output is guaranteed to be always a subset of the Pareto set. Finally, we provide a small experimental study in order to confirm the relevance of our Frame algorithm.

Personnel Scheduling on Railway Yards

We present two efficient heuristics for staff assignment. These methods are integrated into a local search framework to find feasible solutions to the Train Unit Shunting Problem with staff requirements. To the best of our knowledge, this is the first algorithm to solve the complete version of this problem. Additionally, we propose a dynamic programming method to assign staff members as passengers to train movements to reduce their walking time. Furthermore, we describe a branch and price procedure that constructs an optimal robust staff assignment. We use this algorithm to evaluate the quality of the solutions produced by the heuristics.

On a set of 300 instances of the train unit shunting problem with staff scheduling on a real-world railway yard, the best-performing heuristic integrated into the local search approach solves 97% of the instances within three minutes on average.

Cheapest Paths in Public Transport: Properties and Algorithms

However, finding the correct price depends on the fare system used (e.g., distance tariff, zone tariff with different particularities, application of short-distance tariff, etc.) and may be rather complicated even if the path is already fixed. An algorithm which finds a cheapest path in a very general case has been provided in \cite{EulBorn19}, but its running time is exponential. In this paper we model and analyze different fare systems, identify important properties they may have and provide polynomial algorithms for computing a cheapest path.

Time-Dependent Tourist Tour Planning with Adjustable Profits

A rolling horizon heuristic with optimality guarantee for an on-demand vehicle scheduling problem

Probabilistic Simulation of a Railway Timetable

further increases the simulations running times and makes them applicable rather for small areas of interest for complexity reasons.

In this paper, we present a probabilistic simulation algorithm for given timetables using a macroscopic model of the railway infrastructure. This way we consider the railway systems in less detail but are able to examine certain performance indicators for larger areas. We implement the algorithm, examine its results, and discuss possible improvements of this approach.

Crowdsourced Delivery with Drones in Last Mile Logistics