A multi-crossover and adaptive island based population algorithm for solving routing problems

Eneko OSABA; Enrique ONIEVA; Roberto CARBALLEDO; Fernando DIAZ; Asier PERALLOS; Xiao ZHANG

doi:10.1631/jzus.C1300184

Your Location：

Home >

Browse articles >

A multi-crossover and adaptive island based population algorithm for solving routing problems

Computer & Automation | Updated：2022-12-09

- A multi-crossover and adaptive island based population algorithm for solving routing problems
- A multi-crossover and adaptive island based population algorithm for solving routing problems
- Frontiers of Information Technology & Electronic Engineering Vol. 14, Issue 11, Pages: 815-821(2013)
- Affiliations：
  
  Deusto Institute of Technology (DeustoTech), University of Deusto, Bilbao 48007, Spain
- Author bio：
  
  [ "Eneko OSABA, E-mail: e.osaba@deusto.es" ]
  [ "Enrique ONIEVA, E-mail: enrique.onieva@deusto.es" ]
  [ "Roberto CARBALLEDO, E-mail: roberto.carballedo@deusto.es" ]
  [ "Fernando DIAZ, E-mail: fernando.diaz@deusto.es" ]
  [ "Asier PERALLOS, E-mail: perallos@deusto.es" ]
  [ "Xiao ZHANG, E-mail: xiao.zhang@deusto.es" ]
- Funds：
- DOI：10.1631/jzus.C1300184
  CLC： TP273
- Received：09 July 2013，
  
  Revised：2013-10-15，
  
  Published：2013-11
- Accepted：
Scan QR Code
Eneko OSABA, Enrique ONIEVA, Roberto CARBALLEDO, et al. A multi-crossover and adaptive island based population algorithm for solving routing problems[J]. Frontiers of Information Technology & Electronic Engineering, 2013, 14(11): 815-821.
DOI：

Eneko OSABA, Enrique ONIEVA, Roberto CARBALLEDO, et al. A multi-crossover and adaptive island based population algorithm for solving routing problems[J]. Frontiers of Information Technology & Electronic Engineering, 2013, 14(11): 815-821. DOI： 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

references

S. Anbuudayasankar , , , K. Ganesh , , , S.C. Lenny Koh , , , Y. Ducq . . Modified savings heuristics and genetic algorithm for bi-objective vehicle routing problem with forced backhauls . . Expert Syst. Appl. , , 2012 . . 39 ( ( 3 ): ): 2296 - - 2305 . . DOI: 10.1016/j.eswa.2011.08.009 http://doi.org/10.1016/j.eswa.2011.08.009 . .

J. Bae , , , S. Rathinam . . Approximation algorithms for multiple terminal, Hamiltonian path problems . . Optim. Lett. , , 2012 . . 6 ( ( 1 ): ): 69 - - 85 . . DOI: 10.1007/s11590-010-0252-4 http://doi.org/10.1007/s11590-010-0252-4 . .

E. Cantú-Paz . . A survey of parallel genetic algorithms . . Calcul. Parall. Res. Syst. Rep. , , 1998 . . 10 ( ( 2 ): ): 141 - - 171 . . . .

L. Davis . . Applying Adaptive Algorithms to Epistatic Domains . . Proc. Int. Joint Conf. on Artificial Intelligence , , 1985 . . p.161 - - 163 . . . .

K. de Jong . . Analysis of the Behavior of a Class of Genetic Adaptive Systems . . University of Michigan, Michigan, USA , , 1975 . . .

D. Goldberg . . Genetic Algorithms in Search, Optimization, and Machine Learning . . Addison-Wesley Professional, Boston, USA , , 1989 . . .

B. Golden , , , E. Baker , , , J. Alfaro , , , J. Schaffer . . The Vehicle Routing Problem with Backhauling: Two Approaches . . Proc. 21st Annual Meeting of SETIMS , , 1985 . . p.90 - - 92 . . . .

J.H. Holland . . Adaptation in Natural and Artificial Systems: an Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence . . MIT Press, Michigan, USA , , 1975 . . .

G. Laporte . . The vehicle routing problem: an overview of exact and approximate algorithms . . Eur. J. Oper. Res. , , 1992 . . 59 ( ( 3 ): ): 345 - - 358 . . DOI: 10.1016/0377-2217(92)90192-C http://doi.org/10.1016/0377-2217(92)90192-C . .

P. Larranaga , , , C.M.H. Kuijpers , , , R.H. Murga , , , I. Inza , , , S. Dizdarevic . . Genetic algorithms for the travelling salesman problem: a review of representations and operators . . Artif. Intell. Rev. , , 1999 . . 13 ( ( 2 ): ): 129 - - 170 . . DOI: 10.1023/A:1006529012972 http://doi.org/10.1023/A:1006529012972 . .

E. Lawler , , , J. Lenstra , , , A. Kan , , , D. Shmoys . . The Traveling Salesman Problem: a Guided Tour of Combinatorial Optimization, Volume 3 . . Wiley, New York, USA , , 1985 . . .

