Document

Short Paper

**Published in:** OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

The algorithmic efficiency of Newton-based methods for Free Flight Trajectory Optimization is heavily influenced by the size of the domain of convergence. We provide numerical evidence that the convergence radius is much larger in practice than what the theoretical worst case bounds suggest. The algorithm can be further improved by a convergence-enhancing domain decomposition.

Ralf Borndörfer, Fabian Danecker, and Martin Weiser. Convergence Properties of Newton’s Method for Globally Optimal Free Flight Trajectory Optimization (Short Paper). In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 3:1-3:6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2023.3, author = {Bornd\"{o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {{Convergence Properties of Newton’s Method for Globally Optimal Free Flight Trajectory Optimization}}, booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, pages = {3:1--3:6}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-302-7}, ISSN = {2190-6807}, year = {2023}, volume = {115}, editor = {Frigioni, Daniele and Schiewe, Philine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.3}, URN = {urn:nbn:de:0030-drops-187642}, doi = {10.4230/OASIcs.ATMOS.2023.3}, annote = {Keywords: shortest path, flight planning, free flight, optimal control, global optimization, Newton’s method} }

Document

**Published in:** OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

The fundamental task of every passenger railway operator is to offer an attractive railway timetable to the passengers while operating it as cost efficiently as possible. The available rolling stock has to be assigned to trips so that all trips are operated, operational requirements are satisfied, and the operating costs are minimum. This so-called Rolling Stock Rotation Problem (RSRP) is well studied in the literature. In this paper we consider an acyclic version of the RSRP that includes vehicle maintenance. As the latter is an important aspect, maintenance services have to be planned simultaneously to ensure the rotation’s feasibility in practice. Indeed, regular maintenance is important for the safety and reliability of the rolling stock as well as enforced by law in many countries. We present a new integer programming formulation that links a hyperflow to model vehicle compositions and their coupling decisions to a set of path variables that take care of the resource consumption of the individual vehicles. To solve the model we developed different column generation algorithms which are compared to each other as well as to the MILP flow formulation of [Ralf Borndörfer et al., 2016] on a test set of real world instances.

Boris Grimm, Ralf Borndörfer, and Julian Bushe. Assignment Based Resource Constrained Path Generation for Railway Rolling Stock Optimization. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 13:1-13:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{grimm_et_al:OASIcs.ATMOS.2023.13, author = {Grimm, Boris and Bornd\"{o}rfer, Ralf and Bushe, Julian}, title = {{Assignment Based Resource Constrained Path Generation for Railway Rolling Stock Optimization}}, booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, pages = {13:1--13:15}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-302-7}, ISSN = {2190-6807}, year = {2023}, volume = {115}, editor = {Frigioni, Daniele and Schiewe, Philine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.13}, URN = {urn:nbn:de:0030-drops-187741}, doi = {10.4230/OASIcs.ATMOS.2023.13}, annote = {Keywords: Railway Rolling Stock Optimization, Integer Programming, Column Generation} }

Document

Short Paper

**Published in:** OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

The ongoing electrification of logistics systems and vehicle fleets increases the complexity of associated vehicle routing or scheduling problems. Battery-powered vehicles have to be scheduled to recharge in-service, and the relationship between charging time and replenished driving range is non-linear. In order to access the powerful toolkit offered by mixed-integer and linear programming techniques, this battery behavior has to be linearized. Moreover, as electric fleets grow, power draw peaks have to be avoided to save on electricity costs or to adhere to hard grid capacity limits, such that it becomes desirable to keep recharge rates dynamic. We suggest a novel linearization approach of battery charging behavior for vehicle scheduling problems, in which the recharge rates are optimization variables and not model parameters.

Fabian Löbel, Ralf Borndörfer, and Steffen Weider. Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates (Short Paper). In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 15:1-15:6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{lobel_et_al:OASIcs.ATMOS.2023.15, author = {L\"{o}bel, Fabian and Bornd\"{o}rfer, Ralf and Weider, Steffen}, title = {{Non-Linear Charge Functions for Electric Vehicle Scheduling with Dynamic Recharge Rates}}, booktitle = {23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)}, pages = {15:1--15:6}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-302-7}, ISSN = {2190-6807}, year = {2023}, volume = {115}, editor = {Frigioni, Daniele and Schiewe, Philine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.15}, URN = {urn:nbn:de:0030-drops-187765}, doi = {10.4230/OASIcs.ATMOS.2023.15}, annote = {Keywords: Electric Vehicle Scheduling, Battery Powered Vehicles, Charging Process, Non-linear Charging, Recharge Modeling, Dynamic Recharge Rate} }

Document

**Published in:** OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

The Flight Planning Problem is to find a minimum fuel trajectory between two airports in a 3D airway network under consideration of the wind. We show that this problem is NP-hard, even in its most basic version. We then present a novel A* heuristic, whose potential function is derived from an idealized vertical profile over the remaining flight distance. This potential is, under rather general assumptions, both admissible and consistent and it can be computed efficiently. The method outperforms the state-of-the-art heuristic on real-life instances.

Marco Blanco, Ralf Borndörfer, and Pedro Maristany de las Casas. An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 1:1-1:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{blanco_et_al:OASIcs.ATMOS.2022.1, author = {Blanco, Marco and Bornd\"{o}rfer, Ralf and Maristany de las Casas, Pedro}, title = {{An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles}}, booktitle = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, pages = {1:1--1:15}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-259-4}, ISSN = {2190-6807}, year = {2022}, volume = {106}, editor = {D'Emidio, Mattia and Lindner, Niels}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.1}, URN = {urn:nbn:de:0030-drops-171052}, doi = {10.4230/OASIcs.ATMOS.2022.1}, annote = {Keywords: shortest path problem, a-star algorithm, flight trajectory optimization, flight planning, heuristics} }

Document

**Published in:** OASIcs, Volume 106, 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)

We present an efficient algorithm that finds a globally optimal solution to the 2D Free Flight Trajectory Optimization Problem (aka Zermelo Navigation Problem) up to arbitrary precision in finite time. The algorithm combines a discrete and a continuous optimization phase. In the discrete phase, a set of candidate paths that densely covers the trajectory space is created on a directed auxiliary graph. Then Yen’s algorithm provides a promising set of discrete candidate paths which subsequently undergo a locally convergent refinement stage. Provided that the auxiliary graph is sufficiently dense, the method finds a path that lies within the convex domain around the global minimizer. From this starting point, the second stage will converge rapidly to the optimum. The density of the auxiliary graph depends solely on the wind field, and not on the accuracy of the solution, such that the method inherits the superior asymptotic convergence properties of the optimal control stage.

Ralf Borndörfer, Fabian Danecker, and Martin Weiser. A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization. In 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022). Open Access Series in Informatics (OASIcs), Volume 106, pp. 2:1-2:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2022.2, author = {Bornd\"{o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {{A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization}}, booktitle = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, pages = {2:1--2:13}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-259-4}, ISSN = {2190-6807}, year = {2022}, volume = {106}, editor = {D'Emidio, Mattia and Lindner, Niels}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2022.2}, URN = {urn:nbn:de:0030-drops-171068}, doi = {10.4230/OASIcs.ATMOS.2022.2}, annote = {Keywords: shortest path, flight planning, free flight, discretization error bounds, optimal control, discrete optimization, global optimization} }

Document

Short Paper

**Published in:** OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

In order to plan and schedule a demand-responsive public transportation system, both temporal and spatial changes in demand should be taken into account even at the line planning stage. We study the multi-period line planning problem with integrated decisions regarding dynamic allocation of vehicles among the lines. Given the NP-hard nature of the line planning problem, the multi-period version is clearly difficult to solve for large public transit networks even with advanced solvers. It becomes necessary to develop algorithms that are capable of solving even the very-large instances in reasonable time. For instances which belong to real public transit networks, we present results of a heuristic local branching algorithm and an exact approach based on constraint propagation.

Güvenç Şahin, Amin Ahmadi Digehsara, and Ralf Borndörfer. Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation (Short Paper). In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 17:1-17:6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sahin_et_al:OASIcs.ATMOS.2021.17, author = {\c{S}ahin, G\"{u}ven\c{c} and Ahmadi Digehsara, Amin and Bornd\"{o}rfer, Ralf}, title = {{Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation}}, booktitle = {21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)}, pages = {17:1--17:6}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-213-6}, ISSN = {2190-6807}, year = {2021}, volume = {96}, editor = {M\"{u}ller-Hannemann, Matthias and Perea, Federico}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.17}, URN = {urn:nbn:de:0030-drops-148863}, doi = {10.4230/OASIcs.ATMOS.2021.17}, annote = {Keywords: public transportation, line planning, multi-period planning, local branching, constraint propagation} }

Document

APPROX

**Published in:** LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)

A connected partition is a partition of the vertices of a graph into sets that induce connected subgraphs. Such partitions naturally occur in many application areas such as road networks, and image processing. In these settings, it is often desirable to partition into a fixed number of parts of roughly of the same size or weight. The resulting computational problem is called Balanced Connected Partition (BCP). The two classical objectives for BCP are to maximize the weight of the smallest, or minimize the weight of the largest component. We study BCP on c-claw-free graphs, the class of graphs that do not have K_{1,c} as an induced subgraph, and present efficient (c-1)-approximation algorithms for both objectives. In particular, for 3-claw-free graphs, also simply known as claw-free graphs, we obtain a 2-approximation. Due to the claw-freeness of line graphs, this also implies a 2-approximation for the edge-partition version of BCP in general graphs.
A harder connected partition problem arises from demanding a connected partition into k parts that have (possibly) heterogeneous target weights w₁,…,w_k. In the 1970s Győri and Lovász showed that if G is k-connected and the target weights sum to the total size of G, such a partition exists. However, to this day no polynomial algorithm to compute such partitions exists for k > 4. Towards finding such a partition T₁,…, T_k in k-connected graphs for general k, we show how to efficiently compute connected partitions that at least approximately meet the target weights, subject to the mild assumption that each w_i is greater than the weight of the heaviest vertex. In particular, we give a 3-approximation for both the lower and the upper bounded version i.e. we guarantee that each T_i has weight at least (w_i)/3 or that each T_i has weight most 3w_i, respectively. Also, we present a both-side bounded version that produces a connected partition where each T_i has size at least (w_i)/3 and at most max({r,3}) w_i, where r ≥ 1 is the ratio between the largest and smallest value in w₁, … , w_k. In particular for the balanced version, i.e. w₁ = w₂ = , … , = w_k, this gives a partition with 1/3w_i ≤ w(T_i) ≤ 3w_i.

Ralf Borndörfer, Katrin Casel, Davis Issac, Aikaterini Niklanovits, Stephan Schwartz, and Ziena Zeif. Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 27:1-27:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:LIPIcs.APPROX/RANDOM.2021.27, author = {Bornd\"{o}rfer, Ralf and Casel, Katrin and Issac, Davis and Niklanovits, Aikaterini and Schwartz, Stephan and Zeif, Ziena}, title = {{Connected k-Partition of k-Connected Graphs and c-Claw-Free Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {27:1--27:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.27}, URN = {urn:nbn:de:0030-drops-147200}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.27}, annote = {Keywords: connected partition, Gy\H{o}ri-Lov\'{a}sz, balanced partition, approximation algorithms} }

Document

**Published in:** OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

For providing railway services the company’s railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see [Maróti and Kroon, 2005; Gábor Maróti and Leo G. Kroon, 2007], or [Cordeau et al., 2001] for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in [Ralf Borndörfer et al., 2015]. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of [Reuther, 2017] that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.

Boris Grimm, Ralf Borndörfer, Markus Reuther, and Thomas Schlechte. A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 1:1-1:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{grimm_et_al:OASIcs.ATMOS.2019.1, author = {Grimm, Boris and Bornd\"{o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {{A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance}}, booktitle = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, pages = {1:1--1:12}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-128-3}, ISSN = {2190-6807}, year = {2019}, volume = {75}, editor = {Cacchiani, Valentina and Marchetti-Spaccamela, Alberto}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.1}, URN = {urn:nbn:de:0030-drops-114136}, doi = {10.4230/OASIcs.ATMOS.2019.1}, annote = {Keywords: Railway Operations Research, Integer Programming, Infeasible Path Cuts, Cut Separation, Rolling Stock Rotation Problem} }

Document

**Published in:** OASIcs, Volume 75, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)

We present a novel framework to mathematically describe the fare systems of local public transit companies. The model allows the computation of a provably cheapest itinerary even if prices depend on a number of parameters and non-linear conditions. Our approach is based on a ticket graph model to represent tickets and their relation to each other. Transitions between tickets are modeled via transition functions over partially ordered monoids and a set of symbols representing special properties of fares (e.g. surcharges). Shortest path algorithms rely on the subpath optimality property. This property is usually lost when dealing with complicated fare systems. We restore it by relaxing domination rules for tickets depending on the structure of the ticket graph. An exemplary model for the fare system of Mitteldeutsche Verkehrsbetriebe (MDV) is provided. By integrating our framework in the multi-criteria RAPTOR algorithm we provide a price-sensitive algorithm for the earliest arrival problem and assess its performance on data obtained from MDV. We discuss three preprocessing techniques that improve run times enough to make the algorithm applicable for real-time queries.

Ricardo Euler and Ralf Borndörfer. A Graph- and Monoid-Based Framework for Price-Sensitive Routing in Local Public Transportation Networks. In 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019). Open Access Series in Informatics (OASIcs), Volume 75, pp. 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{euler_et_al:OASIcs.ATMOS.2019.12, author = {Euler, Ricardo and Bornd\"{o}rfer, Ralf}, title = {{A Graph- and Monoid-Based Framework for Price-Sensitive Routing in Local Public Transportation Networks}}, booktitle = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, pages = {12:1--12:15}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-128-3}, ISSN = {2190-6807}, year = {2019}, volume = {75}, editor = {Cacchiani, Valentina and Marchetti-Spaccamela, Alberto}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2019.12}, URN = {urn:nbn:de:0030-drops-114243}, doi = {10.4230/OASIcs.ATMOS.2019.12}, annote = {Keywords: shortest path, public transit, optimization, price-sensitive, raptor, fare, operations research} }

Document

Complete Volume

**Published in:** OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

OASIcs, Volume 65, ATMOS'18, Complete Volume

Ralf Borndörfer and Sabine Storandt. OASIcs, Volume 65, ATMOS'18, Complete Volume. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@Proceedings{borndorfer_et_al:OASIcs.ATMOS.2018, title = {{OASIcs, Volume 65, ATMOS'18, Complete Volume}}, booktitle = {18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-096-5}, ISSN = {2190-6807}, year = {2018}, volume = {65}, editor = {Bornd\"{o}rfer, Ralf and Storandt, Sabine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018}, URN = {urn:nbn:de:0030-drops-97272}, doi = {10.4230/OASIcs.ATMOS.2018}, annote = {Keywords: Theory of computation, Design and analysis of algorithms, Mathematics of computing, Discrete mathematics, Mathematics of computing, Combinatorics} }

Document

Front Matter

**Published in:** OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Front Matter, Table of Contents, Preface, Conference Organization

Ralf Borndörfer and Sabine Storandt. Front Matter, Table of Contents, Preface, Conference Organization. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 0:i-0:x, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2018.0, author = {Bornd\"{o}rfer, Ralf and Storandt, Sabine}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)}, pages = {0:i--0:x}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-096-5}, ISSN = {2190-6807}, year = {2018}, volume = {65}, editor = {Bornd\"{o}rfer, Ralf and Storandt, Sabine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.0}, URN = {urn:nbn:de:0030-drops-97050}, doi = {10.4230/OASIcs.ATMOS.2018.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }

Document

**Published in:** OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

We consider the following planning problem in public transportation: Given a periodic timetable, how many vehicles are required to operate it?
In [Julius Paetzold et al., 2017], for this sequential approach, it is proposed to first expand the periodic timetable over time, and then answer the above question by solving a flow-based aperiodic optimization problem.
In this contribution we propose to keep the compact periodic representation of the timetable and simply solve a particular perfect matching problem. For practical networks, it is very much likely that the matching problem decomposes into several connected components. Our key observation is that there is no need to change any turnaround decision for the vehicles of a line during the day, as long as the timetable stays exactly the same.

Ralf Borndörfer, Marika Karbstein, Christian Liebchen, and Niels Lindner. A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 16:1-16:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2018.16, author = {Bornd\"{o}rfer, Ralf and Karbstein, Marika and Liebchen, Christian and Lindner, Niels}, title = {{A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable}}, booktitle = {18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)}, pages = {16:1--16:15}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-096-5}, ISSN = {2190-6807}, year = {2018}, volume = {65}, editor = {Bornd\"{o}rfer, Ralf and Storandt, Sabine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.16}, URN = {urn:nbn:de:0030-drops-97214}, doi = {10.4230/OASIcs.ATMOS.2018.16}, annote = {Keywords: Vehicle Scheduling, Periodic Timetabling, Bipartite Matching} }

Document

**Published in:** OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem.
Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that transforms crossing costs into shadow costs on individual arcs, thus approximating the SPPCC by a standard shortest path problem. We evaluate all algorithms' performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.

Marco Blanco, Ralf Borndörfer, Nam Dung Hoàng, Anton Kaier, Pedro M. Casas, Thomas Schlechte, and Swen Schlobach. Cost Projection Methods for the Shortest Path Problem with Crossing Costs. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 15:1-15:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{blanco_et_al:OASIcs.ATMOS.2017.15, author = {Blanco, Marco and Bornd\"{o}rfer, Ralf and Dung Ho\`{a}ng, Nam and Kaier, Anton and Casas, Pedro M. and Schlechte, Thomas and Schlobach, Swen}, title = {{Cost Projection Methods for the Shortest Path Problem with Crossing Costs}}, booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)}, pages = {15:1--15:14}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-042-2}, ISSN = {2190-6807}, year = {2017}, volume = {59}, editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.15}, URN = {urn:nbn:de:0030-drops-78939}, doi = {10.4230/OASIcs.ATMOS.2017.15}, annote = {Keywords: shortest path problem, resource constrained shortest path, crossing costs, flight trajectory optimization, overflight fees, cost projection} }

Document

**Published in:** OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

We study the Flight Planning Problem for a single aircraft, which deals with finding a path of minimal travel time in an airway network. Flight time along arcs is affected by wind speed and direction, which are functions of time. We consider three variants of the problem, which can be modeled as, respectively, a classical shortest path problem in a metric space, a time-dependent shortest path problem with piecewise linear travel time functions, and a time-dependent shortest path problem with piecewise differentiable travel time functions.
The shortest path problem and its time-dependent variant have been extensively studied, in particular, for road networks. Airway networks, however, have different characteristics: the average node degree is higher and shortest paths usually have only few arcs.
We propose A* algorithms for each of the problem variants. In particular, for the third problem, we introduce an application-specific "super-optimal wind" potential function that overestimates optimal wind conditions on each arc, and establish a linear error bound. We compare the performance of our methods with the standard Dijkstra algorithm and the Contraction Hierarchies (CHs)
algorithm. Our computational results on real world instances show that CHs do not perform as well as on road networks. On the other hand, A* guided by our potentials yields very good results. In particular, for the case of piecewise linear travel time functions, we achieve query times about 15 times shorter than CHs.

Marco Blanco, Ralf Borndörfer, Nam-Dung Hoang, Anton Kaier, Adam Schienle, Thomas Schlechte, and Swen Schlobach. Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{blanco_et_al:OASIcs.ATMOS.2016.12, author = {Blanco, Marco and Bornd\"{o}rfer, Ralf and Hoang, Nam-Dung and Kaier, Anton and Schienle, Adam and Schlechte, Thomas and Schlobach, Swen}, title = {{Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind}}, booktitle = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)}, pages = {12:1--12:15}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-021-7}, ISSN = {2190-6807}, year = {2016}, volume = {54}, editor = {Goerigk, Marc and Werneck, Renato F.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.12}, URN = {urn:nbn:de:0030-drops-65360}, doi = {10.4230/OASIcs.ATMOS.2016.12}, annote = {Keywords: shortest path problem, A*, flight trajectory optimization, preprocessing, contraction hierarchies, time-dependent shortest path problem} }

Document

**Published in:** LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.

Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein. Separation of Cycle Inequalities for the Periodic Timetabling Problem. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 21:1-21:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:LIPIcs.ESA.2016.21, author = {Bornd\"{o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {{Separation of Cycle Inequalities for the Periodic Timetabling Problem}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {21:1--21:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.21}, URN = {urn:nbn:de:0030-drops-63722}, doi = {10.4230/LIPIcs.ESA.2016.21}, annote = {Keywords: periodic timetabling, cycle inequalities, separation algorithm} }

Document

**Published in:** OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

The resource constrained assignment problem (RCAP) is to find a minimal cost partition of the nodes of a directed graph into cycles such that a resource constraint is fulfilled. The RCAP has its roots in rolling stock rotation optimization where a railway timetable has to be covered by rotations, i.e., cycles. In that context, the resource constraint corresponds to maintenance constraints for rail vehicles. Moreover, the RCAP generalizes variants of the vehicle routing problem (VRP). The paper contributes an exact branch and bound algorithm for the RCAP and, primarily, a straightforward algorithmic concept that we call regional search (RS). As a symbiosis of a local and a global search algorithm, the result of an RS is a local optimum for a combinatorial optimization problem. In addition, the local optimum must be globally optimal as well if an instance of a problem relaxation is computed. In order to present the idea for a standardized setup we introduce an RS for binary programs. But the proper contribution of the paper is an RS that turns the Hungarian method into a powerful heuristic for the resource constrained assignment problem by utilizing the exact branch and bound. We present computational results for RCAP instances from an industrial cooperation with Deutsche Bahn Fernverkehr AG as well as for VRP instances from the literature. The results show that our RS provides a solution quality of 1.4 % average gap w.r.t. the best known solutions of a large test set. In addition, our branch and bound algorithm can solve many RCAP instances to proven optimality, e.g., almost all asymmetric traveling salesman and capacitated vehicle routing problems that we consider.

Ralf Borndörfer and Markus Reuther. Regional Search for the Resource Constrained Assignment Problem. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 111-129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2015.111, author = {Bornd\"{o}rfer, Ralf and Reuther, Markus}, title = {{Regional Search for the Resource Constrained Assignment Problem}}, booktitle = {15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)}, pages = {111--129}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-99-6}, ISSN = {2190-6807}, year = {2015}, volume = {48}, editor = {Italiano, Giuseppe F. and Schmidt, Marie}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.111}, URN = {urn:nbn:de:0030-drops-54536}, doi = {10.4230/OASIcs.ATMOS.2015.111}, annote = {Keywords: assignment problem, local search, branch and bound, rolling stock rota- tion problem, vehicle routing problem} }

Document

**Published in:** OASIcs, Volume 42, 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2014)

We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.

Ralf Borndörfer, Markus Reuther, and Thomas Schlechte. A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem. In 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 42, pp. 79-91, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2014.79, author = {Bornd\"{o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {{A Coarse-To-Fine Approach to the Railway Rolling Stock Rotation Problem}}, booktitle = {14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, pages = {79--91}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-75-0}, ISSN = {2190-6807}, year = {2014}, volume = {42}, editor = {Funke, Stefan and Mihal\'{a}k, Mat\'{u}s}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2014.79}, URN = {urn:nbn:de:0030-drops-47549}, doi = {10.4230/OASIcs.ATMOS.2014.79}, annote = {Keywords: Coarse-To-Fine Linear Programming, Rolling Stock Rotation Problem} }

Document

**Published in:** OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

We propose a novel extended formulation for the line planning
problem in public transport. It is based on a new concept of
frequency configurations that account for all possible
options to provide a required transportation capacity on an
infrastructure edge. We show that this model yields a strong LP
relaxation. It implies, in particular, general classes of facet
defining inequalities for the standard model.

Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein. A Configuration Model for the Line Planning Problem. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 68-79, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2013.68, author = {Bornd\"{o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {{A Configuration Model for the Line Planning Problem}}, booktitle = {13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, pages = {68--79}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-58-3}, ISSN = {2190-6807}, year = {2013}, volume = {33}, editor = {Frigioni, Daniele and Stiller, Sebastian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.68}, URN = {urn:nbn:de:0030-drops-42451}, doi = {10.4230/OASIcs.ATMOS.2013.68}, annote = {Keywords: Combinatorial optimization, polyhedral combinatorics, line planning} }

Document

**Published in:** OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)

The treatment of transfers is a major challenge in line planning.
Existing models either route passengers and lines sequentially, and
hence disregard essential degrees of freedom, or they are of
extremely large scale, and seem to be computationally intractable.
We propose a novel direct connection approach that allows an
integrated optimization of line and passenger routing, including
accurate estimates of the number of direct travelers, for large-scale real-world instances.

Ralf Borndörfer and Marika Karbstein. A Direct Connection Approach to Integrated Line Planning and Passenger Routing. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 47-57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2012.47, author = {Bornd\"{o}rfer, Ralf and Karbstein, Marika}, title = {{A Direct Connection Approach to Integrated Line Planning and Passenger Routing}}, booktitle = {12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, pages = {47--57}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-45-3}, ISSN = {2190-6807}, year = {2012}, volume = {25}, editor = {Delling, Daniel and Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.47}, URN = {urn:nbn:de:0030-drops-37027}, doi = {10.4230/OASIcs.ATMOS.2012.47}, annote = {Keywords: combinatorial optimization, line planning, transfers, passenger routing} }

Document

**Published in:** OASIcs, Volume 22, 3rd Student Conference on Operational Research (2012)

In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach.

Ralf Borndörfer, Guillaume Sagnol, and Elmar Swarat. A Case Study on Optimizing Toll Enforcements on Motorways. In 3rd Student Conference on Operational Research. Open Access Series in Informatics (OASIcs), Volume 22, pp. 1-10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.SCOR.2012.1, author = {Bornd\"{o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {{A Case Study on Optimizing Toll Enforcements on Motorways}}, booktitle = {3rd Student Conference on Operational Research}, pages = {1--10}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-39-2}, ISSN = {2190-6807}, year = {2012}, volume = {22}, editor = {Ravizza, Stefan and Holborn, Penny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SCOR.2012.1}, URN = {urn:nbn:de:0030-drops-35418}, doi = {10.4230/OASIcs.SCOR.2012.1}, annote = {Keywords: Vehicle Routing Problem, Duty Rostering, Integer Programming, Operations Research} }

Document

**Published in:** OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the "regularity" of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.

Ralf Borndörfer, Markus Reuther, Thomas Schlechte, and Steffen Weider. A Hypergraph Model for Railway Vehicle Rotation Planning. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 146-155, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2011.146, author = {Bornd\"{o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {{A Hypergraph Model for Railway Vehicle Rotation Planning}}, booktitle = {11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, pages = {146--155}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-33-0}, ISSN = {2190-6807}, year = {2011}, volume = {20}, editor = {Caprara, Alberto and Kontogiannis, Spyros}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.146}, URN = {urn:nbn:de:0030-drops-32746}, doi = {10.4230/OASIcs.ATMOS.2011.146}, annote = {Keywords: Rolling Stock Planning, Hypergraph Modeling, Integer Programming, Column Generation, Rapid Branching} }

Document

**Published in:** OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

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.

Ralf Borndörfer, Thomas Schlechte, and Steffen Weider. Railway Track Allocation by Rapid Branching. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 13-23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2010.13, author = {Bornd\"{o}rfer, Ralf and Schlechte, Thomas and Weider, Steffen}, title = {{Railway Track Allocation by Rapid Branching}}, booktitle = {10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)}, pages = {13--23}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-20-0}, ISSN = {2190-6807}, year = {2010}, volume = {14}, editor = {Erlebach, Thomas and L\"{u}bbecke, Marco}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.13}, URN = {urn:nbn:de:0030-drops-27465}, doi = {10.4230/OASIcs.ATMOS.2010.13}, annote = {Keywords: track allocation problem, integer programming, rapid branching heuristic, proximal bundle method} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 9261, Models and Algorithms for Optimization in Logistics (2009)

The line planning problem in public transport deals with the
construction of a system of lines that is both attractive for the
passengers and of low costs for the operator.
In general, the computed line system should be connected, i.e., for each two stations there have to be a path that is covered by the lines.
This subproblem is a generalization of the well-known Steiner tree problem;
we call it the Steiner connectivity Problem. We discuss complexity of this problem, generalize the so-called
Steiner partition inequalities and give a transformation to the
directed Steiner tree problem. We show that directed models provide
tight formulations for the Steiner connectivity problem, similar as
for the Steiner tree problem.

Ralf Borndörfer, Marika Neumann, and Marc E. Pfetsch. Line Planning and Connectivity. In Models and Algorithms for Optimization in Logistics. Dagstuhl Seminar Proceedings, Volume 9261, pp. 1-3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:DagSemProc.09261.15, author = {Bornd\"{o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc E.}, title = {{Line Planning and Connectivity}}, booktitle = {Models and Algorithms for Optimization in Logistics}, pages = {1--3}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2009}, volume = {9261}, editor = {Cynthia Barnhart and Uwe Clausen and Ulrich Lauther and Rolf H. M\"{o}hring}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09261.15}, URN = {urn:nbn:de:0030-drops-21661}, doi = {10.4230/DagSemProc.09261.15}, annote = {Keywords: Steiner tree, generalization, paths} }

Document

**Published in:** OASIcs, Volume 9, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08) (2008)

Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito TrolebÃƒÂºs system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the TrolebÃƒÂºs System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.

Luis M. Torres, Ramiro Torres, Ralf Borndörfer, and Marc E. Pfetsch. Line Planning on Paths and Tree Networks with Applications to the Quito TrolebÃƒÂºs System. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Open Access Series in Informatics (OASIcs), Volume 9, pp. 1-13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{torres_et_al:OASIcs.ATMOS.2008.1583, author = {Torres, Luis M. and Torres, Ramiro and Bornd\"{o}rfer, Ralf and Pfetsch, Marc E.}, title = {{Line Planning on Paths and Tree Networks with Applications to the Quito Troleb\~{A}ƒ\^{A}ºs System}}, booktitle = {8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08)}, pages = {1--13}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-07-1}, ISSN = {2190-6807}, year = {2008}, volume = {9}, editor = {Fischetti, Matteo and Widmayer, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2008.1583}, URN = {urn:nbn:de:0030-drops-15838}, doi = {10.4230/OASIcs.ATMOS.2008.1583}, annote = {Keywords: Line planning, computational complexity, public transport, combinatorial optimization} }

Document

**Published in:** OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)

The optimal track allocation problem (OPTRA) is to find, in a given
railway network, a conflict free set of train routes of maximum
value. We study two types of integer programming formulations for
this problem: a standard formulation that models block conflicts in
terms of packing constraints, and a novel formulation of the
`extended' type that is based on additional `configuration'
variables. The packing constraints in the standard formulation stem
from an interval graph and can therefore be separated in polynomial
time. It follows that the LP-relaxation of a strong version of this
model, including all clique inequalities from block conflicts, can
be solved in polynomial time. We prove that the LP-relaxation of
the extended formulation can also be solved in polynomial time, and
that it produces the same LP-bound. Albeit the two formulations are
in this sense equivalent, the extended formulation has advantages
from a computational point of view. It features a constant number of
rows and is amenable to standard column generation
techniques. Results of an empirical model comparison on mesoscopic
data for the Hanover-Fulda-Kassel region of the German long
distance railway network are reported.

Ralf Borndörfer and Thomas Schlechte. 05. Models for Railway Track Allocation. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 62-78, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{borndorfer_et_al:OASIcs.ATMOS.2007.1170, author = {Bornd\"{o}rfer, Ralf and Schlechte, Thomas}, title = {{05. Models for Railway Track Allocation}}, booktitle = {7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)}, pages = {62--78}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-04-0}, ISSN = {2190-6807}, year = {2007}, volume = {7}, editor = {Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1170}, URN = {urn:nbn:de:0030-drops-11701}, doi = {10.4230/OASIcs.ATMOS.2007.1170}, annote = {Keywords: Track allocation, train timetabling,integer programming, column generation} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail