Flows over Time: Towards a more Realistic and Computationally Tractable Model
Alexander Hall, Heiko Schilling · DepositOnce · 2004
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.