Fitness-scaling adaptive genetic algorithm with local search for solving the Multiple Depot Vehicle Routing Problem

Shuihua Wang*, Zeyuan Lu, Ling Wei, Genlin Ji, Jiquan Yang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

49 Citations (Scopus)


The multi-depot vehicle routing problem is a well-known non-deterministic polynomial-time hard combinatorial optimization problem, which is crucial for transportation and logistics systems. We proposed a novel fitness-scaling adaptive genetic algorithm with local search (FISAGALS). The fitness-scaling technique converts the raw fitness value to a new value that is suitable for selection. The adaptive rates strategy changes the crossover and mutation probabilities depending on the fitness value. The local search mechanism exploits the problem space in a more efficient way. The experiments employed 33 benchmark problems. Results showed the proposed FISAGALS is superior to the standard genetic algorithm, simulated annealing, tabu search, and particle swarm optimization in terms of success instances and computation time. Furthermore, FISAGALS performs better than parallel iterated tabu search (PITS) and fuzzy logic guided genetic algorithm (FLGA), and marginally worse than ILS-RVND-SP in terms of the maximum gap. It performs faster than PITS and ILS-RVND-SP (a combination of iterated local search framework [ILS], a variable neighborhood descent with random neighborhood ordering [RVND] and the the set partitioning [SP] model) and slower than FLGA. In summary, FISAGALS is a competitive method with state-of-the-art algorithms.

Original languageEnglish
Pages (from-to)601-616
Number of pages16
Issue number7
Publication statusPublished - 1 Jul 2016
Externally publishedYes


  • Vehicle routing problem
  • adaptive rates
  • fitness scaling
  • genetic algorithm
  • local search
  • multi-depot vehicle routing problem


Dive into the research topics of 'Fitness-scaling adaptive genetic algorithm with local search for solving the Multiple Depot Vehicle Routing Problem'. Together they form a unique fingerprint.

Cite this