A Tabu Search Heuristic for the Vehicle Routing Problem
PolyPublie (École Polytechnique de Montréal)Published 1 October 1994
Michel Gendreau, Alain Hertz, Gilbert Laporte
Citations1,231
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
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 out performs the best existing heuristics, and TABUROUTE often produces the best known solutions.
Keywords
Engineering
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
The Journal of Chemical PhysicsEquation of State Calculations by Fast Computing Machines
37,074 Citations1953N. Metropolis, Arianna W. Rosenbluth +3 more
Tabu Search
5,702 Citations1997Fred Glover, Manuel Laguna
Operations ResearchScheduling of Vehicles from a Central Depot to a Number of Delivery Points
3,846 Citations1964Graham Clarke, J. W. Wright
An iterative procedure is developed that enables the rapid selection of an optimum or near-optimum route and has been programmed for a digital computer but is also suitable for hand computation.
European Journal of Operational ResearchThe vehicle routing problem: An overview of exact and approximate algorithms
1,701 Citations1992Gilbert Laporte
In this paper, some of the main known results relative to the Vehicle Routing Problem are surveyed.
Operations ResearchA Heuristic Algorithm for the Vehicle-Dispatch Problem
1,157 Citations1974Billy E. Gillett, Leland R. Miller
The sweep algorithm generally produces results that are significantly better than those produced by Gaskell's savings approach and are generally slightly better than Christofides and Eilon's results; however, the sweep algorithm is not as computationally efficient as Gaskell’s and is slightly less so than Christ ofides andEilon's.
NetworksA generalized assignment heuristic for vehicle routing
1,060 Citations1981Marshall L. Fisher, Ramchandran Jaikumar
This paper presents a heuristic for this problem in which an assignment of customers to vehicles is obtained by solving a generalized assignment problem with an objective function that approximates delivery cost and shows that it has outperformed the best existing heuristics on a sample of standard test problems.
Annals of Operations ResearchA user's guide to tabu search
910 Citations1993Fred Glover, Éric D. Taillard +1 more
This presentation demonstrates that a well-tuned implementation of tabu search makes it possible to obtain solutions of high quality for difficult problems, yielding outcomes in some settings that have not been matched by other known techniques.
Mathematics of Operations ResearchBounds and Heuristics for Capacitated Routing Problems
375 Citations1985M. Haimovich, A. H. G. Rinnooy Kan
Asymptotically optimal bounds and heuristics are developed for a capacitated routing problem that will find a solution with relative error at most (epsilon) in time polynomial in the number of customers.
Annals of Operations ResearchSolving real-life vehicle routing problems efficiently using tabu search
229 Citations1993Frédéric Semet, Éric D. Taillard
This paper presents a tabu search based method for finding good solutions to a real-life vehicle routing problem that takes the heterogeneous character of the fleet into account and obtains solutions that are significantly better than those previously developed and implemented in practice.
Journal of the Operational Research SocietyA Sequential Route-building Algorithm Employing a Generalised Savings Criterion
165 Citations1976RH Mole, Simon Jameson
A new method for vehicle scheduling, based upon sequential generation of vehicle routes, is described in this paper, and the possibility of several journeys being made by each vehicle is actively considered, and vehicle utilisation is high in consequence.
Operations ResearchParallel Savings Based Heuristics for the Delivery Problem
132 Citations1991Kemal Altınkemer, Bezalel Gavish
The paper presents parallel savings algorithms PSAs for generating feasible solutions to the delivery problem, and the average quality of solutions generated by PSAs is shown to be significantly superior on large sets of test problems.
Discrete Applied MathematicsFinding a feasible course schedule using Tabu search
117 Citations1992Alain Hertz
A new method based on Tabu search techniques for finding a feasible course schedule based on daily quantums is described, which takes precedence and time windows requirements into account.
Mathematical ProgrammingPolyhedral study of the capacitated vehicle routing problem
105 Citations1993Gérard Cornuéjols, F. Harche
The capacitated vehicle routing problem (CVRP) considered in this paper occurs when goods must be delivered from a central depot to clients with known demands, usingk vehicles of fixed capacity, and a cutting plane algorithm that only uses inequalities from the above classes is reported on.
Journal of the Operational Research SocietyA Dual Heuristic for Vehicle Scheduling
20 Citations1982I. M. Cheshire, A. M. Malleson +1 more
A heuristic method is used to solve the vehicle scheduling problem by maintaining local optimality whilst approaching the feasible region and giving results comparable with the best published algorithms.
CENTRE DE RECHERCHE SUR LES TRANSPORTS PUBLICATIONVEHICLE ROUTING PROBLEMS VIA TABU SEARCH METAHEURISTIC
19 Citations1991Vitória Pureza, Paulo Morelato França
A simple adaptation of Tabu Search which uses only a short term memory strategy to overcome local optimality is developed and is tested on a large set of randomly generated routing problems and on a set of classical test problems.
Journal of the Operational Research SocietyThe Curse of Unintended Rounding Error: A Case from the Vehicle Scheduling Literature
6 Citations1983RH Mole
A careful examination of the relevant source materials shows that one subset of authors, which includes the authors mentioned here, forced possibly premature rounding upon intermediate results in their calculations.