A new genetic approach for transport network design and optimization

• Autorzy: Dinu S. , Bordea G.
• Języki publikacji: EN

Abstrakty

EN

This paper presents an improved Genetic Algorithm to solve the Transportation Network Design Problem (CTNDP) with interactions among different links. The CTNDP is formulated in an optimal design as a bi-level programming model. A key factor in the present approach is the combination of diploid based complex-encoding with meiosis specific features. The novel mutation operator proposed is another improvement that leads to a better robustness and convergence stability. The computational results obtained by comparing the performance of the proposed algorithm and other Genetic Algorithms for a test network demonstrates its better local searching ability, as well as its high efficiency. Finally, suggestions for further research and extensions are given.

Słowa kluczowe

EN

genetic algorithm; bilevel programming; Network Design Problem; complex-encoding

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2011
• Tom: Vol. 59, nr 3
• Strony: 263--272
• Opis fizyczny: Bibliogr. 32 poz., rys., tab.

Twórcy

autor

Dinu S.

autor

Bordea G.

• Electronics, Electrotechnics and Informatics Department, Constanta Maritime University 104 Mircea cel Batran St., 900663 Constanta, Romania,

Bibliografia

• [1] J.G. Wardrop, “Some theoretical aspects of road traffic research”, Proc. Institute of Civil Engineers II, 325–378 (1952).
• [2] C.F. Daganzo and Y. Sheffi, “On stochastic models of traffic assignment”, Transportation Science 11 (3), 253–274 (1977).
• [3] L.N. Vicente and P.H Calamai, “Bilevel and multilevel programming. A bibliography review”, J. Global Optimization 5, 291–306 (1994).
• [4] M. Chen and A.S. Alfa, “Algorithms for solving Fisk’s stochastic traffic assignment model”, Transportation Science 25 (6), 405–411 (1991).
• [5] Z. Drezner and G.O. Wesolowsky, “Selecting an optimum configuration of one-way and two-way routes”, Transportation Science 31, 386–394 (1997).
• [6] S.N. Kuan, H.L.Ong, and K.M. Ng, “Applying metaheuristics to feeder bus network design problem”, Asia-Pacific J.Operational Research 21 (4), 543–560 (2004).
• [7] M.Y. Abdulaal and L.J. LeBlanc, “Continuous equilibrium network design models”, Transportation Research B 13, 19–32 (1979).
• [8] T.L. Friesz, H. Cho, N.Y. Mehta, and R.Tobin, “Simulated annealing methods for network design problems with variational inequality constraints”, Transportation Science 26 (1), 18–26 (1992).
• [9] Z.Y. Gao, H. Sun, and L. Shan, “A continuous equilibrium network design model and algorithm for transit systems”, Transportation Research B 38, 235–250 (2004).
• [10] D.A. Hensher, K.J. Button, K.E. Haynes, and P.R. Stopher, Handbook of Transport Geography and Spatial System, Elsevier, Amsterdam, 2004.
• [11] A. Nagurney, Spatial Equilibration in Transport Networks: Handbook of Transport Geography and Spatial Systems, Elsevier, Amsterdam, 2003.
• [12] Bureau of Public Roads, Traffic Assignment Manual, Dept. of Commerce, Urban Planning Division, Washington, 1964.
• [13] Federal Highway Administration, Traffing Monitoring Guide, http://www.fhwa.dot.gov/ohim/tmguide/index.htm (2011).
• [14] C. Hurkens, J. Keijsper, and L. Stougie, “Virtual private network design: a proof of the tree routing conjecture on ring networks”, Siam J. Discrete Mathematics 21, 482–503 (2007).
• [15] K. Peric and M. Boile, “A combined model for intermodal networks with variable transit frequencies”, Proc. 85th Annual Transportation Research Board Meeting, Washington SAD 1, 136–145 (2006).
• [16] P. Marcotte and G. Marquis, “Efficient implementation of heuristics for the continuous network design problem”, Annals of Operations Research 34, 163–176 (1992).
• [17] C. Suwansirikul, T.L. Friesz, and R.L. Tobin, “Equilibrium decomposed optimization: a heuristic for the continuous equilibrium network design problem”, Transportation Science 21, 254–263 (1987).
• [18] H. Mourani, M. Ozden, P. Maynard-Zhang, and F. Moore, “Applying genetic algorithms to queuing network design”, J. Automation and Systems Engineering 1 (1), 32–39 (2007).
• [19] S.B. Pattnaik, S. Mohan, and V.M. Tom, “Urban bus transit network design using genetic algorithm”, J. Transportation Engineering 124 (4), 368–375 (1998).
• [20] A. Karoonsoontawong and S. T. Waller, “Dynamic continuous network design problem: linear bi-level programming and metaheuristic approaches”, J. Transportation Research Board 1964, 104–117 (2006).
• [21] L. Dung-Ying and S. T. Waller, “A quantum-inspired genetic algorithm for dynamic continuous network design problem”, Int. J. Transportation Research 1 (1), 81–93 (2009).
• [22] W. Fan and R. Machemehl, “Optimal transit route network design problem with variable transit demand: genetic algorithm approach”, J. Transportation Engineering 132, 40–51 (2006).
• [23] S. Ngamchai and D.J. Lovell, “Optimal time transfer in bus transit route network design using a genetic algorithm”, J. Transportation Engineering 129 (5), 510–521 (2003).
• [24] K. Jeon, J.S. Lee, S. Ukkusuri, and S.T.Waller, “New approach for relaxing computational complexity of discrete network design problem using selectorecombinative genetic algorithm,” Proc. Transportation Research Board’s 85th Annual Meeting 1, CD-ROM (2006).
• [25] Y.E. Xiong and J.B. Schneider, “Transportation network design using a cumulative genetic algorithm and neural network”, Transportation Research Record 1364, 37–44 (1993).
• [26] J.H. Holland, “Adaptation in natural and artificial systems: an introductory analysis with applications to biology”, Control and Artificial Intelligence 1, CD-ROM (1992).
• [27] R. Calabretta, R. Galbiati, S. Nolfi, and D. Parisi, “Two is better than one: a diploid genotype for neural networks”, Neural Processing Letters 4, 1–7 (1996).
• [28] Y. Wang, S. Gao, H. Zhang, and Z. Tang, “An improved genetic algorithm based complex-valued encoding”, IJCSNS Int. J. Computer Science and Network Security 10 (6), 168–174 (2010).
• [29] F.A. Kidwai, B.R. Marwah, K. Deb, and M.R. Karim, “A genetic algorithm based bus scheduling model for transit network”, Proc. Eastern Asia Society for Transportation Studies 5, 447–489 (2005).
• [30] S. Dinu and R. Pacuraru, “An intelligent modeling method based on genetic algorithm for partner selection in virtual organizations“, Business and Economic Horizons 5, CD-ROM (2011).
• [31] Z. Michalewicz, T. Logan, and S. Swaminathan, “Evolutionary operators for continuous convex parameter space”, Proc. Third Annual Conf. on Evolutionary Programming 1, 84–97, (1994).
• [32] M.A. Tabarzad, C. Lucas, and A. Hamzeh, “Statistical genetic algorithm”, Trans. on Engineering, Computing and Technology 14, 100–104 (2006).