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

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