@misc{Lindner2025, author = {Lindner, Niels}, title = {A Multi-Commodity Flow Heuristic for Integrated Periodic Timetabling for Railway Construction Sites}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-99449}, year = {2025}, abstract = {Rescheduling a railway system comprises many aspects, such as line planning, timetabling, track allocation, and vehicle scheduling. For periodic timetables, these features can be integrated into a single mixed-integer program extending the Periodic Event Scheduling Problem (PESP) with a routing component. We develop a multi-commodity-flow-based heuristic that allows to compute better solutions faster than a black-box MIP approach on real construction site scenarios on the S-Bahn Berlin network.}, language = {en} } @inproceedings{LindnerMasing2024, author = {Lindner, Niels and Masing, Berenike}, title = {SAT-Generated Initial Solutions for Integrated Line Planning and Turn-Sensitive Periodic Timetabling with Track Choice}, booktitle = {hEART 2024: 12th Symposium of the European Association for Research in Transportation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-98066}, year = {2024}, abstract = {Periodic timetabling is a challenging planning task in public transport. As safety requirements are crucial, track allocation is indispensable for validating the practical feasibility of a railway timetable. For busy stations with limited capacities, this requires a detailed planning of turn-arounds. It is therefore desirable to integrate timetabling not only with track allocation, but also with vehicle scheduling and line planning. This is captured by the Integrated Line Planning and Turn-Sensitive Periodic Timetabling Problem with Track Choice, whose MIP formulation has been demonstrated to be effective for construction site railway rescheduling, as long as a good quality initial solution is available. In this paper, we discuss how to generate such a solution by extending the SAT formulation of the Periodic Event Scheduling Problem with track choice, track occupation, and minimum service frequency components. The SAT approach is superior to pure MIP on real-world instances of the S-Bahn Berlin network.}, language = {de} } @misc{BorndoerferSchlechteWeider2010, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Weider, Steffen}, title = {Railway Track Allocation by Rapid Branching}, organization = {Zuse Institut Berlin}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11864}, number = {10-22}, year = {2010}, abstract = {The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported.}, language = {en} } @misc{SchlechteTanner2010, author = {Schlechte, Thomas and Tanner, Andreas}, title = {Railway capacity auctions with dual prices}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11729}, number = {10-10}, year = {2010}, abstract = {Railway scheduling is based on the principle of the construction of a conflict-free timetable. This leads to a strict definition of capacity: in contrast with road transportation, it can be said in advance whether a given railway infrastructure can accommodate - at least in theory - a certain set of train requests. Consequently, auctions for railway capacity are modeled as auctions of discrete goods -- the train slots. We present estimates for the efficiency gain that may be generated by slot auctioning in comparison with list price allocation. We introduce a new class of allocation and auction problems, the feasible assignment problem, that is a proper generalization of the well-known combinatorial auction problem. The feasible assignment class was designed to cover the needs for an auction mechanism for railway slot auctions, but is of interest in its own right. As a practical instance to state and solve the railway slot allocation problem, we present an integer programming formulation, briefly the ACP, which turns out to be an instance of the feasible assignment problem and whose dual problem yields prices that can be applied to define a useful activity rule for the linearized version of the Ausubel Milgrom Proxy auction. We perform a simulation aiming to measure the impact on efficiency and convergence rate.}, language = {en} }