Metaheuristics for the robust vehicle routing problem with discrete scenarios

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.
Document type :
Conference papers
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02292191
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, September 19, 2019 - 2:57:30 PM
Last modification on : Friday, September 20, 2019 - 1:25:19 AM

Identifiers

  • HAL Id : hal-02292191, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

8