Probabilistic Diversification and Intensification in Local Search for Vehicle Routing. Publication CRT-95–13, Centre de recherche sur les transports

This paper presents a probabilistic technique to diversify, intensify and parallelize a local search adapted for solving vehicle routing problems. This technique may be applied to a very wide variety of vehicle routing problems and local searches. It is shown that efficient first level taboo searches for vehicle routing problems may be significantly improved with this technique. Moreover, the solutions produced by this technique may often be improved by a post-optimization technique presented in this paper too. The solutions of nearly 40 problem instances of the literature have been improved