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.

  • Corporate Authors:

    University of Montreal

    Center for Research on Transportation (CRT)/CIRRELT
    P.O. Box 6128, Station Centre-ville
    Montreal, Quebec  Canada  H3C 3J7
  • Authors:
    • Rochat, Y
  • Publication Date: 1995

Language

  • English

Media Info

  • Pagination: 31 p.

Subject/Index Terms

Filing Info

  • Accession Number: 00719125
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Mar 16 1996 12:00AM