<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>9234</id>
    <completedYear/>
    <publishedYear>2025</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>106852</pageFirst>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>173</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2024-09-21</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">New Dynamic Programming Algorithm for the Multiobjective Minimum Spanning Tree Problem</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Computers &amp; Operations Research</parentTitle>
    <identifier type="doi">10.1016/j.cor.2024.106852</identifier>
    <identifier type="arxiv">2306.16203</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <licence>Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International</licence>
    <submitter>Pedro Maristany de las Casas</submitter>
    <author>Pedro Maristany de las Casas</author>
    <author>Antonio Sedeño-Noda</author>
    <author>Ralf Borndörfer</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>9235</id>
    <completedYear/>
    <publishedYear>2025</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>349</pageFirst>
    <pageLast>384</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>17</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2025-02-13</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">K-Shortest Simple Paths Using Biobjective Path Search</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Mathematical Programming Computation</parentTitle>
    <identifier type="doi">10.1007/s12532-025-00276-0</identifier>
    <identifier type="arxiv">2309.10377</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <licence>Creative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International</licence>
    <submitter>Pedro Maristany de las Casas</submitter>
    <author>Pedro Maristany de las Casas</author>
    <author>Antonio Sedeño-Noda</author>
    <author>Ralf Borndörfer</author>
    <author>Max Huneshagen</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>6489</id>
    <completedYear/>
    <publishedYear>2017</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>59</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Cost Projection Methods for the Shortest Path Problem with Crossing Costs</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="deu">17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)</parentTitle>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-64817</enrichment>
    <licence>Creative Commons - CC BY - Namensnennung 4.0 International</licence>
    <editor>Gianlorenzo D'Angelo</editor>
    <submitter>Thomas Schlechte</submitter>
    <author>Marco Blanco</author>
    <editor>Twan Dollevoet</editor>
    <author>Ralf Borndörfer</author>
    <author>Nam-Dung Hoang</author>
    <author>Anton Kaier</author>
    <author>Pedro Maristany de las Casas</author>
    <author>Thomas Schlechte</author>
    <author>Swen Schlobach</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="projects" number="MODAL-RailLab">MODAL-RailLab</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8271</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2021-06-29</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data</title>
    <abstract language="eng">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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-82716</identifier>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2021.7</identifier>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="AcceptedDate">30.07.2021</enrichment>
    <enrichment key="SourceTitle">appeared in 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)</enrichment>
    <author>Niels Lindner</author>
    <submitter>Niels Lindner</submitter>
    <author>Pedro Maristany de las Casas</author>
    <author>Philine Schiewe</author>
    <series>
      <title>ZIB-Report</title>
      <number>21-17</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Preprocessing Shortest Path Problems</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Interval Data</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Graph Algorithms</value>
    </subject>
    <collection role="ccs" number="G.">Mathematics of Computing</collection>
    <collection role="ccs" number="J.">Computer Applications</collection>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/8271/ZR-21-17.pdf</file>
  </doc>
  <doc>
    <id>8401</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>7:1</pageFirst>
    <pageLast>7:15</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>96</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2021.7</identifier>
    <enrichment key="Series">Open Access Series in Informatics (OASIcs)</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-82716</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <author>Niels Lindner</author>
    <submitter>Niels Lindner</submitter>
    <author>Pedro Maristany de las Casas</author>
    <author>Philine Schiewe</author>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="persons" number="lindner">Lindner, Niels</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>6481</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2017-08-30</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Cost Projection Methods for the Shortest Path Problem with Crossing Costs</title>
    <abstract language="eng">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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-64817</identifier>
    <enrichment key="FulltextUrl">Appeared in: 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)</enrichment>
    <author>Marco Blanco</author>
    <submitter>Thomas Schlechte</submitter>
    <author>Ralf Borndörfer</author>
    <author>Nam-Dung Hoang</author>
    <author>Anton Kaier</author>
    <author>Pedro Maristany de las Casas</author>
    <author>Thomas Schlechte</author>
    <author>Swen Schlobach</author>
    <series>
      <title>ZIB-Report</title>
      <number>17-48</number>
    </series>
    <collection role="msc" number="90-XX">OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/6481/ZR-17-48.pdf</file>
  </doc>
  <doc>
    <id>9650</id>
    <completedYear>2024</completedYear>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>19</pageFirst>
    <pageLast>30</pageLast>
    <pageNumber>12</pageNumber>
    <edition>1</edition>
    <issue>1</issue>
    <volume>318</volume>
    <type>article</type>
    <publisherName>Elsevier BV</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2024-05-03</completedDate>
    <publishedDate>2024-10-01</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Labeling methods for partially ordered paths</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">European Journal of Operational Research</parentTitle>
    <identifier type="doi">10.1016/j.ejor.2024.05.002</identifier>
    <identifier type="arxiv">2307.10332</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">02.05.2024</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ricardo Euler</author>
    <submitter>Ricardo Euler</submitter>
    <author>Pedro Maristany de las Casas</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="euler">Euler, Ricardo</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="projects" number="Cargo">Cargo</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>7971</id>
    <completedYear>2021</completedYear>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2021-06-18</completedDate>
    <publishedDate>2021-06-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Improved Multiobjective Shortest Path Algorithm</title>
    <abstract language="eng">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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-79712</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <submitter>Pedro Maristany de las Casas</submitter>
    <author>Pedro Maristany de las Casas</author>
    <author>Antonio Sedeno-Noda</author>
    <author>Ralf Borndörfer</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-26</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Multiobjective Shortest Path Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Output-Sensitive Multiobjective Combinatorial Problems</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Network Optimization</value>
    </subject>
    <collection role="ccs" number="G.2">DISCRETE MATHEMATICS</collection>
    <collection role="msc" number="05C85">Graph algorithms [See also 68R10, 68W05]</collection>
    <collection role="msc" number="68R10">Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]</collection>
    <collection role="msc" number="90-02">Research exposition (monographs, survey articles)</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/7971/main.pdf</file>
  </doc>
  <doc>
    <id>9939</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Logic-Constrained Shortest Paths for Flight Planning</title>
    <abstract language="eng">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&amp;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.</abstract>
    <identifier type="arxiv">2412.13235</identifier>
    <enrichment key="PeerReviewed">no</enrichment>
    <enrichment key="SubmissionStatus">under review</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Ricardo Euler</author>
    <submitter>Ricardo Euler</submitter>
    <author>Pedro Maristany de las Casas</author>
    <author>Ralf Borndörfer</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="euler">Euler, Ricardo</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
  <doc>
    <id>8551</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>135</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Improved Multiobjective Shortest Path Algorithm</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">Computers &amp; Operations Research</parentTitle>
    <identifier type="doi">10.1016/j.cor.2021.105424</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-79712</enrichment>
    <author>Pedro Maristany de las Casas</author>
    <submitter>Ekaterina Engel</submitter>
    <author>Antonio Sedeno-Noda</author>
    <author>Ralf Borndörfer</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="projects" number="MODAL-Gesamt">MODAL-Gesamt</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>8205</id>
    <completedYear/>
    <publishedYear>2021</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1</pageFirst>
    <pageLast>22</pageLast>
    <pageNumber/>
    <edition/>
    <issue>2</issue>
    <volume>14</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An FPTAS for Dynamic Multiobjective Shortest Path Problems</title>
    <abstract language="eng">The Dynamic Multiobjective Shortest Path problem features multidimensional costs that can depend on several variables and not only on time; this setting is motivated by flight planning applications and the routing of electric vehicles. We give an exact algorithm for the FIFO case and derive from it an FPTAS for both, the static Multiobjective Shortest Path (MOSP) problems and, under mild assumptions, for the dynamic problem variant. The resulting FPTAS is computationally efficient and beats the known complexity bounds of other FPTAS for MOSP problems.</abstract>
    <parentTitle language="eng">Algorithms</parentTitle>
    <identifier type="doi">https://doi.org/10.3390/a14020043</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="AcceptedDate">2021-01-22</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-80954</enrichment>
    <licence>Creative Commons - CC BY - Namensnennung 4.0 International</licence>
    <author>Pedro Maristany de las Casas</author>
    <submitter>Pedro Maristany de las Casas</submitter>
    <author>Ralf Borndörfer</author>
    <author>Luitgard Kraus</author>
    <author>Antonio Sedeño-Noda</author>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="LHS-ATN">LHS-ATN</collection>
    <collection role="persons" number="maristany">Maristany de las Casas, Pedro</collection>
    <collection role="institutes" number="neo">Network Optimization</collection>
    <collection role="projects" number="MODAL-MobilityLab">MODAL-MobilityLab</collection>
  </doc>
</export-example>
