Improvement heuristics for the Vehicle Routing Problem based on simulated annealing
European Journal of Operational ResearchPublished 1 November 1995
Alex Van Breedam
Citations169
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
The simulated annealing-based improvement methods are compared against their descent alternatives as well as other metaheuristics implementations on a set of classical test problems.
Abstract
This paper reports on the use of simulated annealing-based improvement methods for the Vehicle Routing Problem. The improvement methods considered are aimed at relocating and/or exchanging stops or strings of stops between different routes, starting from an initial feasible solution. The simulated annealing-based improvement methods are compared against their descent alternatives as well as other metaheuristics implementations on a set of classical test problems. The results are reported.
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
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.
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.
Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem
3,797 Citations1973Simon Lin, Brian W. Kernighan
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.
Journal of Optimization Theory and ApplicationsThermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
3,357 Citations1985V. Černý
It is conjecture that the analogy with thermodynamics can offer a new insight into optimization problems and can suggest efficient algorithms for solving them.
Bell System Technical JournalComputer Solutions of the Traveling Salesman Problem
1,960 Citations1965Shen Lin
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer and are based on a general heuristic approach believed to be of general applicability to various optimization problems.
Operations ResearchOptimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
1,468 Citations1989David S. Johnson, C. Aragon +2 more
This paper discusses annealing and its parameterized generic implementation, describes how this generic algorithm was adapted to the graph partitioning problem, and reports how well it compared to standard algorithms like the Kernighan-Lin algorithm.
Mathematics of Operations ResearchCooling Schedules for Optimal Annealing
1,232 Citations1988Bruce Hajek
A Monte Carlo optimization technique called “simulated annealing” is a descent algorithm modified by random ascent moves in order to escape local minima which are not global minima.
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 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.
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.
Operations ResearchOptimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
844 Citations1991David S. Johnson, C. Aragon +2 more
This is the second in a series of three papers that empirically examine the competitiveness of simulated annealing in certain well-studied domains of combinatorial optimization.
European Journal of Operational ResearchSimulated annealing: A tool for operational research
792 Citations1990Richard Eglese
The Simulated Annealing algorithm and the physical analogy on which it is based are described and suggestions are made for ways to improve the performance of the algorithm by modifying the ‘pure’ SA approach.
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.
European Journal of Operational ResearchAn improved annealing scheme for the QAP
406 Citations1990David T. Connolly
The result is a much-improved annealing scheme for this problem which performs well on a range of examples, finding improved solutions for several of the largest problems available in the literature and requiring only modest amounts of computational effort.
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 SocietyBases for Vehicle Fleet Scheduling
224 Citations1967T. J. Gaskell
The outcome is that no basis is superior to the others in all cases and that the suggestion of Clarke and Wright is a reasonable one to use.
American Journal of Mathematical and Management SciencesSimulated Annealing – An Annotated Bibliography
207 Citations1988Nick Collins, Richard Eglese +1 more
The results of an extensive literature survey of the Simulated Annealing algorithm for optimization problems are reported, with particular reference to the type of cooling schedule employed.
Naval Research Logistics QuarterlyUsing simulated annealing to solve routing and location problems
206 Citations1986Bruce Golden, Christopher C. Skiścim
This paper implements the analogy between the statistical mechanics of large multivariate physical systems and combinatorial optimization, applies it to the traveling salesman problem and the p‐median location problem, and test the approach extensively.
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.
Transportation Research Part B MethodologicalImplementing vehicle routing models
95 Citations1990Francesc Robust≐, Carlos F. Daganzo +1 more
This paper shows how idealized models can be used to obtain cost-effective, implementable solutions to large and complex logistics problems and advocates the use of fine tuning software to translate the guidelines produced by idealization into specific feasible solutions.
American Journal of Mathematical and Management SciencesSolution Improvement Heuristics for the Vehicle Routing and Scheduling Problem with Time Window Constraints
81 Citations1986Edward K. Baker, Joanne R. Schaffer
Two test data sets for the vehicle routing and scheduling problem with time window constraints are studied and initial solutions are obtained using a variety of heuristics, then improved using branch exchange procedures modified to incorporate the timewindow constraints.
Computers & Industrial EngineeringA 3-OPT based simulated annealing algorithm for vehicle routing problems
75 Citations1991Attahiru Sule Alfa, Sunderesh S. Heragu +1 more
Simulated Annealing is combined with the3-opt heuristic to solve the vehicle routing problem and preliminary results are encouraging; two examples out of three large size problems gave results as good as the best known 3-opt solution.
Management ScienceA Tabu Search Heuristic for the Vehicle Routing Problem
69 Citations1994Michel Gendreau, Alain Hertz +1 more
Numerical tests on a set of benchmark problems indicate that tabu search outperforms the best existing heuristics, and TABUROUTE often produces the bes known solutions.
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.
Statistica NeerlandicaA parallel insertion heuristic for vehicle routing with side constraints
9 Citations1990Martin Savelsbergh
This paper discusses some of the strong and weak points of this generalized assignment heuristic, and takes its basic ideas to develop a new parallel insertion heuristic for the vehicle routing and scheduling problem that is better able to handle various side constraints.