Metaheuristics for the robust vehicle routing problem with discrete scenarios
Working Group on Vehicle Routing and Logistics Optimization (VeRoLog), Oslo, Norway
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.