THE VEHICLE ROUTING PROBLEM: AN OVERVIEW OF EXACT AND APPROXIAMTE ALGORITHMS

The Vehicle Routing Problem (VRP) can be described as the problem of designing optimal delivery or collection routes from one or several depts to a number of geographically scattered cities or customers, subject to side constraints. the VRP plays a central role in the fields of physical distribution and logistics. There exists a wide variety of VRPs and a broad literature on this class of problems (see, for example, the surveys of Bodin et al. (1983), christofides (1985a), Laporte and Norbert (1987), Laporte (1990), aw well as the recent classification scheme proposed by Desrochers, Lenstra and Savelsbergh (1990)). The purpose of this paper is to survey the main and approximate algorithms developed for the VRP, at a level appropriate for a first graduate course in combinatorial optimization. The paper is organized as follows: 1) definition; 2) exact algorithsm; 3) heuristic algorithms; 4) conclusions. (A)

  • Corporate Authors:

    CENTRE DE RECHERCHE SUR LES TRANSPORTS. UNIVERSITE DE MONTREAL

    C.P. 6128, SUCCURSALE A
    MONTREAL, QUEBEC  Canada  H3C 3J7
  • Authors:
    • Laporte, G
  • Publication Date: 1991-2

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 00674377
  • Record Type: Publication
  • Source Agency: Transportation Association of Canada (TAC)
  • Files: ITRD
  • Created Date: Mar 8 1995 12:00AM