The Vehicle Routing Problem with Time Windows Part I: Tabu Search

Jean-Yves Potvin
Jean-Yves Potvin
Centre de recherche sur les transports, Université de Montréal, Montréal (Québec), Canada H3C 3J7, and Département d'informatique et de recherche opérationnelle, Université de Montréal, Montréal (Québec), Canada H3C 3J7
Search for more papers by this author
,
Tanguy Kervahut
Tanguy Kervahut
Giro Inc., Montréal (Québec), Canada, H3L 3T1
Search for more papers by this author
,
Bruno-Laurent Garcia
Bruno-Laurent Garcia
Centre Universitaire des Sciences et Techniques, Université Blaise Pascal, 63174 Aubière Cedex, France
Search for more papers by this author
,
Jean-Marc Rousseau
Jean-Marc Rousseau
Département d'informatique et de recherche opérationnelle, Université de Montréal, Montréal (Québec), Canada H3C 3J7, and Giro Inc., Montréal (Québec), Canada, H3L 3T1
Search for more papers by this author

Centre de recherche sur les transports, Université de Montréal, Montréal (Québec), Canada H3C 3J7, and Département d'informatique et de recherche opérationnelle, Université de Montréal, Montréal (Québec), Canada H3C 3J7

Search for more papers by this author

Tanguy Kervahut

Giro Inc., Montréal (Québec), Canada, H3L 3T1

Search for more papers by this author

Bruno-Laurent Garcia

Centre Universitaire des Sciences et Techniques, Université Blaise Pascal, 63174 Aubière Cedex, France

Search for more papers by this author

Jean-Marc Rousseau

Département d'informatique et de recherche opérationnelle, Université de Montréal, Montréal (Québec), Canada H3C 3J7, and Giro Inc., Montréal (Québec), Canada, H3L 3T1

Search for more papers by this author

Published Online:1 May 1996https://doi.org/10.1287/ijoc.8.2.158

Abstract

This paper describes a tabu search heuristic for the vehicle routing problem with time windows. The tabu search is based on specialized local search heuristics that maintain the feasibility of the solution at all time. Computational results on a standard set of test problems are reported, as well as comparisons with other heuristics.

Cited by
- A discrete Jaya algorithm for vehicle routing problems with uncertain demands
  8 May 2024 | Systems Science & Control Engineering, Vol. 12, No. 1
- A Confidence-based Bilevel Memetic Algorithm with Adaptive Selection Scheme for Capacitated Electric Vehicle Routing Problem
- Metaheuristic Tabu Search for Vehicle Scheduling: A Case Study of Healthcare Logistics
  19 September 2024
- Vehicle routing in the case of uncertain customer demands and soft time windows: A neuro-fuzzy logic approach
  Journal of Applied Engineering Science, Vol. 22, No. 2
- An Approximation Algorithm for k-Depot Split Delivery Vehicle Routing Problem
  Xiaofan Lai,
  Liang Xu,
  Zhou Xu,
  Yang Du
  25 May 2023 | INFORMS Journal on Computing, Vol. 35, No. 5
- Enhanced solution representations for vehicle routing problems with split deliveries
  8 August 2023 | Frontiers of Engineering Management, Vol. 10, No. 3
- Bi-objective multi-period vehicle routing for perishable goods delivery considering customer satisfaction
  Expert Systems with Applications, Vol. 220
- Combining Variable Neighborhood Search and Constraint Programming for Solving the Dial-A-Ride Problem
  6 October 2022
- Confidence-Based Ant Colony Optimization for Capacitated Electric Vehicle Routing Problem With Comparison of Different Encoding Schemes
  IEEE Transactions on Evolutionary Computation, Vol. 26, No. 6
- Using decomposition-based multi-objective algorithm to solve Selective Pickup and Delivery Problems with Time Windows
  Computers & Operations Research, Vol. 145
- Optimization of downstream fuel logistics based on road infrastructure conditions and exposure to accident events
  Transport Policy, Vol. 124
- A Novel Modified Ant Colony Optimization Algorithm by Resetting and Updating Pheromone for Vehicle Routing Problem with Time Windows
- A prescriptive analytics framework for efficient E-commerce order delivery
  Decision Support Systems, Vol. 147
