Heuristic Approaches for the Robust Vehicle Routing Problem

Abstract : In this article, the Robust Vehicle Routing Problem (RVRP) with uncertain traveling costs is studied. It covers a number of important applications in urban transportation and large scale bio-terrorism emergency. The uncertain data are defined as a bounded set of discrete scenarios associated with each arc of the transportation network. The objective is to determine a set of vehicle routes minimizing the worst total cost over all scenarios. A mixed integer linear program is proposed to model the problem. Then, we adapt some classical VRP heuristics to the RVRP, such as Clarke and Wright, randomized Clarke and Wright, Sequential Best Insertion, Parallel Best Insertion and the Pilot versions of the Best Insertion heuristics. In addition, a local search is developed to improve the obtained solutions and be integrated in a Greedy Randomized Adaptive Search Procedure (GRASP). Computational results are presented for both the mathematical formulation and the proposed heuristics.
Document type :
Book sections
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02291669
Contributor : Jean-Baptiste Vu Van <>
Submitted on : Thursday, September 19, 2019 - 10:08:27 AM
Last modification on : Friday, September 20, 2019 - 1:25:19 AM

Identifiers

  • HAL Id : hal-02291669, version 1

Collections

Citation

Elyn Solano-Charris, Christian Prins, Andréa Cynthia Santos. Heuristic Approaches for the Robust Vehicle Routing Problem. ISCO 2014: Combinatorial Optimization, pp.384-395, 2014. ⟨hal-02291669⟩

Share

Metrics

Record views

7