Journal
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH
Volume 22, Issue 4, Pages 647-667Publisher
WILEY
DOI: 10.1111/itor.12101
Keywords
multidepot vehicle routing problem; metaheuristics; randomized algorithms; biased randomization; iterated local search; parallelization of heuristics
Funding
- Spanish Ministry of Science and Innovation [TRA2013-48180-C3-3-P]
- CYTED-HAROSA Network
- NICTA
- Australian Government through the Department of Communications
- Australian Research Council through the ICT Centre of Excellence Program
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available