On the use of Monte Carlo simulation, cache and splitting techniques to improve the Clarke and Wright savings heuristics

Abstract

This paper presents the SR-GCWS-CS probabilistic algorithm that combines Monte Carlo simulation with splitting techniques and the Clarke and Wright savings heuristic to find competitive quasi-optimal solutions to the Capacitated Vehicle Routing Problem (CVRP) in reasonable response times. The algorithm, which does not require complex fine-tuning processes, can be used as an alternative to other metaheuristics—such as Simulated Annealing, Tabu Search, Genetic Algorithms, Ant Colony Optimization or GRASP, which might be more difficult to implement and which might require non-trivial fine-tuning processes—when solving CVRP instances. As discussed in the paper, the probabilistic approach presented here aims to provide a relatively simple and yet flexible algorithm which benefits from: (a) the use of the geometric distribution to guide the random search process, and (b) efficient cache and splitting techniques that contribute to significantly reduce computational times. The algorithm is validated through a set of CVRP standard benchmarks and competitive results are obtained in all tested cases. Future work regarding the use of parallel programming to efficiently solve large-scale CVRP instances is discussed. Finally, it is important to notice that some of the principles of the approach presented here might serve as a base to develop similar algorithms for other routing and scheduling combinatorial problems.

Keywords:

• simulation
• heuristics
• probabilistic algorithms
• vehicle routing
• road transport

Acknowledgements

This work has been partially supported by the IN3-UOC Knowledge Community Program under grant HAROSA KC (http://dpcs.uoc.edu) and by the project TRA2006-10639 from the Spanish Ministry of Science and Technology. The authors would also like to thank NVIDIA Inc. by their kindly support to our research.

Notes

1 SR-GCWS-CS stands for SimORouting's Generalized CWS with Cache and Splitting.