Please use this identifier to cite or link to this item:
For citation please use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorKoch, Ronald
dc.contributor.authorNasrabadi, Ebrahim
dc.description.abstractWe consider the dynamic shortest path problem in the continuous-time model because of its importance. This problem has been extensively studied in the literature. But so far, all contributions to this problem are based on the assumption that all transit times are strictly positive. However, in order to study dynamic network flows it is essential to support negative transit times since they occur quite naturally in residual networks. In this paper we extend the work of Philpott [SIAM Control Opt., 1994, pp. 538-552] to the case of arbitrary (also negative) transit times. In particular, we study a corresponding linear program in space of measures and characterize its extreme points. We show a one-to-one correspondence between extreme points and dynamic paths. Further, under certain assumptions, we prove the existence of an optimal extreme point to the linear program and establish a strong duality result. We also present counterexamples to show that strong duality only holds under these assumptions.en
dc.subject.ddc510 Mathematiken
dc.subject.othershortest path problemen
dc.subject.otherlinear programming in measure spacesen
dc.subject.otherextreme pointsen
dc.subject.otherduality theoryen
dc.subject.othermeasure theoryen
dc.titleContinuous-time Dynamic Shortest Paths with Negative Transit Timesen
dc.typeResearch Paperen
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2010, 06en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften » Inst. Mathematikde
tub.subject.msc200005C38 Paths and cyclesen
tub.subject.msc200049J27 Existence theories for problems in abstract spacesen
tub.subject.msc200090C46 Optimality conditions and duality in mathematical programmingen
tub.subject.msc200046E27 Spaces of measuresen
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Format: Adobe PDF | Size: 366.96 kB
DownloadShow Preview

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.