@misc{BlancoBorndoerferHoangetal., author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung and Kaier, Anton and Maristany de las Casas, Pedro and Schlechte, Thomas and Schlobach, Swen}, title = {Cost Projection Methods for the Shortest Path Problem with Crossing Costs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64817}, abstract = {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 approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms' performance on real-world flight trajectory optimization instances, obtaining very good {\`a} posteriori error bounds.}, language = {en} } @misc{MaristanydelasCasasBorndoerferKrausetal.2020, author = {Maristany de las Casas, Pedro and Bornd{\"o}rfer, Ralf and Kraus, Luitgard and Sede{\~n}o-Noda, Antonio}, title = {An FPTAS for Dynamic Multiobjective Shortest Path Problems}, doi = {https://doi.org/10.3390/a14020043}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-80954}, year = {2020}, abstract = {We propose in this paper the Dynamic Multiobjective Shortest Problem. It features multidimensional states that can depend on several variables and not only on time; this setting is motivated by flight planning and electric vehicle routing applications. We give an exact algorithm for the FIFO case and derive from it an FPTAS, which is computationally efficient. It also features the best known complexity in the static case.}, language = {en} } @article{SchienleMaristanydelasCasasBlanco, author = {Schienle, Adam and Maristany de las Casas, Pedro and Blanco, Marco}, title = {A Priori Search Space Pruning in the Flight Planning Problem}, issn = {1438-0064}, doi = {https://doi.org/10.4230/OASIcs.ATMOS.2019.8}, abstract = {We study the Flight Planning Problem for a single aircraft, where we look for a minimum cost path in the airway network, a directed graph. Arc evaluation, such as weather computation, is computationally expensive due to non-linear functions, but required for exactness. We propose several pruning methods to thin out the search space for Dijkstra's algorithm before the query commences. We do so by using innate problem characteristics such as an aircraft's tank capacity, lower and upper bounds on the total costs, and in particular, we present a method to reduce the search space even in the presence of regional crossing costs. We test all pruning methods on real-world instances, and show that incorporating crossing costs into the pruning process can reduce the number of nodes by 90\\% in our setting.}, language = {en} } @misc{MaristanydelasCasasSedenoNodaBorndoerfer2021, author = {Maristany de las Casas, Pedro and Sedeno-Noda, Antonio and Bornd{\"o}rfer, Ralf}, title = {An Improved Multiobjective Shortest Path Algorithm}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-79712}, year = {2021}, abstract = {We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes the minimal complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra's algorithm for the Shortest Path problem. Hence, we suggest to call the algorithm \emph{Multiobjective Dijkstra Algorithm} (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins', which we improved using new data structures and pruning techniques. On average, the MDA is \$\times2\$ to \$\times9\$ times faster on all used graph types. On some instances the speedup reaches an order of magnitude.}, language = {en} } @misc{LindnerMaristanydelasCasasSchiewe, author = {Lindner, Niels and Maristany de las Casas, Pedro and Schiewe, Philine}, title = {Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2021.7}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82716}, abstract = {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.}, language = {en} }