SR-2: A Hybrid Algorithm for the Capacitated Vehicle Routing Problem

Angel A. Juan
Javier Faulin
Josep Jorba
Barry Barrios
Scott Erwin Grasman, Missouri University of Science and Technology

This document has been relocated to

There were 29 downloads as of 27 Jun 2016.


During the last decades a lot of work has been devoted to develop algorithms that can provide near-optimal solutions for the capacitated vehicle routing problem (CVRP). Most of these algorithms are designed to minimize an objective function, subject to a set of constraints, which typically represents aprioristic costs. This approach provides adequate theoretical solutions, but they do not always fit real-life needs since there are some important costs and some routing constraints or desirable properties that cannot be easily modeled. In this paper, we present a new approach which combines the use of Monte Carlo simulation and parallel and grid computing techniques to provide a set of alternative solutions to the CVRP. This allows the decision-maker to consider multiple solution characteristics other than just aprioristic costs. Therefore, our methodology offers more flexibility during the routing selection process, which may help to improve the quality of service offered to clients.