TY - JOUR A1 - Maristany de las Casas, Pedro A1 - Sedeño-Noda, Antonio A1 - Borndörfer, Ralf T1 - New Dynamic Programming Algorithm for the Multiobjective Minimum Spanning Tree Problem JF - Computers & Operations Research N2 - The Multiobjective Minimum Spanning Tree (MO-MST) problem is a variant of the Minimum Spanning Tree problem, in which the costs associated with every edge of the input graph are vectors. In this paper, we design a new dynamic programming MO-MST algorithm. Dynamic programming for a MO-MST instance leads to the definition of an instance of the One-to-One Multiobjective Shortest Path (MOSP) problem and both instances have equivalent solution sets. The arising MOSP instance is defined on a so called transition graph. We study the original size of this graph in detail and reduce its size using cost dependent arc pruning criteria. To solve the MOSP instance on the reduced transition graph, we design the Implicit Graph Multiobjective Dijkstra Algorithm (IG-MDA), exploiting recent improvements on MOSP algorithms from the literature. All in all, the new IG-MDA outperforms the current state of the art on a big set of instances from the literature. Our code and results are publicly available. Y1 - 2025 U6 - https://doi.org/10.1016/j.cor.2024.106852 VL - 173 SP - 106852 ER - TY - JOUR A1 - Maristany de las Casas, Pedro A1 - Sedeño-Noda, Antonio A1 - Borndörfer, Ralf A1 - Huneshagen, Max T1 - K-Shortest Simple Paths Using Biobjective Path Search JF - Mathematical Programming Computation N2 - In this paper we introduce a new algorithm for the k-Shortest Simple Paths (K-SSP) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to Roditty and Zwick (2012) that solves at most 2k instances of the Second Shortest Simple Path (2-SSP) problem without specifying how this is done. We fill this gap using a novel approach: we turn the scalar 2-SSP into instances of the Biobjective Shortest Path problem. Our experiments on grid graphs and on road networks show that the new algorithm is very efficient in practice. Y1 - 2025 U6 - https://doi.org/10.1007/s12532-025-00276-0 VL - 17 SP - 349 EP - 384 ER - TY - CHAP A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Kaier, Anton A1 - Maristany de las Casas, Pedro A1 - Schlechte, Thomas A1 - Schlobach, Swen ED - D'Angelo, Gianlorenzo ED - Dollevoet, Twan T1 - Cost Projection Methods for the Shortest Path Problem with Crossing Costs T2 - 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017) N2 - 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 à posteriori error bounds. Y1 - 2017 VL - 59 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 - TY - CHAP A1 - Lindner, Niels A1 - Maristany de las Casas, Pedro A1 - Schiewe, Philine T1 - Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data T2 - 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) 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. Y1 - 2021 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2021.7 VL - 96 SP - 7:1 EP - 7:15 ER - TY - GEN A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Hoang, Nam-Dung A1 - Kaier, Anton A1 - Maristany de las Casas, Pedro A1 - Schlechte, Thomas A1 - Schlobach, Swen T1 - Cost Projection Methods for the Shortest Path Problem with Crossing Costs N2 - 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 à posteriori error bounds. T3 - ZIB-Report - 17-48 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64817 SN - 1438-0064 ER - TY - JOUR A1 - Euler, Ricardo A1 - Maristany de las Casas, Pedro T1 - Labeling methods for partially ordered paths JF - European Journal of Operational Research N2 - The landscape of applications and subroutines relying on shortest path computations continues to grow steadily. This growth is driven by the undeniable success of shortest path algorithms in theory and practice. It also introduces new challenges as the models and assessing the optimality of paths become more complicated. Hence, multiple recent publications in the field adapt existing labeling methods in an ad hoc fashion to their specific problem variant without considering the underlying general structure: they always deal with multi-criteria scenarios, and those criteria define different partial orders on the paths. In this paper, we introduce the partial order shortest path problem (POSP), a generalization of the multi-objective shortest path problem (MOSP) and in turn also of the classical shortest path problem. POSP captures the particular structure of many shortest path applications as special cases. In this generality, we study optimality conditions or the lack of them, depending on the objective functions’ properties. Our final contribution is a big lookup table summarizing our findings and providing the reader with an easy way to choose among the most recent multi-criteria shortest path algorithms depending on their problems’ weight structure. Examples range from time-dependent shortest path and bottleneck path problems to the electric vehicle shortest path problem with recharging and complex financial weight functions studied in the public transportation community. Our results hold for general digraphs and, therefore, surpass previous generalizations that were limited to acyclic graphs. Y1 - 2024 U6 - https://doi.org/10.1016/j.ejor.2024.05.002 VL - 318 IS - 1 SP - 19 EP - 30 PB - Elsevier BV ET - 1 ER - TY - GEN A1 - Maristany de las Casas, Pedro A1 - Sedeno-Noda, Antonio A1 - Borndörfer, Ralf T1 - An Improved Multiobjective Shortest Path Algorithm N2 - 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. T3 - ZIB-Report - 20-26 KW - Multiobjective Shortest Path Problem KW - Output-Sensitive Multiobjective Combinatorial Problems KW - Network Optimization Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-79712 SN - 1438-0064 ER - TY - JOUR A1 - Euler, Ricardo A1 - Maristany de las Casas, Pedro A1 - Borndörfer, Ralf T1 - Logic-Constrained Shortest Paths for Flight Planning N2 - The Logic-Constrained Shortest Path Problem (LCSP) combines a one-to-one shortest path problem with satisfiability constraints imposed on the routing graph. This setting arises in flight planning, where air traffic control (ATC) authorities are enforcing a set of traffic flow restrictions (TFRs) on aircraft routes in order to increase safety and throughput. We propose a new branch and bound-based algorithm for the LCSP. The resulting algorithm has three main degrees of freedom: the node selection rule, the branching rule and the conflict. While node selection and branching rules have been long studied in the MIP and SAT communities, most of them cannot be applied out of the box for the LCSP. We review the existing literature and develop tailored variants of the most prominent rules. The conflict, the set of variables to which the branching rule is applied, is unique to the LCSP. We analyze its theoretical impact on the B&B algorithm. In the second part of the paper, we show how to model the Flight Planning Problem with TFRs as an LCSP and solve it using the branch and bound algorithm. We demonstrate the algorithm’s efficiency on a dataset consisting of a global flight graph and a set of around 20000 real TFRs obtained from our industry partner Lufthansa Systems GmbH. We make this dataset publicly available. Finally, we conduct an empirical in-depth analysis of node selection rules, branching rules and conflicts. Carefully choosing an appropriate combination yields an improvement of an order of magnitude compared to an uninformed choice. Y1 - 2024 ER - TY - JOUR A1 - Maristany de las Casas, Pedro A1 - Sedeno-Noda, Antonio A1 - Borndörfer, Ralf T1 - An Improved Multiobjective Shortest Path Algorithm JF - Computers & Operations Research N2 - We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes a minimum 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 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 2 to 9 times faster on all used graph types. On some instances the speedup reaches an order of magnitude. Y1 - 2021 U6 - https://doi.org/10.1016/j.cor.2021.105424 VL - 135 ER -