License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2017.15
URN: urn:nbn:de:0030-drops-78939
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7893/
Go to the corresponding OASIcs Volume Portal

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

Cost Projection Methods for the Shortest Path Problem with Crossing Costs

pdf-format:
OASIcs-ATMOS-2017-15.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{blanco_et_al:OASIcs:2017:7893,
  author =	{Marco Blanco and Ralf Bornd{\"o}rfer and Nam Dung Ho{\`a}ng and Anton Kaier and Pedro M. Casas and Thomas Schlechte and Swen Schlobach},
  title =	{{Cost Projection Methods for the Shortest Path Problem with Crossing Costs}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{15:1--15:14},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{Gianlorenzo D'Angelo and Twan Dollevoet},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7893},
  URN =		{urn:nbn:de:0030-drops-78939},
  doi =		{10.4230/OASIcs.ATMOS.2017.15},
  annote =	{Keywords: shortest path problem, resource constrained shortest path, crossing costs, flight trajectory optimization, overflight fees, cost projection}
}

Keywords: shortest path problem, resource constrained shortest path, crossing costs, flight trajectory optimization, overflight fees, cost projection
Collection: 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)
Issue Date: 2017
Date of publication: 04.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI