Heuristic Approaches for the Robust Vehicle Routing Problem - Université de technologie de Troyes Access content directly
Book Sections Year : 2014

Heuristic Approaches for the Robust Vehicle Routing Problem


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

Dates and versions

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


  • HAL Id : hal-02291669 , version 1


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, Lecture Notes in Computer Science. ⟨hal-02291669⟩


18 View
0 Download


Gmail Facebook Twitter LinkedIn More