Wardrop's first principle: Extension for capacitated networks

Document Type : Article

Authors

1 Institute for Transportation Studies and Research (ITSR), Department of Civil Engineering, Sharif University of Technology (SUT), Tehran, P.O. Box 14588, Iran

2 Department of Civil Engineering, University of Toronto, Toronto, Ontario M5S 1A4, Canada

Abstract

In transportation literature, User Equilibrium (UE) has been widely studied since early 1950’s, many studies of which define equilibrium flow of traffic for uncapacitated networks based on Wardrop’s first principle, implying also a Nash Equilibrium (NE). Although, in general, the two equilibria (UE and NE) are not explicitly the same, they are shown to be equivalent under special conditions, for uncapacitated UE, when volume-delay functions are separable, continuous, non-decreasing and non-negative.
A good deal of research is devoted to explain UE in capacitated networks based on Wardrop’s first principle and the concept of generalized costs. However, UE for capacitated networks, even under the defined special conditions, is not equivalent to NE. This paper extends Wardrop’s first principle to explain UE in capacitated networks, which, under the same special conditions of uncapacitated networks, would represent an NE as well. Moreover, a complementarity equilibrium model is proposed for UE, based on an extension of Wardrop’s principle.

Keywords


References
1. Morlok, E.K., Introduction to Transportation Engineering
and Planning, McGraw-Hill College, New York
(1978).
2. Beckmann, M., McGuire, C., and Winsten, C., Studies
in the Economics of Transportation, Yale University
Press, New Haven, Conn (1956).
3. Zhang, C., Chen, X., and Sumalee, A. \Robust
Wardrop's user equilibrium assignment under stochastic
demand and supply: expected residual minimization
approach", Transportation Research Part B:
Methodological, 45(3), pp. 534{552 (2011).
4. Nie, Y.M. \Equilibrium analysis of macroscopic trac
oscillations", Transportation Research Part B: Methodological,
44(1), pp. 62{72 (2010).
5. He, F., Yin, Y., Shirmohammadi, N., and Nie, Y.M.
\Tradable credit schemes on networks with mixed
equilibrium behaviors", Transportation Research Part
B: Methodological, 57, pp. 47{65 (2013).
6. Marcotte, P., Nguyen, S., and Schoeb, A. \A strategic

ow model of trac assignment in static capacitated
networks", Operations Research, 52(2), pp. 191{212
(2004).
7. Patriksson, M. \The trac assignment problem: models
and methods", Utrecht, VSP, BV, The Netherlands
(1994).
8. Branston, D. \Link capacity functions: A review",
Transportation Research, 10(4), pp. 223{236 (1976).
9. Larsson, T. and Patriksson, M. \An augmented Lagrangean
dual algorithm for link capacity side constrained
trac assignment problems", Transportation
Research Part B: Methodological, 29(6), pp. 433{455
(1995).
10. Larsson, T. and Patriksson, M. \Side constrained traf-
c equilibrium models-analysis, computation and applications",
Transportation Research Part B: Methodological,
33(4), pp. 233{264 (1999).
11. Correa, J.R., Schulz, A.S., and Stier-Moses, N.E. \Selfish
routing in capacitated networks", Mathematics of
Operations Research, 29(4), pp. 961{976 (2004).
12. Zhang, D., Nagurney, A., and Wu, J. \On the equivalence
between stationary link
ow patterns and trac
network equilibria", Transportation Research Part B:
Methodological, 35(8), pp. 731{748 (2001).
13. Yang, F. and Zhang, D. \Day-to-day stationary
link
ow pattern", Transportation Research Part B:
Methodological, 43(1), pp. 119{126 (2009).
190 H. Zokaei Aashtiani et al./Scientia Iranica, Transactions A: Civil Engineering 28 (2021) 175{191
14. Smith, M.J. \The stability of a dynamic model of
trac assignment-an application of a method of Lyapunov",
Transportation Science, 18(3), pp. 245{252
(1984).
15. Jin, W.-L. \On the stability of user equilibria in static
transportation networks", Transportmetrica, 4(1), pp.
1{17 (2008).
16. Jin, W.-L. \A dynamical system model of the trac
assignment problem", Transportation Research Part B:
Methodological, 41(1), pp. 32{48 (2007).
17. Szeto, W. and Lo, H.K. \Dynamic trac assignment:
properties and extensions", Transportmetrica, 2(1),
pp. 31{52 (2006).
18. Nasri, M. and Sosa, W. \Equilibrium problems and
generalized Nash games", Optimization, 60(8{9), pp.
1161{1170 (2011).
19. Rosenthal, R.W. \The network equilibrium problem in
integers", Networks, 3(1), pp. 53{59 (1973).
20. Devarajan, S. \A note of network equilibrium and
noncooperative games", Transportation Research Part
B: Methodological, 15(6), pp. 421{426 (1981).
21. Levinson, D. \Micro-foundations of congestion and
pricing: A game theory perspective", Transportation
Research Part A: Policy and Practice, 39(7{9), pp.
691{704 (2005).
22. Zou, X. and Levinson, D. \A multi-agent congestion
and pricing model", Transportmetrica, 2(3), pp. 237{
249 (2006).
23. Han, Q., Dellaert, B., Van Raaij, F., and Timmermans,
H. \Modelling strategic behaviour in anticipation
of congestion", Transportmetrica, 3(2), pp. 119{138
(2007).
24. Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos,
E., Wexler, T., and Roughgarden, T. \The price of
stability for network design with fair cost allocation",
SIAM Journal on Computing, 38(4), pp. 1602{1623
(2008).
25. Li, C., Gopalarao, S., and Ray, T. \A path-based

ow formulation for the trac assignment problem",
Transportation Planning and Technology, 39(6), pp.
597{611 (2016).
26. Schulz, A.S. and Stier Moses, N. \On the performance
of user equilibria in trac networks", Working Paper
4274-02, MIT Sloan School of Management (2003).
27. Jahn, O., Mohring, R.H., Schulz, A.S., and Stier-
Moses, N.E. \System-optimal routing of trac
ows
with user constraints in networks with congestion",
Operations Research, 53(4), pp. 600{616 (2005).
28. Poorzahedy, H. and Bushehri, S.N.S. \Pessimistic
equilibrium
ow and its network design implications",
European Journal of Transport and Infrastructure Research,
6(2), pp. 113-130 (2006).
29. Tobin, R.L. and Friesz, T.L. \Sensitivity analysis
for equilibrium network
ow", Transportation Science,
22(4), pp. 242{250 (1988).
30. Daganzo, C.F. \On the trac assignment problem
with
ow dependent costs-II", Transportation Research,
11(6), pp. 439{441 (1977).
31. Daganzo, C.F. \On the trac assignment problem
with
ow dependent costs-I", Transportation Research,
11(6), pp. 433{437 (1977).
32. Boyce, D., Janson, B., and Eash, R. \The e ect on
equilibrium trip assignment of di erent link congestion
functions", Transportation Research Part A: General,
15(3), pp. 223{232 (1981).
33. Nie, Y., Zhang, H., and Lee, D.-H. \Models and
algorithms for the trac assignment problem with link
capacity constraints", Transportation Research Part B:
Methodological, 38(4), pp. 285{312 (2004).
34. Hearn, D. \Bounding
ows in trac assignment models",
in Research Report 80-4, Department of Industrial
and Systems Engineering, University of Florida
Gainesville, FL (1980).
35. Daganzo, C.F. \Queue spillovers in transportation
networks with a route choice", Transportation Science,
32(1), pp. 3{11 (1998).
36. Hearn, D. and Ribera, J. \Bounded
ow equilibrium
problems by penalty methods", In Proceedings of IEEE
International Conference on Circuits and Computers,
Institute of Electrical and Electronics Engineers, New
York (1980).
37. Shahpar, A.H., Aashtiani, H.Z., and Babazadeh, A.
\Dynamic penalty function method for the side constrained
trac assignment problem", Applied Mathematics
and Computation, 206(1), pp. 332{345 (2008).
38. Yang, H. and Yagar, S. \Trac assignment and
trac control in general freeway-arterial corridor systems",
Transportation Research Part B: Methodological,
28(6), pp. 463{486 (1994).
39. Yang, H. and Yagar, S. \Trac assignment and signal
control in saturated road networks", Transportation
Research Part A: Policy and Practice, 29(2), pp. 125{
139 (1995).
40. Haurie, A. and Marcotte, P. \On the relationship
between Nash-Cournot and Wardrop equilibria", Networks,
15(3), pp. 295{308 (1985).
41. Roughgarden, T. and Tardos, E_ . \How bad is sel sh
routing?", Journal of the ACM (JACM), 49(2), pp.
236{259 (2002).
42. Wardrop, J.G. \Some theoretical aspects of road trac
research", OR: Operational Research Quarterly, 4(4),
pp. 72{73 (1952).
43. Aashtiani, H.Z. \The multi-modal trac assignment
problem", PhD Dissertation, Massachusetts Institute
of Technology, Boston, MA, USA (1979).