Metaheuristics for the robust vehicle routing problem with discrete scenarios
Résumé
The robust vehicle routing problem with discrete scenarios is defined on a complete directed graph G=(V,A). V includes one depot with m vehicles of capacity Q and n customers with demands d(i). The arc costs are defined by p scenarios, c(i,j,k) denoting the cost of arc (i,j) in scenario k. The goal is to determine a VRP solution minimizing the worst total cost over all scenarios. A mixed integer program and four metaheuristics using a common local search are presented for this extremely hard problem: one GRASP, one Iterated Local Search (ILS), one multi-start ILS (MS-ILS) and one MS-ILS involving giant tours and a new splitting procedure. 18 small instances (max n=10-20, m=2-3 and p=10-20) and 24 larger ones (max n=50-100, m=5-20 and p=10-20) are randomly generated. The two MS-ILS give the best results. On a 2.2 GHz Intel Core i7 PC, they retrieve in less than 5 seconds the optima found by CPLEX on small instances, and even improve three upper bounds when the solver cannot reach an optimum in 4 hours. On large instances, they last less than one minute and the giant tour version is significantly better than the one working only on complete RVRP solutions.