Integrated network capacity expansion and traffic signal optimization problem: Robust bi-level dynamic formulation. (English) Zbl 1202.90030

Summary: This paper presents a robust optimization formulation, with an exact solution method, that simultaneously solves continuous network capacity expansion, traffic signal optimization and dynamic traffic assignment when explicitly accounting for an appropriate robustness measure, the inherent bi-level nature of the problem and long-term O-D demand uncertainty. The adopted robustness measure is the weighted sum of expected total system travel time (TSTT) and squared up-side deviation from a fixed target. The model propagates traffic according to Daganzo’s cell transmission model. Furthermore, we formulate five additional, related models. We find that when evaluated in terms of robustness, the integrated robust model performs the best, and interestingly the sequential robust approach yields a worse solution compared to certain sequential and integrated approaches. Although the adopted objective of the integrated robust model does not directly optimize the variance of TSTT, our experimental results show that the robust solutions also yield the least-variance solutions.


90B06 Transportation, logistics and supply chain management
90B20 Traffic problems in operations research
90C90 Applications of mathematical programming


Full Text: DOI


[1] Bard JF (1998) Practical bilevel optimization algorithms and applications. Kluwer Academic, Dordrecht · Zbl 0943.90078
[2] Birge JR, Louveaux F (1997) Introduction to stochastic programming. Springer, New York · Zbl 0892.90142
[3] Chiou S-W (2005) Modeling a continuous network design problem for signal-controlled road network. Presented at 84th Annual Meeting of the Transportation Research Board, Washington, D.C
[4] Daganzo CF (1994) The cell transmission model: a simple dynamic representation of highway traffic consistent with the hydrodynamic theory. Transp Res 28B:269–287
[5] Fortuny-Amat J, McCarl B (1981) A representation and economic interpretation of a two-level programming problem. J Oper Res Soc 32:783–792. doi: 10.2307/2581394 · Zbl 0459.90067
[6] Grossmann IE, Viswanathan J, Vecchietti A, Raman R, Kalvelagen E (2002) GAMS/DICOPT: a discrete continuous optimization package. GAMS Development Corporation, Washington, D.C
[7] Infanger G (1992) Monte Carlo (Importance) Sampling with a benders decomposition algorithm for stochastic linear programs. Ann Oper Res 39:69–95. doi: 10.1007/BF02060936 · Zbl 0773.90054
[8] Kalantari B, Rosen JB (1982) Penalty for zero-one equivalent problem. Math Program 24:229–232. doi: 10.1007/BF01585106 · Zbl 0539.90074
[9] Kall P, Wallace SW (1994) Stochastic programming. Wiley, Chichester · Zbl 0812.90122
[10] Karoonsoontawong A (2006) Robustness approach to the integrated network design problem, signal optimization and dynamic traffic assignment problem. Ph.D. Dissertation, The University of Texas at Austin
[11] Karoonsoontawong A, Waller ST (2005) A comparison of system- and user-optimal stochastic dynamic network design models using Monte Carlo bounding techniques. J Transp Res Board 1923:1–102
[12] Karoonsoontawong A, Waller ST (2006) Dynamic continuous network design problem: linear bi-level programming and metaheuristics. J Transp Res Board 1964:104–117
[13] Karoonsoontawong A, Waller ST (2007) Robust dynamic continuous network design problem. J Transp Res Board 2029:58–71
[14] Lee C (1998) Combined traffic signal control and traffic assignment: algorithms, implementation and numerical results. Ph.D. Dissertation, The University of Texas at Austin, Austin, Texas
[15] Mak W, Morton DP, Wood RK (1999) Monte Carlo bounding techniques for determining solution quality in stochastic programs. Oper Res Lett 24:47–56. doi: 10.1016/S0167-6377(98)00054-6 · Zbl 0956.90022
[16] Markowitz H (1991) Portfolio selection, efficiency diversification of investments. Cowles Foundation Monograph 16, Yale University Press, New Haven, Conn., 1959 (second edition, Basil Blackwell, Cambridge
[17] Morton DP (2006) Personal discussion. Operations Research and Industrial Engineering Program, The University of Texas at Austin
[18] Mulvey JM, Vanderbei RJ, Zenios SA (1995) Robust optimization of large scale systems. Oper Res 43(2):264–281 · Zbl 0832.90084
[19] Munoz L, Xiaotian S, Sun D, Gomes G, Horowitz R (2004) Methodological calibration of the cell transmission model. Proceeding of the 2004 American Control Conference, Boston, Massachusetts
[20] Ran B, Boyce DE (1996) A link-based variational inequality formulation of ideal dynamic user-optimal route choice problem. Transp Res Part C 4(1):1–12. doi: 10.1016/0968-090X(95)00017-D
[21] Ukkusuri SVSK (2002) Linear programs for the user optimal dynamic traffic assignment problem. Master’s Thesis, University of Illinois at Urbana-Champaign
[22] Ukkusuri SV, Waller ST (2007) Linear programming models for the user and system optimal dynamic network design problem: formulations, comparisons and extensions. Networks and Spatial Economics. doi: 10.1007/s11067-007-9019-6
[23] Von Stackelberg H (1952) The theory of the market economy. Oxford University Press, Oxford
[24] Waller ST (2000) Optimization and control of stochastic dynamic transportation systems: formulations, solution methodologies, and computational experience. Ph.D. Dissertation, Northwestern University
[25] Waller ST, Ziliaskopoulos AK (2006) A combinatorial user optimal dynamic traffic assignment algorithm. Annual Operations Research, ISSN: 0254-5330, 1572-9338 · Zbl 1156.90324
[26] Ziliaskopoulos AK (2000) A linear programming model for the single destination system optimum dynamic traffic assignment problem. Transp Sci 34(1):37–49. doi: 10.1287/trsc. · Zbl 1002.90013
[27] Ziyou G, Yifan S (2002) A reserve capacity model of optimal signal control with user-equilibrium route choice. Transp Res Part B 36:313–323. doi: 10.1016/S0191-2615(01)00005-4
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.