Using oriented random search to provide a set of alternative solutions to the capacitated vehicle routing problem

Área de Investigación: Articulos Año: 2009
Tipo de publicación: Parte de libro
Autores: Juan, Angel A.; Faulín, Javier; Ruiz, Rubén; Barrios, Barry; Gilibert, Miquel; Vilajosana, Xavier
Editor: Chinneck, John W.; Kristjansson, Bjarni; Saltzman, Matthew J. Volumen: 47
Capítulo: 17 Páginas: 331-346
Publisher: Springer
Part of the book "Operations Research and Cyber-Infrastructure"
In this paper we present SR-GCWS, a simulation-based algorithm for the Capacitated Vehicle Routing Problem (CVRP). Given a CVRP instance, the SR-GCWS algorithm incorporates a randomness criterion to the classical Clarke and Wright Savings (CWS) heuristic and starts an iterative process in order to ob- tain a set of alternative solutions, each of which outperforms the CWS algorithm. Thus, a random but oriented local search of the space of solutions is performed, and a list of “good alternative solutions” is obtained. We can then consider several properties per solution other than aprioristic costs, such as visual attractiveness, number of trucks employed, load balance among routes, environmental costs, etc. This allows the decision-maker to consider multiple solution characteristics other than just those defined by the aprioristic objective function. Therefore, our meth- odology provides more flexibility during the routing selection process, which may help to improve the quality of service offered to clients. Several tests have been performed to discuss the effectiveness of this approach
Versión digital