PROBABILISTIC DIVERSIFICATION AND INTENSIFICATION IN LOCAL SEARCH FOR VEHICULE ROUTING
Local search methods used to find good solutions to combinatorial optimization problems have two main weaknesses: an occasional propensity to become trapped in a very poor local optimum and large computational effort. This paper describes a technique that overcomes both weaknesses by exploring solutions that are very different from each other in order to diversify the search, intensifying the search to identify better local optima in a promising region of the set of feasible solutions, and parallelizing the process. The performance of the technique is illustrated for two taboo searches developed for vehicle routing problems. The paper also presents a post-optimization technique that may often improve the solutions obtained. The performance of the new technique is compared to that of the original local searches.
University of MontrealCenter for Research on Transportation (CRT)/CIRRELT
P.O. Box 6128, Station Centre-ville
Montreal, Quebec Canada H3C 3J7
- Rochat, Y
- Publication Date: 1995
- Pagination: 31 p.
- TRT Terms: Optimization; Probability; Routing
- Uncontrolled Terms: Probabilistic analysis
- Old TRIS Terms: Searching
- Subject Areas: Data and Information Technology; Highways; Operations and Traffic Management;
- Accession Number: 00719125
- Record Type: Publication
- Files: TRIS
- Created Date: Mar 16 1996 12:00AM