- Policy adaptation for vehicle routing
  AI Communications, Vol. 34, No. 1
- VRP with Flexible Time Windows Using the ALNS Metaheuristic Algorithm
  31 October 2021
- Integrating vehicle routing into intermodal service network design with stochastic transit times
  EURO Journal on Transportation and Logistics, Vol. 10
- A modified ALNS algorithm for vehicle routing problems with time windows
  Journal of Physics: Conference Series, Vol. 1743, No. 1
- Multithreading Parallel Robust Approach for the VRPTW with Uncertain Service and Travel Times
  28 December 2020 | Symmetry, Vol. 13, No. 1
- An integrated route, temperature and humidity planning problem for the distribution of perishable products
  Computers & Industrial Engineering, Vol. 147
- A variable neighborhood search algorithm with reinforcement learning for a real-life periodic vehicle routing problem with time windows and open routes
  23 July 2020 | RAIRO - Operations Research, Vol. 54, No. 5
- Heuristics, metaheuristics, and hyperheuristics for rich vehicle routing problems
- Congestion and Pollution, Vehicle Routing Problem of a Logistics Provider in Thailand
  The Open Transportation Journal, Vol. 13, No. 1
- Decentralised multi-demic evolutionary approach to the dynamic multi-agent travelling salesman problem
  13 July 2019
- A hybrid memetic-ant colony optimization algorithm for the home health care problem with time window, synchronization and working time balancing
  Swarm and Evolutionary Computation, Vol. 46
- A memetic algorithm for multi-objective optimization of the home health care problem
  Swarm and Evolutionary Computation, Vol. 44
- Vehicle routing and appointment scheduling with team assignment for home services
  Computers & Operations Research, Vol. 100
- Epistemic Activities, Schooling and Parenting Styles: A Case Study in French Guiana Rural Contexts
  1 December 2018 | Contextes et didactiques, No. 12
- Just-In-Time Vehicle Routing for In-House Part Feeding to Assembly Lines
  Simon Emde,
  Michael Schneider
  2 April 2018 | Transportation Science, Vol. 52, No. 3
- A new bi-objective periodic vehicle routing problem with maximization market share in an uncertain competitive environment
  18 January 2017 | Computational and Applied Mathematics, Vol. 37, No. 2
- A memetic algorithm for a home health care routing and scheduling problem
  Operations Research for Health Care, Vol. 16
- The value of real-time traffic information in urban freight distribution
  19 May 2017 | Journal of Intelligent Transportation Systems, Vol. 22, No. 1
- Risk based, multi objective vehicle routing problem for hazardous materials: a test case in downstream fuel logistics
  Transportation Research Procedia, Vol. 30
- Designing granular solution methods for routing problems with time windows
  European Journal of Operational Research, Vol. 263, No. 2
- Improved artificial bee colony algorithm for vehicle routing problem with time windows
  29 September 2017 | PLOS ONE, Vol. 12, No. 9
- Hybrid Differential Evolution Optimization for the Vehicle Routing Problem with Time Windows and Driver-Specific Times
  6 April 2017 | Wireless Personal Communications, Vol. 95, No. 3
- A general model for the home health care routing and scheduling problem with route balancing
  IFAC-PapersOnLine, Vol. 50, No. 1
- An improved ant colony optimization for green multi-depot vehicle routing problem with time windows
- An Investigation on Compound Neighborhoods for VRPTW
  15 February 2017
- A Bi-criteria Ant Colony Optimization for Minimizing Fuel Consumption and Cost of The Traveling Salesman Problem With Time Windows
  Procedia Computer Science, Vol. 112
- A hybrid algorithm for the Truck-and-Trailer Routing Problem with time windows
- Heuristic solutions for the vehicle routing problem with time windows and synchronized visits
  26 March 2015 | Optimization Letters, Vol. 10, No. 3
- Efficient Path Rescheduling of Heterogeneous Mobile Data Collectors for Dynamic Events in Shanty Town Emergency Response
- A novel hybrid shuffled frog leaping algorithm for vehicle routing problem with time windows
  Information Sciences, Vol. 316
