A Set-Partitioning-Based Heuristic for the Vehicle Routing Problem

• DOI: 10.1287/ijoc.11.2.161
• Publication Date: 2008-10-31T22:41:23Z
• Authors: James P. Kelly; Jiefeng Xu
• Keywords: 0211 other engineering and technologies; 02 engineering and technology

We develop a generic tabu search heuristic for solving the well-known vehicle routing problem. This algorithm explores the advantages of simple local search and improvement heuristics as well as a complex meta-heuristic. The solutions generated by these heuristics are selected and assembled by a set-partitioning model to produce superior solutions. Computational experience on standard benchmark problems is discussed and comparisons with other up-to-date heuristic methods are provided.