An improved fireworks algorithm for the capacitated vehicle routing problem

摘要

The capacitated vehicle routing problem (CVRP), which aims at minimizing travel costs, is a well-known NP-hard combinatorial optimization. Owing to its hardness, many heuristic search algorithms have been proposed to tackle this problem. This paper explores a recently proposed heuristic algorithm named the fireworks algorithm (FWA), which is a swarm intelligence algorithm. We adopt FWA for the combinatorial CVRP problem with several modifications of the original FWA: it employs a new method to generate “sparks” according to the selection rule, and it uses a new method to determine the explosion amplitude for each firework. The proposed algorithm is compared with several heuristic search methods on some classical benchmark CVRP instances. The experimental results show a promising performance of the proposed method. We also discuss the strengths and weaknesses of our algorithm in contrast to traditional algorithms.