- Adaptive comprehensive learning bacterial foraging optimization and its application on vehicle routing problem with time windows
  Neurocomputing, Vol. 151
- A Survey of Hybrid Artificial Intelligence Algorithms for Dynamic Vehicle Routing Problem
  29 May 2015
- Towards Fast and Accurate Solutions to Vehicle Routing in a Large-Scale and Dynamic Environment
  13 August 2015
- Efficient Path Rescheduling of Heterogeneous Mobile Data Collectors for Dynamic Events in Shanty Town Emergency Response
- Transit Bus Scheduling with Limited Energy
  Jing-Quan Li
  25 June 2013 | Transportation Science, Vol. 48, No. 4
- A TDVRP Model for Financial Convoy Service in China
  2 July 2014
- A knowledge-based evolutionary algorithm for the multiobjective vehicle routing problem with time windows
  Computers & Operations Research, Vol. 45
- Memetic Algorithm with an Efficient Split Procedure for the Team Orienteering Problem with Time Windows
  25 October 2014
- A new mathematical model of vehicle routing problem based on milk-run
- Recent progress of local search in handling the time window constraints of the vehicle routing problem
  9 January 2013 | Annals of Operations Research, Vol. 204, No. 1
- A heuristic to solve the synchronized log-truck scheduling problem
  Computers & Operations Research, Vol. 40, No. 3
- Recurrent Neural Network and Genetic Algorithm Approaches for a Dual Route Optimization Problem: A Real Case Study
  26 September 2012
- A Simulated Annealing Algorithm for the Vehicle Routing Problem with Time Windows and Synchronization Constraints
  26 November 2013
- Neighborhood reduction strategy for tabu search implementation in asymmetric traveling salesman problem
  3 May 2012 | OPSEARCH, Vol. 49, No. 4
- A transgenic algorithm for the Vehicle Routing Problem with Time Windows
- A multiobjective evolutionary algorithm with enhanced reproduction operators for the vehicle routing problem with time windows
- On the tour planning problem
  12 June 2010 | Annals of Operations Research, Vol. 192, No. 1
- Tabu Search Implementation on Traveling Salesman Problem and Its Variations: A Literature Survey
  American Journal of Operations Research, Vol. 02, No. 02
- A Survey on the Vehicle Routing Problem and Its Variants
  Intelligent Information Management, Vol. 04, No. 03
- Assessing the value of information for retail distribution of perishable goods
  19 May 2011 | European Transport Research Review, Vol. 3, No. 2
- A hybrid algorithm for vehicle routing problem with time windows
  Expert Systems with Applications, Vol. 38, No. 1
- Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems
  İbrahim Muter,
  Ş. İlker Birbil,
  Güvenç Şahin,
  23 March 2010 | INFORMS Journal on Computing, Vol. 22, No. 4
- Recent progress of local search in handling the time window constraints of the vehicle routing problem
  10 September 2010 | 4OR, Vol. 8, No. 3
- Fast Approximation Heuristics for Multi-Objective Vehicle Routing Problems
- Optimization model and algorithm for goods delivery under E-commerce
- An effective genetic algorithm for the fleet size and mix vehicle routing problems
  Transportation Research Part E: Logistics and Transportation Review, Vol. 45, No. 3
- Particle Evolutionary Swarm Multi-Objective Optimization for Vehicle Routing Problem with Time Windows
- The design of vehicle routes for a third-party logistics service provider using the simulated annealing algorithm
  International Journal of Business Performance Management, Vol. 11, No. 1/2
- An iterated local search algorithm for the vehicle routing problem with convex time penalty functions
  Discrete Applied Mathematics, Vol. 156, No. 11
- Computational intelligence approach to real-world cooperative vehicle dispatching problem
  1 January 2008 | International Journal of Intelligent Systems, Vol. 23, No. 5
- An iterated local search algorithm for the time-dependent vehicle routing problem with time windows
  Discrete Optimization, Vol. 5, No. 2
- A heuristic for the vehicle routing problem with due times
  Computers & Industrial Engineering, Vol. 54, No. 3