S. Lin . . Computer solutions of the traveling salesman problem . . Bell Syst. Techn. J. , , 1965 . . 44 ( ( 10 ): ): 2245 - - 2269 . . DOI: 10.1002/j.1538-7305.1965.tb04146.x http://doi.org/10.1002/j.1538-7305.1965.tb04146.x . .

M. Martínez-Torres . . A genetic search of patterns of behaviour in OSS communities . . Expert Syst. Appl. , , 2012 . . 39 ( ( 18 ): ): 13182 - - 13192 . . DOI: 10.1016/j.eswa.2012.05.083 http://doi.org/10.1016/j.eswa.2012.05.083 . .

G. Mattos Ribeiro , , , G. Laporte . . An adaptive large neighborhood search heuristic for the cumulative capacitated vehicle routing problem . . Comput. Oper. Res. , , 2012 . . 39 ( ( 3 ): ): 728 - - 735 . . DOI: 10.1016/j.cor.2011.05.005 http://doi.org/10.1016/j.cor.2011.05.005 . .

I. Moon , , , J.H. Lee , , , J. Seong . . Vehicle routing problem with time windows considering overtime and outsourcing vehicles . . Expert Syst. Appl. , , 2012 . . 39 ( ( 18 ): ): 13202 - - 13213 . . DOI: 10.1016/j.eswa.2012.05.081 http://doi.org/10.1016/j.eswa.2012.05.081 . .

S. Mukherjee , , , S. Ganguly , , , S. Das . . A strategy adaptive genetic algorithm for solving the travelling salesman problem . . LNCS , , 2012 . . 7677 778 - - 784 . . DOI: 10.1007/978-3-642-35380-2_91 http://doi.org/10.1007/978-3-642-35380-2_91 . .

S. Ngueveu , , , C. Prins , , , R. Wolfler Calvo . . An effective memetic algorithm for the cumulative capacitated vehicle routing problem . . Comput. Oper. Res. , , 2010 . . 37 ( ( 11 ): ): 1877 - - 1885 . . DOI: 10.1016/j.cor.2009.06.014 http://doi.org/10.1016/j.cor.2009.06.014 . .

B. Niu , , , Y. Zhu , , , X. He , , , H. Wu . . MCPSO: a multiswarm cooperative particle swarm optimizer . . Appl. Math. Comput. , , 2007 . . 185 ( ( 2 ): ): 1050 - - 1062 . . DOI: 10.1016/j.amc.2006.07.026 http://doi.org/10.1016/j.amc.2006.07.026 . .

E. Osaba , , , R. Carballedo , , , F. Diaz , , , A. Perallos . . Analysis of the Suitability of Using Blind Crossover Operators in Genetic Algorithms for Solving Routing Problems . . Proc. 8th Int. Symp. on Applied Computational Intelligence and Informatics , , 2013 . . p.17 - - 23 . . . .

S. Ray , , , S. Bandyopadhyay , , , S. Pal . . New Operators of Genetic Algorithms for Traveling Salesman Problem . . Proc. 17th Int. Conf. on Pattern Recognition , , 2004 . . p.497 - - 500 . . . .

G. Reinelt . . TSPLIB: a traveling salesman problem library . . ORSA J. Comput. , , 1991 . . 3 ( ( 4 ): ): 376 - - 384 . . DOI: 10.1287/ijoc.3.4.376 http://doi.org/10.1287/ijoc.3.4.376 . .

S.C. Sarin , , , H.D. Sherali , , , L. Yao . . New formulation for the high multiplicity asymmetric traveling salesman problem with application to the Chesapeake problem . . Optim. Lett. , , 2011 . . 5 ( ( 2 ): ): 259 - - 272 . . DOI: 10.1007/s11590-010-0205-y http://doi.org/10.1007/s11590-010-0205-y . .

J.D. Schaffer , , , A. Morishima . . An Adaptive Crossover Distribution Mechanism for Genetic Algorithms . . Proc. 2nd Int. Conf. on Genetic Algorithms and Their Application , , 1987 . . p.36 - - 40 . . . .

W.M. Spears . . Adapting Crossover in Evolutionary Algorithms . . Proc. Conf. on Evolutionary Programming , , 1995 . . p.367 - - 384 . . . .

G. Syswerda . . Schedule Optimization Using Genetic Algorithms. In : Handbook of Genetic Algorithms . . Van Nostrand Reinhold, New York, USA , , 1991 . . p.332 - - 349 . . . .

P.W. Tsai , , , J.S. Pan , , , B.Y. Liao , , , S.C. Chu . . Enhanced artificial bee colony optimization . . Int. J. Innov. Comput. Inf. Control , , 2009 . . 5 ( ( 12 ): ): 5081 - - 5092 . . . .

L. Wang , , , D.B. Tang . . An improved adaptive genetic algorithm based on hormone modulation mechanism for job-shop scheduling problem . . Expert Syst. Appl. , , 2011 . . 38 ( ( 6 ): ): 7243 - - 7250 . . DOI: 10.1016/j.eswa.2010.12.027 http://doi.org/10.1016/j.eswa.2010.12.027 . .

D. Whitley , , , S. Rana , , , R.B. Heckendorn . . The island model genetic algorithm: on separability, population size and convergence . . J. Comput. Inf. Technol. , , 1999 . . 7 33 - - 48 . . . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