A tabu search algorithm for the multi-trip vehicle routing and scheduling problem
European Journal of Operational ResearchPublished 1 July 1997
José Brandão, Alan Mercer
Citations213
SJR quartileQ1
SJR score2.24
SNIP2.62
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.
TL;DR
A novel tabu search heuristic for the multi-trip vehicle routing and scheduling problem (MTVRSP) was developed to tackle real distribution problems, taking into account most of the constraints that appear in practice.
Abstract
This paper describes a novel tabu search heuristic for the multi-trip vehicle routing and scheduling problem (MTVRSP). The method was developed to tackle real distribution problems, taking into account most of the constraints that appear in practice. In the MTVRSP, besides the constraints that are common to the basic vehicle routing problem, the following ones are present: during each day a vehicle can make more than one trip; the customers impose delivery time windows; the vehicles have different capacities considered in terms of both volume and weight; the access to some customers is restricted to some vehicles; the drivers' schedules must respect the maximum legal driving time per day and the legal time breaks; the unloading times are considered.
Keywords
Engineering
INFORMS Journal on ComputingTabu Search—Part II
5,643 Citations1990Fred Glover
The elements of staged search and structured move sets are characterized, which bear on the issue of finiteness, and new dynamic strategies for managing tabu lists are introduced, allowing fuller exploitation of underlying evaluation functions.
INFORMS Journal on ComputingTabu Search—Part I
4,974 Citations1989Fred Glover
The fundamental principles underlying tabu search as a strategy for combinatorial optimization problems are presented and more advanced considerations are examined, applying the basic ideas to special settings and outlining a dynamic move structure to insure finiteness.
Decision SciencesHEURISTICS FOR INTEGER PROGRAMMING USING SURROGATE CONSTRAINTS
1,352 Citations1977Fred Glover
NetworksComplexity of vehicle routing and scheduling problems
1,288 Citations1981Jan Karel Lenstra, A. H. G. Rinnooy Kan
The complexity of a class of vehicle routing and scheduling problems is investigated and known NP-hardness results are reviewed and compiled to compile the worst-case performance of approximation algorithms.
PolyPublie (École Polytechnique de Montréal)A Tabu Search Heuristic for the Vehicle Routing Problem
1,231 Citations1994Michel Gendreau, Alain Hertz +1 more
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.
Parallel ComputingRobust taboo search for the quadratic assignment problem
827 Citations1991Éric D. Taillard
An adaptation of taboo search to the quadratic assignment problem is discussed in this paper, which is efficient and robust, requiring less complexity and fewer parameters than earlier adaptations.
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 SocietyVehicle Routeing with Multiple Use of Vehicles
222 Citations1996Éric D. Taillard, Gilbert Laporte +1 more
A tabu search heuristic is developed for the vehicle routeing problem with multiple use of vehicles and is shown to produce high quality solutions on a series of test problems.
Operations ResearchA Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows
219 Citations1998Michel Gendreau, Alain Hertz +2 more
Tests performed on 375 instances indicate that the proposed heuristic compares very well with alternative methods and very often produces optimal or near-optimal solutions.
Journal of the Operational Research SocietyA Tabu Search Approach for Delivering Pet Food and Flour in Switzerland
92 Citations1994Y. Rochat, Frédéric Semet
This paper proposes two heuristic methods: a fast straightforward insertion procedure and a method based on tabu search techniques that can reduce the total distance travelled when used in a real-life vehicle routeing problem in a major Swiss company producing pet food and flour.
Operations ResearchNew Insertion and Postoptimization Procedures for the Traveling Salesman Problem
65 Citations1992Michel Gendreau, Alain Hertz +1 more
A new insertion procedure and a new post- optimization routine for the traveling salesman problem results in an efficient algorithm (GENIUS) which outperforms known alternative heuristics in terms of solution quality and computing time.
Annals of Operations ResearchA tabu search experience in production scheduling
50 Citations1993J. Wesley Barnes, Manuel Laguna
A synthesis of the various tabu search mechanisms that have been employed, giving special attention to advances that have led to major improvements and suggesting directions for future research.
Annals of Operations ResearchLarge-scale controlled rounding using tabu search with strategic oscillation
45 Citations1993James P. Kelly, Bruce Golden +1 more
A heuristic based on tabu search with strategic oscillation with lower-bounding technique is described for solving this NP-hard problem of rounding tabular data subject to additivity constraints while minimizing the overall perturbation of the data.
Annals of Operations ResearchTabu search for a class of scheduling problems
37 Citations1993Edward L. Mooney, Ronald L. Rardin
Extensions and enhancements of tabu search for the special case of the resource scheduling problem described above are described and compared with other variations using consistent measures of solution time and quality developed for this study.
INFORMS Journal on Applied AnalyticsInteractive Optimization of Bulk Sugar Deliveries
21 Citations1992André van Vliet, C. G. E. Boender +1 more
Journal of the Operational Research SocietyIntegration of AI and OR Techniques for Computer-Aided Algorithmic Design in the Vehicle Routing Domain
14 Citations1990Jean‐Yves Potvin, Guy Lapalme +1 more
This paper shows how tools and techniques of artificial intelligence can be successfully integrated into a computer system working in the vehicle routing domain and describes the general algorithmic framework and the rich interface provided by the system to the expert algorithm designer.