Heuristic methods for vehicle routing problem with time windows
Artificial Intelligence in EngineeringPublished 1 July 2001Open access
Kay Chen Tan, L.H Lee, Qibo Zhu, Kepeng Ou
Citations297
SJR quartileQ4
SJR score0.11
SNIP0.06
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
Each of the heuristics developed to Solomon's 56 VRPTW 100-customer instances are applied, and yielded 18 solutions better than or equivalent to the best solution ever published for these problems.
Abstract
10.1016/S0954-1810(01)00005-X
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
The MIT Press eBooksAdaptation in Natural and Artificial Systems
35,568 Citations1992John H. Holland
Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.
Operations ResearchAlgorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
4,181 Citations1987Marius M. Solomon
This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints and finds that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.
Lecture notes in computer scienceUsing Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems
1,274 Citations1998Paul Shaw
This work uses a local search method that is analogous to the shuffling technique of job-shop scheduling, and so meshes well with constraint programming technology, to solve vehicle routing problems.
PolyPublie (École Polytechnique de Montréal)A Tabu Search Heuristic for the Vehicle Routing Problem
1,231 Citations1994Michel Gendreau, Alain Hertz +1 more
Operations ResearchA New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
1,180 Citations1992Martin Desrochers, Jacques Desrosiers +1 more
This paper presents a new optimization algorithm capable of optimally solving 100-customer problems of the vehicle routing problem with time windows VRPTW and indicates that this algorithm proved to be successful on a variety of practical sized benchmark VRPTw test problems.
Annals of Operations ResearchMetastrategy simulated annealing and tabu search algorithms for the vehicle routing problem
1,022 Citations1993Ibrahim H. Osman
Approximate methods based on descent, hybrid simulated annealing/tabu search, and tabu search algorithms are developed and different search strategies are investigated and an estimate for the tabu list size is statistically derived.
international conference on Genetic algorithmsA study of permutation crossover operators on the traveling salesman problem
892 Citations1987I. M. Oliver, David J. Smith +1 more
NetworksParallel iterative search methods for vehicle routing problems
593 Citations1993Éric D. Taillard
Two partition methods that speed up iterative search methods applied to vehicle routing problems including a large number of vehicles, based on the arborescence built from the shortest paths from any city to the depot are presented.
Operations ResearchVehicle Routing with Time Windows
298 Citations1987Antoon Kolen, A. H. G. Rinnooy Kan +1 more
A branch-and-bound method is described that minimizes the total route length in vehicle routing problems with time windows, and some computational results are presented.
Handbooks in operations research and management scienceChapter 1 Vehicle routing
257 Citations1995Marshall L. Fisher
INFORMS journal on computingThe Vehicle Routing Problem with Time Windows Part I: Tabu Search
219 Citations1996Jean‐Yves Potvin, Tanguy Kervahut +2 more
A tabu search heuristic for the vehicle routing problem with time windows is described, based on specialized local search heuristics that maintain the feasibility of the solution at all time.
Operations ResearchAn Optimization Algorithm for the Vehicle Routing Problem with Time Windows Based on Lagrangian Relaxation
215 Citations1997Niklas Kohl, Oli B.G. Madsen
The method is based on a Lagrangian relaxation of the constraint set requiring that each customer must be serviced and turns out to be very competitive compared to algorithms considered in the literature, and has succeeded in solving several previously unsolved problems.
Vehicle Routing with Time Windows using Genetic Algorithms
182 Citations1995Sam R. Thangiah
GIDEON, a genetic algorithm heuristic for solving vehicle routing problems with time windows, consists of a global customer clustering method and a local post-optimization method that obtained 41 new best known solutions.
A Hybrid Genetic Algorithm, Simulated Annealing and Tabu Search Heuristic for Vehicle Routing Problems with Time Windows
104 Citations2019Sam R. Thangiah
American Journal of Mathematical and Management SciencesAlgorithms for the Vehicle Routing Problems with Time Deadlines
78 Citations1993Sam R. Thangiah, Ibrahim H. Osman +2 more
Three heuristics to solve the VRPTD: deadline sweep, push-forward insertion and genetic sectoring are developed and improved using a local post-optimization procedure.
Artificial Neural Nets and Genetic AlgorithmsHybrid Genetic Algorithms for the Traveling Salesman Problem
19 Citations1993P. Prinetto, Maurizio Rebaudengo +1 more
A new operator is proposed, whose goal is to include in the genetic mechanism some heuristic knowledge drawn from the already proposed local-optimization techniques, to exploit the benefits of the different operators.