Document Open Access Logo

Cost Projection Methods for the Shortest Path Problem with Crossing Costs

Authors Marco Blanco, Ralf Borndörfer, Nam Dung Hoàng, Anton Kaier, Pedro M. Casas, Thomas Schlechte, Swen Schlobach

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2017.15.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Marco Blanco
Ralf Borndörfer
Nam Dung Hoàng
Anton Kaier
Pedro M. Casas
Thomas Schlechte
Swen Schlobach

Cite As Get BibTex

Marco Blanco, Ralf Borndörfer, Nam Dung Hoàng, Anton Kaier, Pedro M. Casas, Thomas Schlechte, and Swen Schlobach. Cost Projection Methods for the Shortest Path Problem with Crossing Costs. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/OASIcs.ATMOS.2017.15

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 transforms crossing costs into shadow costs on individual arcs, thus approximating the SPPCC by a standard shortest path problem.  We evaluate all algorithms' performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.

Subject Classification

Keywords
  • shortest path problem
  • resource constrained shortest path
  • crossing costs
  • flight trajectory optimization
  • overflight fees
  • cost projection

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Federal Aviation Administration. Overflight fees, 2017. [Online; accessed 1-July-2017]. URL: https://www.faa.gov/air_traffic/international_aviation/overflight_fees/.
  2. ASECNA. Air Navigation Services Charges, 2017. [Online; accessed 1-July-2017]. URL: http://www.ais-asecna.org/pdf/gen/gen-4-2/00gen4-2-01.pdf.
  3. C. Barrett, K. Bisset, M. Holzer, G. Konjevod, M. V. Marathe, and D. Wagner. Engineering label-constrained shortest-path algorithms. In Proceedings of the 4th International Conference on Algorithmic Aspects in Information and Management (AAIM'08), volume 5034 of Lecture Notes in Computer Science, pages 27-37. Springer, June 2008. Google Scholar
  4. Marco Blanco, Ralf Borndörfer, Nam Dung Hoang, Anton Kaier, Adam Schienle, Thomas Schlechte, and Swen Schlobach. Solving Time Dependent Shortest Path Problems on Airway Networks Using Super-Optimal Wind. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016), volume 54 of Open Access Series in Informatics (OASIcs), pages 1-15, 2016. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2016.12.
  5. Marco Blanco, Ralf Borndörfer, Nam Dung Hoang, Anton Kaier, Thomas Schlechte, and Swen Schlobach. The shortest path problem with crossing costs. Technical Report 16-70, ZIB, Takustr.7, 14195 Berlin, 2016. Google Scholar
  6. Pierre Bonami, Alberto Olivares, Manuel Soler, and Ernesto Staffetti. Multiphase mixed-integer optimal control approach to aircraft trajectory optimization. Journal of Guidance, Control, and Dynamics, 36(5):1267-1277, July 2013. Google Scholar
  7. Hajo Broersma, Xueliang Li, Gerhard Woeginger, and Shenggui Zhang. Paths and cycles in colored graphs. Australasian journal of combinatorics, 31:299-311, 2005. Google Scholar
  8. Susan Carey. Calculating costs in the clouds. The Wall Street Journal, March 2007. Google Scholar
  9. EUROCONTROL. Route charges, 2017. [Online; accessed 1-July-2017]. URL: http://www.eurocontrol.int/crco.
  10. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., New York, NY, USA, 1979. Google Scholar
  11. Horst W. Hamacher and Anita Schöbel. Design of zone tariff systems in public transport. Operations Research, 52(6):897-908, 2004. Google Scholar
  12. Refael Hassin. Approximation schemes for the restricted shortest path problem. Mathematics of Operations Research, 17(1):36-42, 1992. Google Scholar
  13. Refael Hassin, Jérôme Monnot, and Danny Segev. Approximation algorithms and hardness results for labeled connectivity problems. Journal of Combinatorial Optimization, 14(4):437-453, 2007. Google Scholar
  14. Stefan Irnich and Guy Desaulniers. Column Generation, chapter Shortest Path Problems with Resource Constraints, pages 33-65. Springer US, Boston, MA, 2005. Google Scholar
  15. Stefan E. Karisch, Stephen S. Altus, Goran Stojković, and Mirela Stojković. Operations. In Cynthia Barnhart and Barry Smith, editors, Quantitative Problem Solving Methods in the Airline Industry, volume 169 of International Series in Operations Research &Management Science, pages 283-383. Springer US, 2012. Google Scholar
  16. Dean H. Lorenz and Danny Raz. A simple efficient approximation scheme for the restricted shortest path problem. Oper. Res. Lett., 28(5):213-219, June 2001. Google Scholar
  17. Robert L. Schultz, Stephen G. Pratt, and Donald A. Shaner. Four-dimensional route planner, March 27 2003. WO Patent App. PCT/US2002/029,474. Google Scholar
  18. Christian Sommer. Shortest-path queries in static networks. ACM Comput. Surv., 46(4):45:1-45:31, March 2014. Google Scholar
  19. Banavar Sridhar, Hok Kwan Ng, Florian Linke, and Neil Y. Chen. Impact of airspace charges on transatlantic aircraft trajectories. In 15th AIAA Aviation Technology, Integration, and Operations Conference. American Institute of Aeronautics and Astronautics, jun 2015. URL: http://dx.doi.org/10.2514/6.2015-2596.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact