<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <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>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>8866</id>
    <completedYear/>
    <publishedYear>2022</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1:1</pageFirst>
    <pageLast>1:15</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>106</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An A* Algorithm for Flight Planning Based on Idealized Vertical Profiles</title>
    <abstract language="eng">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.</abstract>
    <parentTitle language="eng">22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)</parentTitle>
    <identifier type="doi">10.4230/OASIcs.ATMOS.2022.1</identifier>
    <enrichment key="PeerReviewed">yes</enrichment>
    <enrichment key="opus.source">publish</enrichment>
    <author>Marco Blanco</author>
    <submitter>Marco Blanco</submitter>
    <author>Ralf Borndörfer</author>
    <author>Pedro Maristany de las Casas</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>8096</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>2019-11-15</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">A Priori Search Space Pruning in the Flight Planning Problem</title>
    <abstract language="eng">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.&#13;
&#13;
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.</abstract>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="doi">https://doi.org/10.4230/OASIcs.ATMOS.2019.8</identifier>
    <licence>Creative Commons - CC BY - Namensnennung 4.0 International</licence>
    <author>Adam Schienle</author>
    <submitter>Pedro Maristany de las Casas</submitter>
    <author>Pedro Maristany de las Casas</author>
    <author>Marco Blanco</author>
    <series>
      <title>ZIB-Report</title>
      <number>20-32</number>
    </series>
    <collection role="msc" number="90B99">None of the above, but in this section</collection>
    <collection role="msc" number="90C35">Programming involving graphs or networks [See also 90C27]</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>
    <thesisPublisher>Zuse Institute Berlin (ZIB)</thesisPublisher>
    <file>https://opus4.kobv.de/opus4-zib/files/8096/OASIcs-ATMOS-2019-8.pdf</file>
  </doc>
</export-example>
