Genetic-Algorithms-Based Approach for Bilevel Programming Models
Publication: Journal of Transportation Engineering
Volume 126, Issue 2
Abstract
Many decision-making problems in transportation system planning and management can be formulated as bilevel programming models, which are intrinsically nonconvex and hence difficult to solve for the global optimum. Therefore, successful implementations of bilevel models rely largely on the development of an efficient algorithm in handling realistic complications. In spite of various intriguing attempts that were made in solving the bilevel models, these algorithms are unfortunately either incapable of finding the global optimum or very computationally intensive and impractical for problems of a realistic size. In this paper, a genetic-algorithms-based (GAB) approach is proposed to efficiently solve these models. The performance of the algorithm is illustrated and compared with the previous sensitivity-analysis-based algorithm using numerical examples. The computation results show that the GAB approach is efficient and much simpler than previous heuristic algorithms. Furthermore, it is believed that the GAB approach can more likely achieve the global optimum based on the globality and parallelism of genetic algorithms.
Get full access to this article
View all available purchase options and get full access to this article.
References
1.
Allsop, R. E. ( 1989). “Evolving application of mathematical optimization in design and operation of individual signal-controlled road junctions.” Mathematics in transportation planning and control, J. D. Griffiths, ed., Clarendon Press, Oxford, England, 1–24.
2.
Asakura, Y., and Sasaki, T. (1990). “Formulation and feasibility test of optimal road network design model with endogenously determined travel demand.” Proc., 5th World Conf. on Transp. Res., Yokohama, Japan, 351–365.
3.
Chan, K. S., and Lam, H. K. (1998). “A sensitivity analysis based algorithm for determining the optimal detector density of the network with variable message sign.” Proc., 3rd Conf. of Hong Kong Soc. for Transp. Studies, The Hong Kong Polytechnic University, Hong Kong, 247–256.
4.
Fisk, C. S. (1984). “Game theory and transportation system modeling.” Transp. Res., 18B(4/5), 301–313.
5.
Friesz, T. L., Anandalingam, G., Mehta, N. J., Nam, K., Shah, S., and Tobin, R. L. (1993). “The multiobjective equilibrium network design problem revisited: A simulated annealing approach.” Eur. J. Operational Res., 65(1), 44–57.
6.
Friesz, T. L., Cho, H. J., Mehta, N. J., Tobin, R. L., and Anandalingam, G. (1992). “A simulated annealing approach to the network design problem with variational inequality constraints.” Transp. Sci., 26(1), 18–26.
7.
Golberg, D. E. (1989). Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading, Mass.
8.
LeBlanc, L., and Boyce, D. E. (1986). “A bi-level programming for exact solution of the network design problem with user-optimal flows.” Transp. Res., 20B(3), 259–265.
9.
Sheffi, Y. (1985). Urban transportation network. Prentice-Hall, Englewood Cliffs, N.J.
10.
Wong, S. C., and Yang, H. (1997). “Reserve capacity of a signal-controlled road network.” Transp. Res., 31B(5), 397–402.
11.
Yang, H. (1995). “Heuristic algorithms for the bilevel origin-destination matrix estimation problem.” Transp. Res., 29B(4), 231–242.
12.
Yang, H., and Bell, M. G. H. (1998). “Models and algorithms for road network design: A review and some new developments.” Transp Rev., 18(3), 257–278.
13.
Yang, H., and Lam, H. K. (1996). “Optimal road tolls under conditions of queuing and congestion.” Transp. Res., 30A(5), 319–332.
14.
Yang, H., and Yagar, S. (1994). “Traffic assignment and traffic control in general freeway-arterial corridor systems.” Transp. Res., 28B(6), 463–486.
15.
Yang, H., and Yagar, S., Iida, Y., and Asakura, Y. (1994). “An algorithm for the inflow control problem on urban freeway networks with user-optimal flows.” Transp. Res., 28B(2), 123–139.
Information & Authors
Information
Published In
Journal of Transportation Engineering
Volume 126 • Issue 2 • March 2000
Pages: 115 - 120
History
Received: Jan 26, 1999
Published online: Mar 1, 2000
Published in print: Mar 2000
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.