Combining biased randomization with iterated local search for solving the multidepot vehicle routing problem

This paper proposes a hybrid approach for solving the multidepot vehicle routing problem (MDVRP) with a limited number of identical vehicles per depot. Our approach, which only uses a few parameters, combines biased randomizationuse of nonsymmetric probability distributions to generate randomnesswith the iterated local search (ILS) metaheuristic. Two biased-randomized processes are employed at different stages of the ILS framework in order to (a) assign customers to depots following a randomized priority criterionthis allows for fast generation of alternative allocation maps and (b) improving routing solutions associated with a promising allocation mapthis is done by randomizing the classical savings heuristic. These biased-randomized processes rely on the use of the geometric probability distribution, which is characterized by a single and bounded parameter. Being an approach with few parameters, our algorithm does not require troublesome fine-tuning processes, which tend to be time consuming. Using standard benchmarks, the computational experiments show the efficiency of the proposed algorithm. Despite its hybrid nature, our approach is relatively easy to implement and can be parallelized in a very natural way, which makes it an interesting alternative for practical applications of the MDVRP.