- A New Approach using Machine Learning and Data Fusion Techniques for Solving Hard Combinatorial Optimization Problems
- A Path Relinking Approach with an Adaptive Mechanism to Control Parameters for the Vehicle Routing Problem with Time Windows
- Market Based Allocation of Transportation Orders to Vehicles in Adaptive Multi-objective Vehicle Routing
- Combination of Multiple Ant Colony System and Simulated Annealing for the Multidepot Vehicle-Routing Problem with Time Windows
  1 January 2008 | Transportation Research Record: Journal of the Transportation Research Board, Vol. 2089, No. 1
- PSO-based algorithm for home care worker scheduling in the UK
  Computers & Industrial Engineering, Vol. 53, No. 4
- Interactive Utility Maximization in Multi-Objective Vehicle Routing Problems: A "Decision Maker in the Loop"-Approach
- On the Interactive Resolution of Multi-objective Vehicle Routing Problems
- Annotated bibliography in vehicle routing
  Operational Research, Vol. 7, No. 1
- Chapter 6 Vehicle Routing
- The vehicle routing problem with flexible time windows and traveling times
  Discrete Applied Mathematics, Vol. 154, No. 16
- Vehicle Routing Problems with Time Windows Using Simulated Annealing
- Travel Time Reliability in Vehicle Routing and Scheduling with Time Windows
  25 August 2006 | Networks and Spatial Economics, Vol. 6, No. 3-4
- A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems
  European Journal of Operational Research, Vol. 172, No. 3
- Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries
  Transportation Research Part C: Emerging Technologies, Vol. 14, No. 3
- A Hybrid Multiobjective Evolutionary Algorithm for Solving Vehicle Routing Problem with Time Windows
  18 October 2005 | Computational Optimization and Applications, Vol. 34, No. 1
- Scatter search for the vehicle routing problem with time windows
  European Journal of Operational Research, Vol. 169, No. 2
- An Experimental Study on the Performance of Probabilistic Vehicle Routing and Scheduling with ITS
- Notice of Violation of IEEE Publication Principles - Dynamic vehicle routing and scheduling with variable travel times in intelligent transportation system
- Effective Local Search Algorithms for Routing and Scheduling Problems with General Time-Window Constraints
  T. Ibaraki,
  S. Imahori,
  M. Kubo,
  T. Masuda,
  T. Uno,
  M. Yagiura,
  1 May 2005 | Transportation Science, Vol. 39, No. 2
- A two-phase hybrid metaheuristic for the vehicle routing problem with time windows
  European Journal of Operational Research, Vol. 162, No. 1
- A vehicle routing problem with backhauls and time windows: a guided local search solution
  Transportation Research Part E: Logistics and Transportation Review, Vol. 41, No. 2
- Dynamic vehicle routing for online B2C delivery
  Omega, Vol. 33, No. 1
- A Tabu Search Heuristic for a Full-Load, Multi-Terminal, Vehicle Scheduling Problem with Backhauling and Time Windows
  Journal of Mathematical Modelling and Algorithms, Vol. 3, No. 3
- Intelligent transportation system based dynamic vehicle routing and scheduling with variable travel times
  Transportation Research Part C: Emerging Technologies, Vol. 12, No. 3-4
- COMPARISON OF SYSTEMS BASED ON EVOLUTIONARY SEARCH AND SIMULATED ANNEALING TO SOLVE THE VRPTW PROBLEM
  20 November 2011 | International Journal of Computational Intelligence and Applications, Vol. 04, No. 01
- Towards a decision support system for the ready concrete distribution system: A case of a Greek company
  European Journal of Operational Research, Vol. 152, No. 2
- Computational intelligence approach to real-world cooperative vehicle dispatching problem
- Local search with annealing-like restarts to solve the VRPTW
  European Journal of Operational Research, Vol. 150, No. 1
- Exact and heuristic methods for a full-load, multi-terminal, vehicle scheduling problem with backhauling and time windows
  21 December 2017 | Journal of the Operational Research Society, Vol. 54, No. 4
- Vehicle capacity planning system: A case study on vehicle routing problem with time windows
  IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, Vol. 33, No. 2
- Modelling Dynamic Vehicle Routing and Scheduling with Real Time Information on Travel Times
  8 February 2016
