A powerful route minimization heuristic for the vehicle routing problem with time windows
Operations Research LettersPublished 25 May 2009
Yuichi Nagata, Olli Bräysy
Citations98
SJR quartileQ2
SJR score0.44
SNIP0.68
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
An efficient route minimization heuristic is suggested for the vehicle routing problem with time windows based on the ejection pool, powerful insertion and guided local search strategies.
Abstract
We suggest an efficient route minimization heuristic for the vehicle routing problem with time windows. The heuristic is based on the ejection pool, powerful insertion and guided local search strategies. Experimental results on the Gehring and Homberger's benchmarks demonstrate that our algorithm outperforms previous approaches and found 18 new best-known solutions.
Keywords
Computer ScienceEngineering
International series in management science/operations research/International series in operations research & management scienceHandbook of Metaheuristics
3,396 Citations2003Fred Glover, Gary Kochenberger
This book discusses Metaheuristic Class Libraries, Hyper-Heuristics, and Parallel Strategies for Meta-Heuristics as well as other topics related to Meta-Heuristics, which have had an important role in the development of search technology.
Princeton University Press eBooksLocal Search in Combinatorial Optimization
2,059 Citations2003Emile Aarts, Jan Karel Lenstra
Computers & Operations ResearchA general heuristic for vehicle routing problems
1,394 Citations2005David Pisinger, Stefan Røpke
A unified heuristic which is able to solve five different variants of the vehicle routing problem and shown promising results for a large class of vehicle routing problems with backhauls as demonstrated in Ropke and Pisinger.
Transportation ScienceVehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms
1,112 Citations2005Olli Bräysy, Michel Gendreau
How heuristic methods should be evaluated and proposed using the concept of Pareto optimality in the comparison of different heuristic approaches are discussed.
Transportation ScienceVehicle Routing Problem with Time Windows, Part II: Metaheuristics
826 Citations2005Olli Bräysy, Michel Gendreau
This paper surveys the research on the metaheuristics for the Vehicle Routing Problem with Time Windows and describes basic features of each method, and experimental results for Solomon's benchmark test problems are presented and analyzed.
Transportation ScienceA Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows
356 Citations2004Russell Bent, Pascal Van Hentenryck
A two-stage hybrid algorithm that minimizes the number of vehicles, using simulated annealing, and minimizes travel cost by using a large neighborhood search that may relocate a large number of customers is proposed.
Journal of the Operational Research SocietyAn Exchange Heuristic for Routeing Problems with Time Windows
344 Citations1995Jean‐Yves Potvin, Jean‐Marc Rousseau
This paper compares different exchange heuristics for vehicle routeing problems with time windows, and introduces a new 2-opt* exchange heuristic, and shows that a hybrid approach, based on Or-opt and 2- opt* exchanges, is particularly powerful for problems withTime windows.
International series in management science/operations research/International series in operations research & management scienceGuided Local Search
212 Citations2010Christos Voudouris, Edward Tsang +1 more
This chapter describes the principles of Guided Local Search (GLS) and Fast Local Search and surveys their applications and provides guidance for implementing and using GLS and FLS.
American Journal of Medical GeneticsA Parallel Hybrid Evolutionary Metaheuristic for the Vehicle Routing Problem with Time Windows
176 Citations1999Hermann Gehring
A two-phase procedural approach for solving the vehicle routing problem with time windows is parallelized and the aim of the first phase is the minimization of the number of vehicles by means of a (1, λ)-evolution strategy, whereas in the second phase the total distance is minimized using a tabu search algorithm.
Journal of HeuristicsParallelization of a Two-Phase Metaheuristic for Routing Problems with Time Windows
126 Citations2002Hermann Gehring, Jörg Homberger
The parallelized two-phase metaheuristic for the vehicle routing problem with time windows and a central depot was subjected to a comparative test and the derived results seem to justify the proposed parallelization concept.
NetworksA branch‐and‐price‐based large neighborhood search algorithm for the vehicle routing problem with time windows
102 Citations2009Eric Prescott‐Gagnon, Guy Desaulniers +1 more
A large neighborhood search algorithm that takes advantage of the power of branch‐and‐price which is the leading methodology for the exact solution of the VRPTW.
Discrete Applied MathematicsAn iterated local search algorithm for the vehicle routing problem with convex time penalty functions
95 Citations2007Toshihide Ibaraki, Shinji Imahori +4 more
INFORMS journal on computingA Two-Stage Heuristic with Ejection Pools and Generalized Ejection Chains for the Vehicle Routing Problem with Time Windows
91 Citations2007Andrew Lim, Xingwen Zhang
The experimental results showed that the VRPTW algorithm extended to solve m-VRPTW is effective and efficient in reducing the number of vehicles and is also very competitive in terms of distance minimization.
Wiley Encyclopedia of Operations Research and Management ScienceGuided Local Search
84 Citations2024Christos Voudouris, Edward Tsang +1 more
Efficient evolutionary algorithm for the vehicle routing problem with time windows: edge assembly crossover for the VRPTW
14 Citations2007Yuichi Nagata
An evolutionary algorithm (EA) for the vehicle routing problem with time windows (VRPTW) is proposed and a crossover operator suitable for solving the VRPTW is presented.