TY - GEN A1 - Schiewe, Philine A1 - Goerigk, Marc A1 - Lindner, Niels T1 - Introducing TimPassLib - A library for integrated periodic timetabling and passenger routing N2 - Classic models to derive a timetable for public transport often face a chicken-and-egg situation: A good timetable should offer passengers routes with small travel times, but the route choice of passengers depends on the timetable. While models that fix passenger routes were frequently considered in the literature, integrated models that simultaneously optimize timetables and passenger routes have seen increasing attention lately. This creates a growing need for a set of instances that allows to test and compare new algorithmic developments for the integrated problem. Our paper addresses this requirement by presenting TimPassLib, a new benchmark library of instances for integrated periodic timetabling and passenger routing. T3 - ZIB-Report - 23-06 KW - periodic timetabling KW - optimization in public transport KW - data sets KW - benchmarking Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-89741 SN - 1438-0064 ER - TY - GEN A1 - Lindner, Niels A1 - Maristany de las Casas, Pedro A1 - Schiewe, Philine T1 - Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data N2 - We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport. T3 - ZIB-Report - 21-17 KW - Preprocessing Shortest Path Problems KW - Interval Data KW - Graph Algorithms Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-82716 SN - 1438-0064 ER -