- Parallelization of a Two-Phase Metaheuristic for Routing Problems with Time Windows
  Journal of Heuristics, Vol. 8, No. 3
- Local search with annealing-like restarts to solve the vehicle routing problem with time windows
  11 March 2002
- Modeling City Logistics
  1 January 2002 | Transportation Research Record: Journal of the Transportation Research Board, Vol. 1790, No. 1
- Artificial intelligence heuristics in solving vehicle routing problems with time window constraints
  Engineering Applications of Artificial Intelligence, Vol. 14, No. 6
- Adaptive memory programming: A unified view of metaheuristics
  European Journal of Operational Research, Vol. 135, No. 1
- Heuristic methods for vehicle routing problem with time windows
  Artificial Intelligence in Engineering, Vol. 15, No. 3
- PROBABILISTIC ROUTING AND SCHEDULING OF URBAN PICKUP/DELIVERY TRUCKS WITH VARIABLE TRAVEL TIMES
  Doboku Gakkai Ronbunshu, Vol. 2001, No. 674
- Comparing descent heuristics and metaheuristics for the vehicle routing problem
  Computers & Operations Research, Vol. 28, No. 4
- A Heuristic for the Vehicle Routing Problem with Time Windows
  Journal of Heuristics, Vol. 7, No. 2
- A messy genetic algorithm for the vehicle routing problem with time window constraints
- Classical and modern heuristics for the vehicle routing problem
  24 August 2006 | International Transactions in Operational Research, Vol. 7, No. 4-5
- Probabilistic Vehicle Routing and Scheduling with Variable Travel Times
  IFAC Proceedings Volumes, Vol. 33, No. 9
- A PATH-EXCHANGE-TYPE LOCAL SEARCH ALGORITHM FOR VEHICLE ROUTING AND ITS EFFICIENT SEARCH STRATEGY
  Journal of the Operations Research Society of Japan, Vol. 43, No. 1
- A route-neighborhood-based metaheuristic for vehicle routing problem with time windows
  European Journal of Operational Research, Vol. 118, No. 3
- A heuristic for bi-objective vehicle routing with time window constraints
  International Journal of Production Economics, Vol. 62, No. 3
- ANALYSES ON EFFECTS OF IMPROVEMENT AND COOPERATION IN URBAN PICKUP/DELIVERY TRUCK ROUTING AND SCHEDULING ON ROAD TRAFFIC
  Doboku Gakkai Ronbunshu, Vol. 1999, No. 625
- Ein Simulated-Annealing-Verfahren für das Standardproblem der Tourenplanung mit Zeitfensterrestriktionen
- A parallel algorithm for the vehicle routing problem with time window constraints
  Annals of Operations Research, Vol. 86, No. 0
- Iterative improvement methods for a multiperiod network design problem
  European Journal of Operational Research, Vol. 110, No. 1
- A Generalized Insertion Heuristic for the Traveling Salesman Problem with Time Windows
  Michel Gendreau,
  Alain Hertz,
  Gilbert Laporte,
  Mihnea Stan,
  1 June 1998 | Operations Research, Vol. 46, No. 3
- Zwei Evolutionsstrategien für das Standardproblem der Tourenplanung mit Zeitfensterrestriktionen
- A parallel tabu search heuristic for the vehicle routing problem with time windows
  Transportation Research Part C: Emerging Technologies, Vol. 5, No. 2
- Tabu Search and Adaptive Memory Programming — Advances, Applications and Challenges
- Metaheuristics: A bibliography
  Annals of Operations Research, Vol. 63, No. 5

cover image INFORMS Journal on Computing

Volume 8, Issue 2

Spring 1996

Pages 87-191

Article Information

Metrics

Information

Published Online:May 01, 1996

Cite as

Jean-Yves Potvin, Tanguy Kervahut, Bruno-Laurent Garcia, Jean-Marc Rousseau, (1996) The Vehicle Routing Problem with Time Windows Part I: Tabu Search. INFORMS Journal on Computing 8(2):158-164.

https://doi.org/10.1287/ijoc.8.2.158

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

The Vehicle Routing Problem with Time Windows Part I: Tabu Search

Abstract

Volume 8, Issue 2

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News