Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

The Shortest Path Problem with Crossing Costs

Please always quote using this URN: urn:nbn:de:0297-zib-61240
  • We introduce the shortest path problem with crossing costs (SPPCC), a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions. The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs. In this paper, we provide a comprehensive analysis of the problem. In particular, we identify efficient exact and approximation algorithms for the cases that are most relevant in practice.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Marco Blanco, Ralf BorndörferORCiD, Nam-Dung Hoang, Anton Kaier, Thomas Schlechte, Swen Schlobach
Document Type:ZIB-Report
Date of first Publication:2016/11/30
Series (Serial Number):ZIB-Report (16-70)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.