ATMOS 2020 Accepted Papers with Abstracts

Abstract: We study the one-to-many journey planning problem in multi-modal transportation networks consisting of a public transit network and an additional, non-schedule-based mode of transport. Given a departure time and a single source vertex, we aim to compute optimal journeys to all vertices in a set of targets, optimizing both travel time and the number of transfers used. Solving this problem yields a crucial component in many other problems, such as efficient point-of-interest queries, computation of isochrones, or multi-modal traffic assignments. While many algorithms for multi-modal journey planning exist, none of them are applicable to one-to-many scenarios. Our solution is based on the combination of two state-of-the-art approaches: ULTRA, which enables efficient journey planning in multi-modal networks, but only for one-to-one queries, and (R)PHAST, which enables efficient one-to-many queries, but only in time-independent networks. Similarly to ULTRA, our new approach can be combined with any existing public transit algorithm that allows a search to all stops, which we demonstrate for CSA and RAPTOR. For small to moderately sized target sets, the resulting algorithms are nearly as fast as the pure public transit algorithms they are based on. For large target sets, we achieve a speedup of up to 7 compared to a naive one-to-many extension of a state-of-the-art multi-modal approach.

Abstract: The BahnCard problem is an important problem in the realm of online decision making. In its original form, there is one kind of BahnCard associated with a certain price, which upon purchase reduces the ticket price of train journeys for a certain factor over a certain period of time. The problem consists of deciding on which dates BahnCards should be purchased such that the overall cost, that is, BahnCard prices plus (reduced) ticket prices, is minimized without having knowledge about the number and prices of future journeys. In this paper, we extend the problem such that multiple kinds of BahnCards are available for purchase. We provide an optimal offline algorithm, as well as online strategies with provable competitiveness factors. Furthermore, we describe and implement several heuristic online strategies and compare their competitiveness in realistic scenarios.

Abstract: We propose an additional preprocessing step for the Trip-Based Public Transit Routing algorithm, an exact state-of-the art algorithm for bi-criteria min cost path problems in public transit networks. This additional step reduces significantly the preprocessing time, while preserving the correctness and the computation times of the queries. We test our approach on three large scale networks and show that the improved preprocessing is compatible with frequent real-time updates, even on the larger data set. The experiments also indicate that it is possible, if preprocessing time is an issue, to use the proposed preprocessing step on its own to obtain already a significant reduction of the query times compared to the no pruning scenario.

Abstract: We study a bi-modal journey planning scenario consisting of a public transit network and a transfer graph representing a secondary transportation mode (e.g., walking or cycling). Given a pair of source and target locations, the objective is to find a Pareto set of journeys optimizing arrival time and the number of required transfers. For public transit networks with a restricted, transitively closed transfer graph, one of the fastest known algorithms solving this bi-criteria problem is Trip-Based Routing. However, it cannot be trivially extended to unrestricted transfer graphs. In this work, we combine Trip-Based Routing with ULTRA, a preprocessing technique that allows any public transit algorithm to handle an unrestricted transfer graph. Since both ULTRA and Trip-Based Routing precompute transfer shortcuts in a preprocessing phase, a naive combination of the two leads to a three-phase algorithm that performs redundant work and produces superfluous shortcuts. We therefore propose a new, integrated preprocessing phase that combines the advantages of both and reduces the number of computed shortcuts by up to a factor of 9 compared to a naive combination. The resulting query algorithm, ULTRA-Trip-Based is the fastest known algorithm for the considered problem setting, achieving a speedup of up to 4 compared to the fastest previously known approach, ULTRA-RAPTOR.

Abstract: We investigate polyhedral aspects of the Periodic Event Scheduling Problem (PESP), the mathematical basis for periodic timetabling problems in public transport. Flipping the orientation of arcs, we obtain a new class of valid inequalities, the flip inequalities, comprising both the known cycle and change-cycle inequalities. For a point of the LP relaxation, a violated flip inequality can be found in pseudo-polynomial time, and even in linear time for a spanning tree solution. Our main result is that the integer vertices of the polytope described by the flip inequalities are exactly the vertices of the PESP polytope, i.e., the convex hull of all feasible periodic slacks with corresponding modulo parameters. Moreover, we show that this flip polytope equals the PESP polytope in some special cases. On the computational side, we devise several heuristic approaches concerning the separation of cutting planes from flip inequalities. These produce better dual bounds for the smallest and largest instance of the benchmarking library PESPlib.

Abstract: When evaluating the operational costs of a public transport system, the most important factor is the number of vehicles needed for operation. We consider a sequential approach where a vehicle schedule is determined for a given line plan and only afterwards a timetable is fixed and compare this 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.

Abstract: In this paper, we analyze a family of formulations for the Cyclic Crew Rostering Problem (CCRP), in which a cyclic roster has to be constructed for a group of employees. Each formulation in the family is based on a partition of the roster. Intuitively, finer partitions give rise to a formulation with fewer variables, but possibly more constraints. Coarser partitions lead to more variables, but might allow to incorporate many of the constraints implicitly. We derive analytical results regarding the relative strength of the different formulations, which can serve as a guideline for formulating a given problem instance. Furthermore, we propose a column generation approach, and use it to compare the strength of the formulations empirically. Both the theoretical and computational results demonstrate the importance of choosing a suitable formulation. In particular, for practical instances of Netherlands Railways, stronger lower bounds are obtained, and more than 90% of the roster constraints can be modeled implicitly.

Abstract: We present a new method for computing a set of alternative origin-to-destination routes in road networks with an underlying time-dependent metric. The resulting set is aggregated in the form of a time-dependent alternative graph and is characterized by minimum route overlap, small stretch factor, small size and low complexity.

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.

