Authors
Elyn Solano-Charris, Christian Prins, Andréa Cynthia Santos,
Title
Local search based metaheuristics for the robust vehicle routing problem with discrete scenarios
In
Applied Soft Computing
Volume
32
Pages
518–531
Publisher
Elsevier
Year
2015
Publisher's URL
http://www.sciencedirect.com/science/article/pii/S1568494615002380
Indexed by
Abstract
The Capacitated Vehicle Routing Problem (CVRP) is extended here to handle uncertain arc costs without resorting to probability distributions, giving the Robust VRP(RVRP). The unique set of arc costs in the CVRP is replaced by a set of discrete scenarios. A scenario is for instance the travel time observed on each arc at a given traffic hour. The goal is to build a set of routes using the lexicographic min–max criterion: the worst cost over all scenarios is minimized but ties are broken using the other scenarios, from the worst to the best. This version of robust CVRP has never been studied before. A Mixed Integer Linear Program (MILP), two greedy heuristics, a local search and four metaheuristics are proposed: a Greedy Randomized Adaptive Search Procedure, an Iterated Local Search (ILS), a Multi-Start ILS (MS-ILS), and an MS-ILS based on Giant Tours (MS-ILS-GT) converted into feasible routes via a lexicographic splitting procedure. The greedy heuristics provide the other algorithms with good initial solutions. Tests on small instances (10-20 customers, 2-3 vehicles, 10-30 scenarios) show that the four metaheuristics retrieve all optima found by the MILP. On larger cases with 50-100 customers, 5-20 vehicles and 10-20 scenarios, MS-ILS-GT dominates the other approaches. As our algorithms share the same components (initial heuristic, local search), the positive contribution of using the giant tour approach is confirmed on the RVRP.
Affiliations
Offprint