Operations Research 2025
Abstract Submission

2427. Visualization of Event Graphs for Train Schedules

Invited abstract in session WE-4: GOR Master Thesis Awards, stream PC Stream.

Wednesday, 16:30-18:00
Room: H6

Authors (first author is the speaker)

1. Samuel Wolf
Lehrstuhl I, University of Würzburg

Abstract

Software that is used to compute or adjust train schedules is based on so-called event graphs. The vertices of such a graph correspond to events; each event is associated with a point in time, a location, and a train. A train line corresponds to a sequence of events that are associated with the same train. The event graph has a directed edge from an earlier to a later event if they are consecutive along a train line.

We present a way to visualize such graphs. We propose a straight-line drawing of the event graph with the additional constraint that all vertices that belong to the same location lie on the same horizontal line and that the x-coordinate of each vertex is given by its point in time. Hence, it remains to determine the y-coordinates of the locations. A good drawing of a time-space diagram supports users (or software developers) when creating (software for computing) train schedules.

To enhance readability, we define two aesthetic criteria: the number of crossings and the number of turns. We show that minimizing the number of crossings or minimizing the number of turns is NP-hard, and even NP-hard to approximate. To tackle these challenges, we develop exact reduction rules to reduce the instance size. Additionally, we propose exact algorithms, including integer linear programs and parameterized algorithms, along with heuristics for minimizing the number of crossings and the number of turns. Finally, we experimentally evaluate the performance of these algorithms
using real-world test data.

Keywords

Status: accepted

Back to the list of papers