Time-Expanded Graphs for Flow-Dependent Transit Times

dc.contributor.authorKöhler, Ekkehard
dc.contributor.authorLangkau, Katharina
dc.contributor.authorSkutella, Martin
dc.date.accessioned2021-12-17T10:18:48Z
dc.date.available2021-12-17T10:18:48Z
dc.date.issued2002
dc.description.abstractMotivated by applications in road traffic control, we study flows in networks featuring special characteristics. In contrast to classical static flow problems, time plays a decisive role. Firstly, there are transit times on the arcs of the network which specify the amount of time it takes for flow to travel through a particular arc; more precisely, flow values on arcs may change over time. Secondly, the transit time of an arc varies with the current amount of flow using this arc. Especially the latter feature is crucial for various real-life applications of flows over time; yet, it dramatically increases the degree of difficulty of the resulting optimization problems.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15979
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14752
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.otherapproximation algorithmsen
dc.subject.otherdynamic flowen
dc.subject.otherflow over timeen
dc.subject.othergraph algorithmsen
dc.subject.othernetwork flowen
dc.subject.otherroutingen
dc.subject.othertraffic modelsen
dc.titleTime-Expanded Graphs for Flow-Dependent Transit Timesen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber2002, 762en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
tub.subject.msc200090C27 Combinatorial optimizationen
tub.subject.msc200090B10 Network models, deterministicen
tub.subject.msc200090B20 Traffic problemsen
tub.subject.msc200090C35 Programming involving graphs or networksen
tub.subject.msc200005C85 Graph algorithmsen
tub.subject.msc200090C59 Approximation methods and heuristicsen
tub.subject.msc200068W25 Approximation algorithmsen
tub.subject.msc200068Q25 Analysis of algorithms and problem complexityen

Files

Original bundle
Now showing 1 - 2 of 2
Loading…
Thumbnail Image
Name:
Report-762-2002.pdf
Size:
217.29 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
Report-762-2002.ps.gz
Size:
219.78 KB
Format:
Unknown data format

Collections