A multi-crossover and adaptive island based population algorithm for solving routing problems
- 9 November 2013
- journal article
- research article
- Published by Zhejiang University Press in Journal of Zhejiang University SCIENCE C
- Vol. 14 (11), 815-821
- https://doi.org/10.1631/jzus.c1300184
Abstract
We propose a multi-crossover and adaptive island based population algorithm (MAIPA). This technique divides the entire population into subpopulations, or demes, each with a different crossover function, which can be switched according to the efficiency. In addition, MAIPA reverses the philosophy of conventional genetic algorithms. It gives priority to the autonomous improvement of the individuals (at the mutation phase), and introduces dynamism in the crossover probability. Each subpopulation begins with a very low value of crossover probability, and then varies with the change of the current generation number and the search performance on recent generations. This mechanism helps prevent premature convergence. In this research, the effectiveness of this technique is tested using three well-known routing problems, i.e., the traveling salesman problem (TSP), capacitated vehicle routing problem (CVRP), and vehicle routing problem with backhauls (VRPB). MAIPA proves to be better than a traditional island based genetic algorithm for all these three problems.Keywords
This publication has 13 references indexed in Scilit:
- A genetic search of patterns of behaviour in OSS communitiesExpert Systems with Applications, 2012
- Vehicle routing problem with time windows considering overtime and outsourcing vehiclesExpert Systems with Applications, 2012
- An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problemComputers & Operations Research, 2012
- Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhaulsExpert Systems with Applications, 2011
- An effective memetic algorithm for the cumulative capacitated vehicle routing problemComputers & Operations Research, 2010
- Approximation algorithms for multiple terminal, Hamiltonian path problemsOptimization Letters, 2010
- MCPSO: A multi-swarm cooperative particle swarm optimizerApplied Mathematics and Computation, 2007
- Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and OperatorsArtificial Intelligence Review, 1999
- The vehicle routing problem: An overview of exact and approximate algorithmsEuropean Journal of Operational Research, 1992
- Computer Solutions of the Traveling Salesman ProblemBell System Technical Journal, 1965