Authors
Elyn Solano Charris, Christian Prins, Andréa Cynthia Santos,
Title
Heuristic approaches for the robust vehicle routing problem
In
International Symposium on Combinatorial Optimization (ISCO 2014), Lecture Notes in Computer Science (LNCS)
Volume
8596
Pages
384–395
Publisher
Springer
Year
2014
Indexed by
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 serve in a Greedy Randomized Adaptive Search Procedure (GRASP). Computational results are presented for both the mathematical formulation and the proposed heuristics.
Affiliations
Offprint