On the system optimum of traffic assignment in \(M/G/c/c\) state-dependent queueing networks. (English) Zbl 1177.90089

Summary: The classical Wardrop System Optimum assignment model assumes that the users will cooperate with each other in order to minimize the overall travel costs. The importance of the system optimum model lies on its well-recognized ability of producing solutions that correspond to the most efficient way of using the scarce resources represented by the street and road capacities. In this paper, we present a version of the system optimum model in which the travel costs incurred on each path come from \(M/G/c/c\) state-dependent queueing networks, a stochastic travel time estimation formula which takes into account congestion effects. A Differential Evolution algorithm is proposed to solve the model. We motivate this version of the problem in several ways and computational results show that the proposed approach is efficient.


90B22 Queues and service in operations research
90B20 Traffic problems in operations research
68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI


[1] Akçelik, R., Travel time function for transport planning purposes: davidson’s function, its time dependent form and an alternative travel time function, Australian road research, 21, 3, 49-59, (1991)
[2] Babu, B.V.; Sastry, K.K.N., Estimation of heat transfer parameters in a trickle bed reactor using differential evolution and orthogonal collocation, Computers and chemical engineering, 23, 3, 327-339, (1999)
[3] Beckmann, M.; McGuire, C.B.; Winsten, C., Studies in the economics of transportation, (1956), Yale University Press New Haven, CT
[4] Bell, M.G.H.; Cassir, C., Risk-averse user equilibrium traffic assignment: an application of game theory, Transportation research part B, 36, 8, 671-681, (2002)
[5] Braess, D., Über ein paradoxon aus der verkehrsplanung, Unternehmensforschung, 12, 258-268, (1968) · Zbl 0167.48305
[6] Braess, D.; Nagurney, A.; Wakolbinger, T., On a paradox of traffic planning, Transportation science, 39, 446-450, (2005), [Translation from the original in German, Braess (1968)]
[7] Bureau of Public Roads, 1964. Traffic assignment manual. Tech. rep., June, US Department of Commerce.
[8] Ceylan, H.; Bell, M.G.H., Genetic algorithm solution for the stochastic equilibrium transportation networks under congestion, Transportation research part B, 39, 169-185, (2005)
[9] Charnes, A.; Klingman, D., The more for less paradox in the distribution model, Cahiers du centre d’etudes de recherche operationelle, 13, 1, 11-22, (1971) · Zbl 0212.51201
[10] Cheah, J.; Smith, J.M., Generalized \(M / G / C / C\) state dependent queueing models and Pedestrian traffic flows, Queueing systems, 15, 365-386, (1994) · Zbl 0797.90028
[11] Cruz, F.R.B.; Smith, J.M., Approximate analysis of \(M / G / c / c\) state-dependent queueing networks, Computers and operations research, 34, 8, 2332-2344, (2007) · Zbl 1144.90345
[12] Dijkstra, E.W., A note on two problems in connection with graphs, Numerical mathematics, 1, 269-271, (1959) · Zbl 0092.16002
[13] Drake, J.S.; Schofer, J.L.; May, A.D., A statistical analysis of speed density hypotheses, Highway research record, 154, 53-87, (1967)
[14] Edie, L.C., Car following and steady-state theory, Operations research, 9, 66-76, (1961) · Zbl 0097.34002
[15] Fan, H.-Y.; Lampinen, J., A trigonometric mutation operation to differential evolution, Journal of global optimization, 27, 1, 105-129, (2004) · Zbl 1142.90509
[16] Frank, M.; Wolfe, P., An algorithm for quadratic programming, Naval research logistics quarterly, 3, 1-2, 95-110, (1956)
[17] García-Ródenas, R.; López-García, M.L.; Niño-Arbelaez, A.; Verastegui-Rayo, D., A continuous whole-link travel time model with occupancy constraint, European journal of operational research, 175, 3, 1455-1471, (2006) · Zbl 1142.90349
[18] Ghatee, M.; Hashemi, S.M., Traffic assignment model with fuzzy level of travel demand: an efficient algorithm based on quasi-logit formulas, European journal of operational research, 194, 2, 432-451, (2009) · Zbl 1154.90339
[19] Greenshields, B.D., A study of traffic capacity, Highway research board Proceedings, 14, 448-477, (1935)
[20] Hearn, D.W.; Lawphongpanich, S., A dual ascent algorithm for traffic assignment problems, Transportation research part B, 24, 6, 423-430, (1990)
[21] Helbing, D.; Schönhof, M.; Stark, H.-U.; Holyst, J.A., How individuals learn to take turns: emergence of alternating cooperation in a congestion game and the prisoners dilemma, Advances in complex systems, 8, 1, 87-116, (2005) · Zbl 1112.91012
[22] Ho, J.K., Solving the dynamic traffic assignment problem on a hypercube multicomputer, Transportation research part B, 24, 6, 443-451, (1990)
[23] Jain, R.; Smith, J.M., Modeling vehicular traffic flow using \(M / G / C / C\) state dependent queueing models, Transportation science, 31, 4, 324-336, (1997) · Zbl 0920.90064
[24] Kerbache, L.; Smith, J.M., Multi-objective routing within large scale facilities using open finite queueing networks, European journal of operational research, 121, 1, 105-123, (2000) · Zbl 0971.90014
[25] Kimber, R.M., Hollis, E.M., 1979. Traffic queues and delays at road junctions. Laboratory Report 909, Transport and Road Research Laboratory, Crowthorne, UK.
[26] Lampinen, J., 2000. A bibliography of differential evolution algorithm. Technical report, Laboratory of Information Processing, Department of Information Technology, Lappeenranta University of Technology. <http://www.lut.fi/ jlampine/debiblio.htm>.
[27] Lampinen, J.; Zelinka, I., Mechanical engineering design optimization by differential evolution, (), 127-146
[28] Larsson, T.; Patriksson, M., An augmented Lagrangean dual algorithm for link capacity side constrained traffic assignment problems, Transportation research part B, 29, 6, 433-455, (1995)
[29] Lieckens, K.; Vandaele, N., Reverse logistics network design with stochastic lead times, Computers and operations research, 34, 2, 395-416, (2007) · Zbl 1113.90023
[30] Mitchell, D.H.; Smith, J.M., Topological network design of Pedestrian networks, Transportation research part B, 35, 107-135, (2001)
[31] Moreno-Quintero, E., Optimal control of road freight flows by route choice inducement: A case from Mexico, European journal of operational research, 175, 3, 1588-1604, (2006) · Zbl 1142.90326
[32] Patriksson, M., Algorithms for computing traffic equilibria, Networks and spatial economics, 4, 23-38, (2006) · Zbl 1079.90141
[33] Poli, J.; Monteiro, L.H.A., Improving vehicle flow with traffic lights, Advances in complex systems, 8, 1, 59-63, (2005) · Zbl 1112.90317
[34] Prashker, J.N.; Bekhor, S., Some observations on stochastic user equilibrium and system optimum of traffic assignment, Transportation research part B, 34, 277-291, (2000)
[35] Price, K., Storn, R., 2006. Differential evolution. Website of DE as on August 2006, International Computer Science Institute, University of California, Berkeley. <http://www.icsi.berkeley.edu/ storn/code.html>.
[36] Pursals, S.C.; Garzón, F.G., Optimal building evacuation time considering evacuation routes, European journal of operational research, 192, 2, 692-699, (2009) · Zbl 1157.90356
[37] Sheffi, Y., Urban transportation networks: equilibrium analysis with mathematical programming methods, (1985), Prentice-Hall Englewood Cliffs, NJ
[38] Sheffi, Y.; Daganzo, C.F., Another ‘paradox’ of traffic flow, Transportation research, 12, 1, 43-46, (1978)
[39] Storn, R.; Price, K., Differential evolution: A simple and efficient heuristic for global optimization over continuous spaces, Journal of global optimization, 11, 4, 341-359, (1997) · Zbl 0888.90135
[40] Transportation Research Board, Highway capacity manual, (2000), National Research Council
[41] Underwood, R.T., Speed, volume, and density relationships: quality and theory of traffic flow, Yale bureau of highway traffic, 141-188, (1961)
[42] van Woensel, T.; Vandaele, N., Modelling traffic flows with queueing models: A review, Asia-Pacific journal of operational research, 24, 4, 435-461, (2007) · Zbl 1172.90356
[43] van Woensel, T.; Wuyts, B.; Vandaele, N., Validating state-dependent queueing models for uninterrupted traffic flows using simulation, 4OR: A quarterly journal of operations research, 4, 2, 159-174, (2006) · Zbl 1112.60072
[44] Watling, D., User equilibrium traffic network assignment with stochastic travel times and late arrival penalty, European journal of operational research, 175, 3, 1539-1556, (2006) · Zbl 1142.90359
[45] Yuhaski, S.J.; Smith, J.M., Modeling circulation systems in buildings using state dependent models, Queueing systems, 4, 319-338, (1989) · Zbl 0669.90050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.