• search hit 4 of 8
Back to Result List

A Duality Theory for Continuous-time Dynamic Shortest Paths with Negative Transit Times

Please always quote using this URN:urn:nbn:de:0296-matheon-8131
  • This paper concerns the shortest path problem for a network in which arc costs can vary with time, each arc has a transit time, parking with a corresponding time-varying cost is allowed at the nodes, and time is modeled as a continuum. The resulting problem is called the {\em continuous-time dynamic shortest path problem}, which is well studied in the literature. However, the problem appears as a subproblem when one wishes to test, via an algorithm for dynamic shortest paths, the presence of negative cycles in the residual network in order to develop continuous-time analogues of several well-known optimality conditions for continuous-time dynamic network flow problems. But, in general, the residual network contains arcs with negative transit times and hence the results in the literature are useless for these purposes since all results are based on the assumption of positive transit times. In this paper, we relax this condition to allow negative transit times. We study a corresponding linear program in space of measures and prove the existence of an optimal extreme point solution. Moreover, we define a dual problem and establish a strong duality result that shows under certain assumptions that the value of the linear program equals the value of the dual problem and both values are attained. We also present counterexamples to show that strong duality only holds under these assumptions.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Ronald Koch, Ebrahim Nasrabadi
URN:urn:nbn:de:0296-matheon-8131
Referee:Martin Skutella
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2011/04/26
Release Date:2011/04/26
Tag:
Institute:Research Center Matheon
Technische Universität Berlin
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C21 Flows in graphs
49-XX CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX] / 49Jxx Existence theories / 49J27 Problems in abstract spaces [See also 90C48, 93C25]
49-XX CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX] / 49Kxx Optimality conditions / 49K27 Problems in abstract spaces [See also 90C48, 93C25]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C46 Optimality conditions, duality [See also 49N15]
Preprint Number:780
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.