Continuous-time Dynamic Shortest Paths with Negative Transit Times
| dc.contributor.author | Koch, Ronald | |
| dc.contributor.author | Nasrabadi, Ebrahim | |
| dc.date.accessioned | 2021-12-17T10:09:14Z | |
| dc.date.available | 2021-12-17T10:09:14Z | |
| dc.date.issued | 2010 | |
| dc.description.abstract | We 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.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15699 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14472 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | shortest path problem | en |
| dc.subject.other | linear programming in measure spaces | en |
| dc.subject.other | extreme points | en |
| dc.subject.other | duality theory | en |
| dc.subject.other | measure theory | en |
| dc.title | Continuous-time Dynamic Shortest Paths with Negative Transit Times | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2010, 06 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
| tub.subject.msc2000 | 05C38 Paths and cycles | en |
| tub.subject.msc2000 | 49J27 Existence theories for problems in abstract spaces | en |
| tub.subject.msc2000 | 90C46 Optimality conditions and duality in mathematical programming | en |
| tub.subject.msc2000 | 46E27 Spaces of measures | en |
Files
Original bundle
1 - 1 of 1