Flows over time with load-dependent transit times

ABSTRACT

About forty years ago, Ford and Fulkerson studied maximum 'dynamic' s-t-flows in networks with fixed transit times on the edges and a fixed time horizon. They showed that there always exists an optimal solution which sends flow on certain s-t-paths at a constant rate as long as there is enough time left for the flow along a path to arrive at the sink.Although this result does not hold for the more general setting of flows over time with load-dependent transit times on the edges, we prove that there always exists a provably good solution of this structure. Moreover, such a solution can be determined very efficiently by only one minimum convex cost flow computation on the underlying 'static' network. Finally, we show that the time-dependent flow problem under consideration is NP-hard and even cannot be approximated with arbitrary precision in polynomial time, unless P=NP.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: J. E. Aronson, A survey of dynamic network flows, Annals of Operations Research, v.20 n.1-4, p.1-66, Aug. 1989 [doi>10.1007/BF02216922]
• 3: M. Carey. A constraint qualification for a dynamic traffic assignment model. Transportation Science, 20:55 - 58, 1986.
• 4: M. Carey, Optimal time-varying flows on congested networks, Operations Research, v.35 n.1, p.58-69, Jan.-Feb. 1987 [doi>10.1287/opre.35.1.58]
• 5: M. Carey and E. Subrahmanian. An approach to modelling time-varying flows on congested networks. Transportation Research B, 34:157 - 183, 2000.
• 6: L. R. Ford and D. R. Fulkerson. Constructing maximal dynamic flows from static flows. Operations Research, 6:419 - 433, 1958.
• 7: L. R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, Princeton, NJ, 1962.
• 8: N. Gartner, C. J. Messer, and A. K. Rathi. Traffic flow theory: A state of the art report. http://www-cta.ornl.gov/cta/research/trb/tft.html, 1997.
• 9: Bruce Hoppe , Òva Tardos, The Quickest Transshipment Problem, Mathematics of Operations Research, v.25 n.1, p.36-62, February 2000 [doi>10.1287/moor.25.1.36.15211]
• 10: Bettina Klinz , Gerhard J. Woeginger, Minimum Cost Dynamic Flows: The Series-Parallel Case, Proceedings of the 4th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.329-343, May 29-31, 1995
• 11: H. S. Mahmassani and S. Peeta. System optimal dynamic assignment for electronic route guidance in a congested traffic network. In N. H. Gartner and G. Improta, editors, Urban Traffic Networks. Dynamic Flow Modelling and Control, pages 3 - 37. Springer, Berlin, 1995.
• 12: D. K. Merchant and G. L. Nemhauser. A model and an algorithm for the dynamic traffic assignment problems. Transportation Science, 12:183 - 199, 1978.
• 13: D. K. Merchant and G. L. Nemhauser. Optimality conditions for a dynamic traffic assignment model. Transportation Science, 12:200 - 207, 1978.
• 14: W. B. Powell, P. Jaillet, and A. Odoni. Stochastic and dynamic networks and routing. In M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, editors, Network Routing, volume 8 of Handbooks in Operations Research and Management Science, chapter 3, pages 141 - 295. North-Holland, Amsterdam, The Netherlands, 1995.
• 15: B. Ran and D. E. Boyce. Modelling Dynamic Transportation Networks. Springer, Berlin, 1996.
• 16: T. Roughgarden , E. Tardos, How bad is selfish routing?, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.93, November 12-14, 2000
• 17: Y. Sheffi. Urban Transportation Networks. Prentice-Hall, New Jersey, 1985.