IN – Track A

Project

IN-A1

Algebraic and Tropical Methods for Periodic Timetabling

Project Heads

Project Members

Niels Lindner (ZIB)

Project Duration

01.01.2020 – 31.12.2020

Located at

ZIB

Description

In particular, we will pursue the following research directions:

• Use linear algebra over Z/TZ (e.g., invoking Hermite and Smith normal forms) to parametrize the solution space for PESP and to explore new algorithmic perspectives.
• Find tropical interpretations of PESP beyond timetable stability analysis in the framework of the max-plus algebra.
• Investigate tropically inspired polyhedral decompositions of the space of periodic timetables and of passenger paths in integrated periodic timetabling and passenger routing, in order to understand routing structures in public transportation networks.

Background

Creating, optimizing and evaluating timetables is an indispensable task for public transport operators. For both local and long-distance traffic, timetables are often desired to be periodic, since this drastically reduces the size of the planning horizon and leads to recurring operational situations. The standard approach for the mathematical optimization of periodic timetables is the Periodic Event Scheduling Problem (PESP), which can be seen as a minimum cost network tension problem with additional modulo constraints reflecting the periodicity. More precisely, fixing a period time T, on a digraph (V, E) with incidence matrix A, one seeks for a periodic timetable π and a periodic tension x such that A^t π ≡ x mod T, x satisfies some lower and upper bounds, and x minimizes some linear functional. Intuitively, π assigns to each vertex a time, and x gives each edge a duration.

Methods for solving PESP instances comprise mixed integer linear programming, a modulo variant of the network simplex algorithm, and transformations to weighted MaxSAT instances. Combining these three approaches to a concurrent solver enabled us to compute the current best primal and dual bounds for all instances of the benchmarking library PESPlib, improving the previous values for half of the instances within only 20 minutes. Lately, we investigated PESP from a graph partitioning perspective dividing the network into T parts, which resulted in a powerful heuristic using standard maximum cuts as subroutine. Moreover, divide-and-conquer strategies by means of graph separators were able to produce stronger dual bounds. However, computing a provably optimal periodic timetable for, e.g., the public transport network of a whole city, is still out of reach due to large optimality gaps. Separating even the easiest type of cutting planes – the so-called cycle inequalities – is already NP-hard.

A reasonable extension of PESP is to include passenger routing: Usually passengers choose their route according to a timetable, so that the travel time of passengers can only be roughly estimated when planning a timetable. Mathematically speaking, including routing means to make the linear objective function bilinear, where the tension at each edge is multiplied by the number of passengers passing through this edge. Solving this integrated periodic timetabling problem is naturally more difficult. Since linearizations produce too large mixed integer linear programs, we developed an extension of the modulo network simplex method as a primal heuristic. A computational challenge is the frequent recomputation of the passenger flow, which can be overcome by restricting passengers to few likely paths, as the number of transfers in a public transit network is very small for most journeys.

Goals and Methods

Our idea is to include algebraic and tropical considerations into periodic timetabling.

At first, we want to exploit linear algebra over the residue class ring Z/TZ. As T = 60 minutes is a common choice, we cannot expect T to be prime. By a graph cohomology argument, the row space of the incidence matrix A is the orthogonal complement of the kernel of a cycle matrix Γ, i.e., a matrix whose rows are incidence vectors of oriented cycles forming a Z-basis of the cycle space of the graph. As a consequence, the PESP constraint A^t π ≡ x mod T is equivalent to Γx ≡ 0 mod T. The latter system of linear equations modulo T can be solved by means of the Hermite or Smith normal forms, allowing for an explicit parameterization of the tension space. So far, the Hermite normal form has only been suggested for a direct branch-and-bound algorithm. To our knowledge, there has been no further theoretical investigation, and there are no implementations in state-of-the art PESP solvers. The Smith normal form has not been discussed at all, although its elementary divisors are all 1. We want to compare the linear algebra modulo T approach to the common mixed integer programming formulations. Since the choice of Γ heavily influences the range of the integer variables, which motivates to strive for a minimum integral cycle basis, we also wonder how this is reflected in the parameterization.

Secondly, periodic timetabling is connected to tropical geometry. Given a feasible periodic timetable π and a periodic tension x on a digraph, the condition A^t π ≡ x mod T implies that for every edge ij holds x_ij + π_i ≡ π_j mod T . After normalizing x, if X denotes the weighted adjacency matrix of the digraph weighted by x, then this reads as X π = T π with respect to max-plus matrix multiplication. In other words, π is a tropical eigenvector for the tropical eigenvalue T of X. This relation is used in practice for robustness analysis of periodic timetables, where the eigenvalue for a given timetable is computed as maximum mean cycle length and then compared to the desired period time. A novel standpoint is to see the PESP conditions as description of the feasibility set of a quadratically-constrained tropical program. Using the cycle-matrix formulation Γx ≡ 0 mod T , we can even interpret x as a feasible solution to a linear tropical program. Our goal is to explore the tropical meanings of periodic timetabling, on one hand getting more insight into the structure of timetables, and on the other finding new combinatorial interpretations of tropical geometry. For example, we believe that there is a tropically inspired decomposition of the solution space.

Our third approach is again related to tropical geometry. In the integrated periodic timetabling problem, it is highly beneficial to keep the number of passenger paths per origin-destination pair low. For a fixed source and target, we therefore want to – as a preprocessing step – exclude edges in the network that can impossibly be part of a shortest path, regardless of the actual timetable. This depends of course on the lower and upper bounds on the periodic tension of the edges. Typically, the difference between upper and lower bound is only significant for edges representing transfers, and the number of transfers on a passenger path is desired to be small. For a single-source query, a modified version of Dijkstra’s algorithm is able to find the edges that cannot be part of a shortest path tree for each feasible choice of tensions within the bounds. In particular, one has an efficient characterization of the union of all shortest path trees for a fixed source, when edge costs can be arbitrary within an interval. A reverse perspective has been taken recenty, producing an algorithm to enumerate all shortest path trees with parameterized costs, exploiting a correspondence between shortest path trees and polyhedral cells induced by tropical hypersurfaces. Moreover, the cells are explicitly described by inequalities. This algorithm has been applied to a road network with uncertain travel times. We would like to apply the enumeration procedure to public transportation networks, and examine the interplay between our adapted Dijkstra algorithm and the tropical approach.

Project Webpages

Project Webpage at ZIB

Selected Publications

• N. Lindner, J. Reisch. Parameterized Complexity of Periodic Timetabling. ZIB Report 20-15, Zuse Institute Berlin, 2020.
• R. Borndörfer, H. Hoppmann, M. Karbstein, N. Lindner. Separation of Cycle Inequalities in Periodic Timetabling. Discrete Optimization (35), 2020.
• R. Borndörfer, N Lindner, S. Roth. A Concurrent Approach to the Periodic Event Scheduling Problem. Journal of Rail Transport Planning & Management, 2019, in press.
• N. Lindner, C. Liebchen. New Perspectives on PESP: T-Partitions and Separators. 19th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019).
• F. Löbel, N. Lindner, R. Borndörfer. The Restricted Modulo Network Simplex Method for Integrated Timetabling and Passenger Routing. ZIB-Report 19-36, Zuse Institute Berlin, 2019. To appear in Operations Research Proceedings 2019.

Selected Pictures