z-logo
Premium
Combining biased randomization with iterated local search for solving the multidepot vehicle routing problem
Author(s) -
Juan Angel A.,
Pascual Iñaki,
Guimarans Daniel,
Barrios Barry
Publication year - 2015
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12101
Subject(s) - iterated local search , vehicle routing problem , randomness , mathematical optimization , computer science , iterated function , heuristic , routing (electronic design automation) , bounded function , randomized algorithm , local search (optimization) , algorithm , mathematics , statistics , computer network , mathematical analysis
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 randomization”—use of nonsymmetric probability distributions to generate randomness—with 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 criterion—this allows for fast generation of alternative allocation maps and (b) improving routing solutions associated with a “promising” allocation map—this 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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here