An Improved Immune Genetic Algorithm for Capacitated Vehicle Routing Problem

ABSTRACT

The capacitated vehicle routing problem is an NP-hard problem. In this paper, it proposes a kind of dynamically adaptive immune genetic algorithm with automatic immune monitoring function. By setting an immune monitor, the algorithm automatically obtains the timing of regulating the antibody concentration and vaccination, and the dynamic antibody concentration regulation mechanism is designed to keep the variety of the antibody evolution process and prevent the algorithm from getting in trouble with local optimal solution. What is more, the manner of vaccination and extraction is designed to improve the global optimization of the algorithm, and the elite antibodies ensure the convergence. The experiment results show that the improved immune genetic algorithm takes good performance on the capacitated vehicle routing problem.

Keywords: