@article{BorndoerferDaneckerWeiser2023, author = {Bornd{\"o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {Newton's Method for Global Free Flight Trajectory Optimization}, volume = {4}, journal = {Operations Research Forum}, doi = {10.1007/s43069-023-00238-z}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91846}, year = {2023}, abstract = {Globally optimal free flight trajectory optimization can be achieved with a combination of discrete and continuous optimization. A key requirement is that Newton's method for continuous optimization converges in a sufficiently large neighborhood around a minimizer. We show in this paper that, under certain assumptions, this is the case.}, language = {en} } @misc{PrauseBorndoerfer2023, author = {Prause, Felix and Bornd{\"o}rfer, Ralf}, title = {Construction of a Test Library for the Rolling Stock Rotation Problem with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91734}, year = {2023}, abstract = {We describe the development of a test library for the rolling stock rotation problem with predictive maintenance (RSRP-PdM). Our approach involves the utilization of genuine timetables from a private German railroad company. The generated instances incorporate probability distribution functions for modeling the health states of the vehicles and the considered trips possess varying degradation functions. RSRP-PdM involves assigning trips to a fleet of vehicles and scheduling their maintenance based on their individual health states. The goal is to minimize the total costs consisting of operational costs and the expected costs associated with vehicle failures. The failure probability is dependent on the health states of the vehicles, which are assumed to be random variables distributed by a family of probability distributions. Each distribution is represented by the parameters characterizing it and during the operation of the trips, these parameters get altered. Our approach incorporates non-linear degradation functions to describe the inference of the parameters but also linear ones could be applied. The resulting instances consist of the timetables of the individual lines that use the same vehicle type. Overall, we employ these assumptions and utilize open-source data to create a library of instances with varying difficulty. Our approach is vital for evaluating and comparing algorithms designed to solve the RSRP-PdM.}, language = {en} } @misc{BorndoerferDaneckerWeiser2023, 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}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-91309}, year = {2023}, abstract = {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.}, language = {en} } @misc{BorndoerferDaneckerWeiser2023, author = {Bornd{\"o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {Newton's Method for Global Free Flight Trajectory Optimization}, doi = {10.12752/8987}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89876}, year = {2023}, abstract = {Globally optimal free flight trajectory optimization can be achieved with a combination of discrete and continuous optimization. A key requirement is that Newton's method for continuous optimization converges in a sufficiently large neighborhood around a minimizer. We show in this paper that, under certain assumptions, this is the case.}, language = {en} } @inproceedings{MasingLindnerBorndoerfer2022, author = {Masing, Berenike and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {Optimal Line Plans in the Parametric City and the Impact of In-Motion Costs}, booktitle = {Operations Research Proceedings 2021}, editor = {Trautmann, Norbert and Dr{\"a}gi, Mario}, publisher = {Springer, Cham}, isbn = {978-3-031-08623-6}, doi = {10.1007/978-3-031-08623-6_44}, pages = {295 -- 301}, year = {2022}, abstract = {Line planning in public transport involves determining vehicle routes and assigning frequencies of service such that travel demands are satisfied. We evaluate how line plans, which are optimal with respect to in-motion costs (IMC), the objective function depending purely on arc-lengths for both user and operator costs, performs with respect to the value of resources consumed (VRC). The latter is an elaborate, socio-economic cost function which includes discomfort caused by delay, boarding and alighting times, and transfers. Even though discomfort is a large contributing factor to VRC and is entirely disregarded in IMC,  we observe that the two cost functions are qualitatively comparable.}, language = {en} } @misc{PrauseBorndoerferGrimmetal.2023, author = {Prause, Felix and Bornd{\"o}rfer, Ralf and Grimm, Boris and Tesch, Alexander}, title = {Approximating the RSRP with Predictive Maintenance}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89531}, year = {2023}, abstract = {We study the solution of the rolling stock rotation problem with predictive maintenance (RSRP-PM) by an iterative refinement approach that is based on a state-expanded event-graph. In this graph, the states are parameters of a failure distribution, and paths correspond to vehicle rotations with associated health state approximations. An optimal set of paths including maintenance can be computed by solving an integer linear program. Afterwards, the graph is refined and the procedure repeated. An associated linear program gives rise to a lower bound that can be used to determine the solution quality. Computational results for two instances derived from real world timetables of a German railway company are presented. The results show the effectiveness of the approach and the quality of the solutions.}, language = {en} } @inproceedings{BlancoBorndoerferMaristanydelasCasas2022, 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}, volume = {106}, booktitle = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, doi = {10.4230/OASIcs.ATMOS.2022.1}, pages = {1:1 -- 1:15}, year = {2022}, abstract = {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.}, language = {en} } @inproceedings{BorndoerferDaneckerWeiser2022, author = {Bornd{\"o}rfer, Ralf and Danecker, Fabian and Weiser, Martin}, title = {A Discrete-Continuous Algorithm for Globally Optimal Free Flight Trajectory Optimization}, volume = {106}, booktitle = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, doi = {10.4230/OASIcs.ATMOS.2022.2}, pages = {1 -- 13}, year = {2022}, abstract = {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.}, language = {en} } @article{MasingLindnerBorndoerfer2022, author = {Masing, Berenike and Lindner, Niels and Bornd{\"o}rfer, Ralf}, title = {The price of symmetric line plans in the Parametric City}, volume = {166}, journal = {Transportation Research Part B: Methodological}, doi = {10.1016/j.trb.2022.10.009}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-88613}, pages = {419 -- 443}, year = {2022}, abstract = {We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. We prove that the symmetry gap is small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations.}, language = {de} } @article{BorndoerferSchwartzSurau2023, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Vertex Covering with Capacitated Trees}, volume = {81}, journal = {Networks}, number = {2}, doi = {10.1002/net.22130}, pages = {253 -- 277}, year = {2023}, abstract = {The covering of a graph with (possibly disjoint) connected subgraphs is a funda-mental problem in graph theory. In this paper, we study a version to cover a graph'svertices by connected subgraphs subject to lower and upper weight bounds, and pro-pose a column generation approach to dynamically generate feasible and promisingsubgraphs. Our focus is on the solution of the pricing problem which turns out to bea variant of the NP-hard Maximum Weight Connected Subgraph Problem. We com-pare different formulations to handle connectivity, and find that a single-commodityflow formulation performs best. This is notable since the respective literature seemsto have widely dismissed this formulation. We improve it to a new coarse-to-fine flowformulation that is theoretically and computationally superior, especially for largeinstances with many vertices of degree 2 like highway networks, where it provides aspeed-up factor of 5 over the non-flow-based formulations. We also propose a pre-processing method that exploits a median property of weight-constrained subgraphs,a primal heuristic, and a local search heuristic. In an extensive computational studywe evaluate the presented connectivity formulations on different classes of instances,and demonstrate the effectiveness of the proposed enhancements. Their speed-upsessentially multiply to an overall factor of well over 10. Overall, our approach allowsthe reliable solution of instances with several hundreds of vertices in a few min-utes. These findings are further corroborated in a comparison to existing districtingmodels on a set of test instances from the literature}, language = {en} }