Metaheuristics for the robust vehicle routing problem with discrete scenarios - Archive ouverte HAL Access content directly
Conference Papers Year :

Metaheuristics for the robust vehicle routing problem with discrete scenarios

(1) , (1) , (1)
1

Abstract

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.
Not file

Dates and versions

hal-02292191 , version 1 (19-09-2019)

Identifiers

  • HAL Id : hal-02292191 , version 1

Cite

Elyn Solano-Charris, Christian Prins, Andréa Cynthia Santos. Metaheuristics for the robust vehicle routing problem with discrete scenarios. Working Group on Vehicle Routing and Logistics Optimization (VeRoLog 2014), Jun 2014, Oslo, Norway. ⟨hal-02292191⟩

Collections

CNRS UTT LOSI
167 View
0 Download

Share

Gmail Facebook Twitter LinkedIn More