TABU SEARCH HEURISTIC FOR THE VEHICLE ROUTING PROBLEM WITH TWO DIMENSIONAL LOADING CONSTRAINTS

This paper addresses the capacitated vehicle routing problem (CFRP) in the special case where the demand of a customer consists of a certain number of two-dimensional weighted items. The problem calls for the minimization of the cost of transportation needed for the delivery of goods demanded by the customers, and carried out by a fleet of vehicles based at a central depot. In order to accommodate all items on the vehicles, a feasibility check of the two-dimensional packing must be executed on each vehicle. The overall problem, designated as 2L-CVRP, is particularly difficult to solve in practice. This paper proposes a tabu search heuristic in which the 2L-CVRP is solved through heuristics, lower bounds, and a truncated branch-and-bound procedure. The effectiveness of the solution algorithm is demonstrated through extensive computational experiments.

• Corporate Authors:

  Universite de Montreal

  Centre de Recherche sur Les Transports
  C.P. 6128 Succursale Centre-ville
  Montreal H3C 3J7, Quebec  Canada 
• Authors:
  • Gendreau, M
• Publication Date: 2004

Language

• English

Media Info

• Pagination: 26 p.

Subject/Index Terms

• TRT Terms: Capacitance; Costs; Heuristic methods; Load factor; Routing; Tabu search
• Subject Areas: Finance; Highways; Operations and Traffic Management; Society;

Filing Info

• Accession Number: 00986708
• Record Type: Publication
• Files: TRIS
• Created Date: Feb 3 2005 12:00AM