Solving Bus Terminal Location Problem Using Genetic Algorithm

Authors: S. Babaie-Kafaki, R. Ghanbari, S.H. Nasseri, E. Ardil

Abstract:

Bus networks design is an important problem in public transportation. The main step to this design, is determining the number of required terminals and their locations. This is an especial type of facility location problem, a large scale combinatorial optimization problem that requires a long time to be solved. The genetic algorithm (GA) is a search and optimization technique which works based on evolutionary principle of natural chromosomes. Specifically, the evolution of chromosomes due to the action of crossover, mutation and natural selection of chromosomes based on Darwin's survival-of-the-fittest principle, are all artificially simulated to constitute a robust search and optimization procedure. In this paper, we first state the problem as a mixed integer programming (MIP) problem. Then we design a new crossover and mutation for bus terminal location problem (BTLP). We tested the different parameters of genetic algorithm (for a sample problem) and obtained the optimal parameters for solving BTLP with numerical try and error.

Keywords: Bus networks, Genetic algorithm (GA), Locationproblem, Mixed integer programming (MIP).

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330119

References:

[1] H. Aashtiani, B. Hejazi, Solving Bus Terminal Location Problem Using Simulated Annealing Method, to appear in: Esteghlal, Volume 2, March 2001 (in Persian).
[2] Stephen P. Bradley, Arnoldo C. Hax, Thomas L. Magnanti, Applied Mathematical Programming, ADDISON-WESLEY PUBLISHING COMPANY, 1976.
[3] Robert S. Garfinkel, George L. Nemhauser, Integer Programming, JOHN WILEY & SONS, 1972.
[4] D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, ADDISON-WESLEY PUBLISHING COMPANY, 1989.
[5] D. Goldberg and R. Lingle, Alleles, loci and traveling salesman problem, In J.J. Grefenstette, editor, Proceedings of International Conference on GAs, Lawrence Erlbaum, 1985.
[6] J.H. Holland, Adaptation in Natural and Artificial Systems, The University of Michigan Press, Ann Arbor, Michigan, 1975.
[7] Alden H. Wright, Genetic Algorithm for Real Parameter Optimization, to appear in: Foundations of Genetic Algorithms, 1991.
[8] R. Ghanbari, Jaszkiewicz-s Genetic Local search for Solving Molti- Objective Combinatorial Optimization, M.Sc. Thesis, Supervisor: N. Mahdavi-Amiri, Department of Mathematical Sciences, sharif Univarsity of Technology, November 2004.