Abstract: We incorporate turn restrictions and turn costs into the route planning algorithm customizable contraction hierarchies (CCH). There are two common ways to represent turn costs and restrictions. The edge-based model expands the network so that road segments become vertices and allowed turns become edges. The compact model keeps intersections as vertices, but associates a turn table with each vertex. Although CCH can be used as is on the edge-based model, the performance of preprocessing and customization is severely affected. While the expanded network is only three times larger, both preprocessing and customization time increase by up to an order of magnitude. In this work, we carefully engineer CCH to exploit different properties of the expanded graph. We reduce the increase in customization time from up to an order of magnitude to a factor of about 3. The increase in preprocessing time is reduced even further. Moreover, we present a CCH variant that works on the compact model, and show that it performs worse than the variant on the edge-based model. Surprisingly, the variant on the edge-based model even uses less space than the one on the compact model, although the compact model was developed to keep the space requirement low.

Abstract: Traditional navigation services find the fastest route for a single driver. Though always using the fastest route seems desirable for every individual, selfish behavior can have undesirable effects such as higher energy consumption and avoidable congestion, even leading to higher overall and individual travel times. In contrast, strategic routing aims at optimizing the traffic for all agents regarding a global optimization goal. We introduce a framework to formalize real-world strategic routing scenarios as algorithmic problems and study one of them, which we call Single Alternative Path (SAP), in detail. There, we are given an original route between a single origin-destination pair. The goal is to suggest an alternative route to all agents that optimizes the overall travel time under the assumption that the agents distribute among both routes according to a psychological model, for which we introduce the concept of Pareto-conformity. We show that the SAP problem is NP-complete, even for such models. Nonetheless, assuming Pareto-conformity, we give multiple algorithms for different variants of SAP, using multi-criteria shortest path algorithms as subroutines. Moreover, we prove that several natural models are in fact Pareto-conform. The implementation and evaluation of our algorithms serve as a proof of concept, showing that SAP can be solved in reasonable time even though
the algorithms have exponential running time in the worst case.

Abstract: This paper deals with the computation of d-dimensional multicriteria shortest paths. In a weighted graph with arc weights represented by vectors, the cost of a path is the vector sum of the weights of its arcs. For a given pair consisting of a source s and a destination t, a path P dominates a path Q if and only if P’s cost is component-wise smaller than or equal to Q’s cost. The set of Pareto paths, or Pareto set, from s to t is the set of paths that are not dominated. The computation time of the Pareto paths can be prohibitive whenever the set of Pareto paths is large.
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.

Abstract: In this paper we consider the integration of the staff scheduling into planning railway yards. This involves an extension of the Train Unit Shunting Problem, in which a conflict-free schedule of all activities at the yard has to be constructed. As the yards often consist of several kilometers of railway track, the main challenge in finding efficient staff schedules arises from the potentially large walking distances between activities.

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.

Abstract: When determining the paths of the passengers in public transportation, the travel time is usually the main criterion. However, also the ticket price a passenger has to pay is a relevant factor for choosing the path. This not only concerns the passengers themselves, but is also an important issue for simulating how much is paid in large transport networks in order to divide the income among several public transport companies.

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.

Abstract: Planning a tourist trip in a foreign city can be a complex undertaking: when selecting the attractions and choosing visit order and visit durations, opening hours as well as the public transit timetable need to be considered. Additionally, when planning trips for multiple days, it is desirable to avoid redundancy. Since the attractiveness of activities such as shopping or sightseeing depends on personal preferences, there is no one-size-fits-all solution to this problem. We propose several realistic extension to the Time-Dependent Team Orienteering Problem with Time Windows (TDTOPTW) which are relevant in practice and present the first MILP representation of it. Furthermore, we propose a problem-specific preprocessing step which enables fast heuristic (ILS) and exact (MILP) personalized trip-planning for tourists. Experimental results for the city of Berlin show that the approach is feasible in practice.

Abstract: We consider a basic vehicle scheduling problem that arises in the context of travel demand models: Given demanded vehicle trips, what is the minimal number of vehicles needed to fulfill the demand? In this paper, we model the vehicle scheduling problem as a network flow problem. Since instances arising in the context of travel demand models are often so big that the network flow model becomes intractable, we propose using a rolling horizon heuristic to split huge problem instances into smaller subproblems and solve them independently to optimality. By letting the horizons of the subproblems overlap, it is possible to look ahead to the demand of the next subproblem. We prove that composing the solutions of the subproblems yields an optimal solution to the whole problem if the overlap of the horizons is sufficiently large. Our experiments show that this approach is not only suitable for solving extremely large instances that are intractable as a whole, but it is also possible to decrease the solution time for large instances compared to a comprehensive approach.

Abstract: Railway systems are often highly utilized, which makes them vulnerable to delay propagation. In order to minimize delays timetables are desired to be robust, a property that is often estimated by simulating the respective timetable for different deterministic delay values. To achieve an accurate estimation under consideration of uncertain delays many simulation runs need to be executed. Most established simulation systems additionally use microscopic models of the railway systems, which
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.

Abstract: We consider a combined system of regular delivery trucks and crowdsourced drones to provide a technology-assisted crowd-based last-mile delivery experience. We develop analytical models and methods for a system in which package delivery is performed by a big truck carrying a large number of packages to a neighborhood or a town in a metropolitan area and then assign the packages to crowdsourced drone operators to deliver them to their final destinations. A combination of heuristic algorithms is used to solve this NP-hard problem, computational results are presented, and an exhaustive sensitivity analysis is done to check the influence of different parameters and assumptions.