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

摘要

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.