TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)2004

COGA 5-Wheel

Page Content

to Navigation

Preprints 2004

Flows over Time: Towards a more Realistic and Computationally Tractable Model
Citation key Report-035-2004
Author Alex Hall and Heiko Schilling
Year 2004
Number 035
Institution Technische Universität Berlin, Institut für Mathematik
Abstract We introduce a novel model for ``Flows over Time'' which captures the behavior of cars traveling through a road network better than previous models. We show that computing an optimal solution in the new model is NP-hard and present an LP-based algorithm which we evaluate with several experiments on real world data of road networks and generated requests. Among other things we compare the quality of the solutions with solutions generated by an FPTAS for a related but considerably less realistic model.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe