Solving Bus Terminal Location Problem Using Genetic Algorithm

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.

Authors:

• S. Babaie-Kafaki
• R. Ghanbari
• S.H. Nasseri
• E. Ardil

Keywords:

• Bus networks
• Genetic algorithm (GA)
• Locationproblem
• Mixed integer programming (MIP).

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.