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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:51336", author = "S. Babaie-Kafaki and R. Ghanbari and S.H. Nasseri and E. Ardil", title = "Solving Bus Terminal Location Problem Using Genetic Algorithm", 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).", volume = "2", number = "2", pages = "71-4", }