A TABU SEARCH HEURISTIC FOR THE VEHICLE-ROUTING PROBLEM

• 成果类型: Article
• 署名作者: GENDREAU, M; HERTZ, A; LAPORTE, G
• 署名单位: Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.40.10.1276
• 发表日期: 1994
• 页码: 1276-1290
• 关键词: vehicle routing problem; tabu search; GENERALIZED INSERTION

摘要

The purpose of this paper is to describe TABUROUTE, a new tabu search heuristic for the vehicle routing problem with capacity and route length restrictions. The algorithm considers a sequence of adjacent solutions obtained by repeatedly removing a vertex from its current route and reinserting it into another route. This is done by means of a generalized insertion procedure previously developed by the authors. During the course of the algorithm, infeasible solutions are allowed. Numerical tests on a set of benchmark problems indicate that tabu search outperforms the best existing heuristics, and TABUROUTE often produces the best known solutions.