Because of the limitation of budget, in the planning of road works, increased efforts should be made on links that are more critical to the whole traffic system. Therefore, it would be helpful to model and evaluate the vulnerability and reliability of the transportation network when the network design is processing. This paper proposes a bilevel transportation network design model, in which the upper level is to minimize the performance of the network under the given budgets, while the lower level is a typical user equilibrium assignment problem. A new solution approach based on particle swarm optimization (PSO) method is presented. The topological effects on the performance of transportation networks are studied with the consideration of three typical networks, regular lattice, random graph, and small-world network. Numerical examples and simulations are presented to demonstrate the proposed model. 1. Introduction The network design problem (NDP) involves the optimal decision on the expansion of an urban street and highway system in response to a growing demand for travel. It has emerged as an important area for progress in handling effective transport planning, because the demand for travel on the roads is growing at a rate faster than our urban transport systems can ever hope to accommodate, while resources available for expanding the system capacity remain limited. The objective of NDP is to optimize a given system performance measure such as to minimize total system travel cost, while accounting for the route choice behavior of network users [1]. The decisions made by road planners influence the route choice behavior of network users, which is normally described by a network user equilibrium model. Mathematically, the bilevel programming is a good technique to describe this hierarchical property of the NDP with an equilibrium constraint. Generally the upper level problem is to minimize the total system cost and the lower level problem is to characterize the UE traffic flow pattern ([2, 3]). Studies have been overwhelmingly focused on the continuous network design problem (CNDP) and substantial achievements in algorithmic development have been made. Abdulaal and LeBlanc [4] formulated the CNDP under deterministic user equilibrium (DUE) as a bilevel programming model and the Hooke-Jeeves heuristic algorithm was also introduced. As an application, Friesz et al. [5] used a simulated annealing approach to solve the multiobjective equilibrium network design problem as a single level minimization problem. Marcotte [6] transferred the CNDP into a single
References
[1]
H. Yang and M. G. H. Bell, “Models and algorithms for road network design: a review and some new developments,” Transport Reviews, vol. 18, no. 3, pp. 257–278, 1998.
[2]
Z. Gao, H. Sun, and H. Zhang, “A globally convergent algorithm for transportation continuous network design problem,” Optimization and Engineering, vol. 8, no. 3, pp. 241–257, 2007.
[3]
Z. Y. Gao and Y. F. Song, “A reserve capacity model of optimal signal control with user-equilibrium route choice,” Transportation Research B, vol. 36, no. 4, pp. 313–323, 2002.
[4]
M. Abdulaal and L. J. LeBlanc, “Continuous equilibrium network design models,” Transportation Research B, vol. 13, no. 1, pp. 19–32, 1979.
[5]
T. L. Friesz, G. Anandalingam, N. J. Mehta, K. Nam, S. J. Shah, and R. L. Tobin, “The multiobjective equilibrium network design problem revisited: a simulated annealing approach,” European Journal of Operational Research, vol. 65, no. 1, pp. 44–57, 1993.
[6]
P. Marcotte, “Network optimization with continuous control parameters,” Transportation Science, vol. 17, no. 2, pp. 181–197, 1983.
[7]
Q. Meng, H. Yang, and M. G. H. Bell, “An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem,” Transportation Research B, vol. 35, no. 1, pp. 83–105, 2001.
[8]
V. Latora and M. Marchiori, “Efficient behavior of small-world networks,” Physical Review Letters, vol. 87, no. 19, Article ID 198701, 2001.
[9]
V. Latora and M. Marchiori, “Economic small-world behavior in weighted networks,” European Physical Journal B, vol. 32, no. 2, pp. 249–263, 2003.
[10]
V. Latora and M. Marchiori, “How the science of complex networks can help developing strategies against terrorism,” Chaos, Solitons and Fractals, vol. 20, no. 1, pp. 69–75, 2004.
[11]
Q. Qiang and A. Nagurney, “A unified network performance measure with importance identification and the ranking of network components,” Optimization Letters, vol. 2, no. 1, pp. 127–142, 2008.
[12]
D. Zhu, Y. Hu, Y. Li, and B. Yu, A New Measure For Airline Networks Performance Evaluation and Critical Cities Identification, Fudan University, Shanghai, China, 2006.
[13]
E. Jenelius, T. Petersen, and L.-G. Mattsson, “Importance and exposure in road network vulnerability analysis,” Transportation Research A, vol. 40, no. 7, pp. 537–560, 2006.
[14]
P. M. Murray-Tuite and H. S. Mahmassani, “Methodology for determining vulnerable links in a transportation network,” Transportation Research Record, vol. 1882, pp. 88–96, 2004.
[15]
D. E. Boyce, “Urban transportation network equilibrium and design models: recent achievements and future prospectives,” Environment and Planning, vol. 16A, pp. 1445–1474, 1984.
[16]
Y. Sheffi, Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods, Prentice-Hall, Englewood Cliffs, NJ, USA, 1985.
[17]
J. Kennedy and R. Eberhart, “Particle swarm optimization,” in Proceedings of the IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948, Perth, Australia, December 1995.
[18]
K. Premalatha and A. M. Natarajan, “A new approach for data clustering based on PSO with local search,” Computer and Information Science, vol. 1, no. 4, pp. 139–145, 2008.
[19]
P. C. Fourie and A. A. Groenwold, “The particle swarm optimization algorithm in size and shape optimization,” Structural and Multidisciplinary Optimization, vol. 23, no. 4, pp. 259–267, 2002.
[20]
P. Erd？s and A. Rényi, “On the evolution of random graphs,” Publications of the Mathematical Institute of the Hungarian Academy of Science, vol. 5, pp. 17–61, 1960.
[21]
D. J. Watts and S. H. Strogatz, “Collective dynamics of “small-world” networks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998.
[22]
S. Boccaletti, V. Latora, Y. Moreno, M. Chavez, and D.-U. Hwang, “Complex networks: structure and dynamics,” Physics Reports, vol. 424, no. 4-5, pp. 175–308, 2006.
