Tabu Search Implementation on Traveling Salesman Problem and Its Variations: A Literature Survey

The Traveling Salesman Problem (TSP) and its allied problems like Vehicle Routing Problem (VRP) are one of the most widely studied problems in combinatorial optimization. It has long been known to be NP-hard and hence research on developing algorithms for the TSP has focused on approximate methods in addition to exact methods. Tabu search is one of the most widely applied metaheuristic for solving the TSP. In this paper, we review the tabu search literature on the TSP and its variations, point out trends in it, and bring out some interesting research gaps in this literature.

• Publication year

  2012

• Venue

  American Journal of Operations Research

• Publication date

  2012-06-20

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4236/AJOR.2012.22019
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A parallel iterated tabu search heuristic for vehicle routing problems

  2012cited by this paper
• An incremental tabu search heuristic for the generalized vehicle routing problem with time windows

  2012cited by this paper
• Research on vehicle routing problem with soft time windows based on tabu search algorithm

  2011cited by this paper
• A tabu search algorithm for the heterogeneous fixed fleet vehicle routing problem

  2011influential reference
• A tabu search heuristic for the split delivery vehicle routing problem with production and demand calendars

  2010cited by this paper
• A Tabu Search Approach combined with An Extended Saving Me- thod for Multi-depot Vehicle Routing Problems with Time Windows

  2010cited by this paper
• A Guided Tabu Search for the Vehicle Routing Problem with two-dimensional loading constraints

  2009cited by this paper
• A Combining Heuristic Algorithm for the Multi-depot Vehicle Routing Problem with Inter-depot Routes

  2009cited by this paper
• A deterministic tabu search algorithm for the fleet size and mix vehicle routing problem

  2009influential reference
• A tabu search heuristic for the vehicle routing problem with private fleet and common carrier

  2009influential reference
• A Tabu search heuristic for the vehicle routing problem with two‐dimensional loading constraints

  2008cited by this paper
• A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries

  2008cited by this paper
• A reactive variable neighborhood tabu search for the heterogeneous fleet vehicle routing problem with time windows

  2008cited by this paper
• The traveling salesman problem and its variations

  2007cited by this paper
• Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery

  2007influential reference
• A tabu search heuristic for the truck and trailer routing problem

  2006influential reference
• A tabu search algorithm for the min-max k-Chinese postman problem

  2006influential reference
• Scatter search for the vehicle routing problem with time windows

  2006cited by this paper
• Multi-objective metaheuristics for a location-routing problem with multiple use of vehicles on real data and simulated data

  2006influential reference
• A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service

  2006influential reference
• A TABU search heuristic for the team orienteering problem

  2005influential reference
• Solving the vehicle routing problem with adaptive memory programming methodology

  2005influential reference
• A cooperative parallel meta-heuristic for the vehicle routing problem with time windows

  2005influential reference
• A tabu search algorithm for the routing and capacity assignment problem in computer networks

  2005cited by this paper
• A two-phase hybrid metaheuristic for the vehicle routing problem with time windows

  2005influential reference
• A tabu search heuristic for the vehicle routing problem with time windows and split deliveries

  2004influential reference
• Solving the theater distribution vehicle routing and scheduling problem using group theoretic tabu search

  2004cited by this paper
• Vehicle routing problem with time windows and a limited number of vehicles

  2003influential reference
• Parallel tabu search for a pickup and delivery problem under track contention

  2003cited by this paper
• On the harmonious mating strategy through tabu search

  2003cited by this paper
• A Tabu Search Heuristic for the Static Multi-Vehicle Dial-a-Ride Problem

  2002influential reference
• Heuristic solutions to multi-depot location-routing problems

  2002cited by this paper
• Tabu Search heuristics for the Vehicle Routing Problem with Time Windows

  2002cited by this paper
• A Tabu Scatter Search Metaheuristic for the Arc Routing Problem

  2002cited by this paper
• A tabu search method for the truck and trailer routing problem

  2002cited by this paper
• Comparing descent heuristics and metaheuristics for the vehicle routing problem

  2001influential reference
• A unified tabu search heuristic for vehicle routing problems with time windows

  2001influential reference
• Solving the pickup and delivery problem with time windows using reactive tabu search

  2000influential reference
• Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees

  2000influential reference
• A Tabu Search Heuristic for the Capacitated Arc Routing Problem

  2000cited by this paper
• A tabu search algorithm for the vehicle routing problem

  1999influential reference
• Heuristics for the traveling salesman problem with pickup and delivery

  1999cited by this paper
• A two-phase tabu search approach to the location routing problem

  1999cited by this paper
• An adaptive tabu search algorithm for the capacitated clustering problem

  1999cited by this paper
• Optimizing tabu list size for the traveling salesman problem

  1998influential reference
• Separating capacity constraints in the CVRP using tabu search

  1998cited by this paper
• The multi-trip vehicle routing problem

  1998cited by this paper
• A model for warehouse order picking

  1998cited by this paper
• A tabu search heuristic for the undirected selective travelling salesman problem

  1998cited by this paper
• Tabu Search

  1997cited by this paper
• A tabu search heuristic for periodic and multi-depot vehicle routing problems

  1997influential reference
• A tabu search algorithm for the multi-trip vehicle routing and scheduling problem

  1997influential reference
• A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows

  1997influential reference
• A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows

  1997cited by this paper
• A PARALLEL TABU SEARCH HEURISTIC FOR THE VEHICLE ROUTING PROBLEM WITH TIME WINDOWS

  1997influential reference
• A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem

  1997cited by this paper
• A tabu search heuristic for the multi-depot vehicle routing problem

  1996cited by this paper
• The Vehicle Routing Problem with Time Windows Part I: Tabu Search

  1996cited by this paper
• A Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers

  1996influential reference
• Probabilistic diversification and intensification in local search for vehicle routing

  1995cited by this paper
• A Tabu Search Approach for Delivering Pet Food and Flour in Switzerland

  1994influential reference
• A parallel implementation of the Tabu search heuristic for vehicle routing problems with time window constraints

  1994cited by this paper
• Solving real-life vehicle routing problems efficiently using tabu search

  1993cited by this paper
• Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem

  1993influential reference
• A tabu search procedure for multicommodity location/allocation with balancing requirements

  1992cited by this paper
• New Insertion and Postoptimization Procedures for the Traveling Salesman Problem

  1992cited by this paper
• A Tabu Search Heuristic for the Vehicle Routing Problem

  1991influential reference
• Robust taboo search for the quadratic assignment problem

  1991cited by this paper
• TSPLIB - A Traveling Salesman Problem Library

  1991cited by this paper
• Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem

  1990influential reference
• THE TRAVELING SALESMAN PROBLEM A Guided Tour of Combinatorial Optimization

  1986cited by this paper
• Reducibility Among Combinatorial Problems

  1972cited by this paper
• Scheduling of Vehicles from a Central Depot to a Number of Delivery Points

  1964cited by this paper

• A multiobjective construction site layout and safety planning model based on evolutionary algorithms

  2026cites this paper
• Quantum annealing‐driven branch and bound for the total weighted tardiness traveling salesman problem on the D‐Wave quantum computer

  2026cites this paper
• Hopfield network-based algorithm for combinatorial optimization

  2026cites this paper
• Cutting path planning using reinforcement learning with adaptive sequence adjustment and attention mechanisms

  2025cites this paper
• Battery-Aware UAV Path Planning for Maximum Value Collection: A Spatial-Correction and DRL-Based Optimization Approach

  2025cites this paper
• CompreCity: Accelerating the Traveling Salesman Problem on GPU with data compression

  2024cites this paper
• Algorithmic strategies for finding the best TSP 2-OPT move in average sub-quadratic time

  2024cites this paper
• An End-to-End Deep Reinforcement Learning Framework for Electric Vehicle Routing Problem

  2024cites this paper
• Learning-driven Evolutionary Optimization for the Traveling Salesman Problem

  2024cites this paper
• An Improved Genetic Algorithm Optimization by Driver Preference Route Mining for Minimizing Actual Travel Time

  2023cites this paper
• HiTSP: Towards a Hierarchical Neural Framework for Large-scale Traveling Salesman Problems

  2023cites this paper
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors

  2023cites this paper
• Route Planning Based on Deep Reinforcement Learning to Minimize Energy Consumption in UAV Photogrammetry

  2022cites this paper
• OPTIMIZING THE PROCESS OF PICK-UP AND DELIVERY WITH TIME WINDOWS USING ANT COLONY AND TABU SEARCH ALGORITHMS

  2022cites this paper
• Generic Tabu Search

  2022cites this paper
• Non-revisiting stochastic search revisited: Results, perspectives, and future directions

  2021cites this paper
• A Tabu Search algorithm for the Probabilistic Orienteering Problem

  2021cites this paper
• Discrete crow-inspired algorithms for traveling salesman problem

  2021cites this paper
• Modified transitive closure algorithm for traveling salesman problems

  2020cites this paper
• Study and Analysis of Various Heuristic Algorithms for Solving Travelling Salesman Problem—A Survey

  2020cites this paper
• Resilience-Driven Multiobjective Restoration Planning for Water Distribution Networks

  2020cites this paper
• IMPROVED GENETIC ALGORITHM USING HYBRID INITIAL POPULATION TO SOLVE TRAVELLING SALESMAN PROBLEM

  2019cites this paper
• A cutting sequence optimization method based on tabu search algorithm for complex parts machining

  2019cites this paper
• Solving the Traveling Salesman Problem Using Hydrological Cycle Algorithm

  2018cites this paper
• Enhanced Structured Population Approach for Genetic Algorithm

  2017cites this paper
• A bi-level school bus routing problem with bus stops selection and possibility of demand outsourcing

  2017cites this paper
• Optimisation de problème de tournées de véhicules de service à domicile. (Optimization of vehicle routing problem for field service)

  2017cites this paper
• Efficient preprocessing methods for tabu search: an application on asymmetric travelling salesman problem

  2017cites this paper
• Combinatorial Optimization: Comparison of Heuristic Algorithms in Travelling Salesman Problem

  2017cites this paper
• Discrete swallow swarm optimization algorithm for travelling salesman problem

  2017cites this paper
• A Genetic Algorithm's Approach to the Optimization of Capacitated Vehicle Routing Problems

  2016cites this paper
• Concentric Tabu Search Algorithm for Solving Traveling Salesman Problem

  2016cites this paper
• Hybrid water flow-like algorithm with Tabu search for traveling salesman problem

  2016cites this paper
• Worm Optimization for the Traveling Salesman Problem

  2016cites this paper
• Heuristic algorithms for static and dynamic frequency assignment problems

  2016cites this paper
• Composition of Optimized Assessment Sheet with Multi-criteria using Evolutionary IntelligentWater Drops (EvIWD) Algorithm

  2016cites this paper
• Redeployment in Convoys of Fleets of Shared Vehicles. (Redéploiement en convois de flottes de véhicules partagés)

  2016cites this paper
• A new improved fruit fly optimization algorithm for traveling salesman problem

  2016cites this paper
• Apoio à tomada de decisão e minimização da perda de matéria prima em processos de manufatura

  2015influential citation
• Novel approach to optimize milk-run delivery: A case study

  2015cites this paper
• An Investigation of Hybrid Tabu Search for the Traveling Salesman Problem

  2015influential citation
• A Review of the Optimization Algorithms on Traveling Salesman Problem

  2015cites this paper
• A Review of Traveling Salesman Problem with Time Window Constraint

  2015cites this paper
• An Analysis of New Optimization Algorithm for Different Combinatorial Problems

  2015cites this paper
• A Problem-based Heuristic for Asymmetric Travelling Salesman Problems

  2015cites this paper
• Ant Colony Optimization Algorithm for Solving the Provider - Modified Traveling Salesman Problem

  2014cites this paper
• Optimization of COCOMOII Model Coefficients using Tabu Search

  2014cites this paper
• Cell formation problem: An multithreading Tabu search for setup time optimization for limited machine magazines: A New Solution For A Classical Problem

  2014influential citation
• Worm Optimization: A novel optimization algorithm inspired by C. Elegans

  2014cites this paper
• A Performance Comparison of Genetic Algorithm's Mutation Operators in n-Cities Open Loop Travelling Salesman Problem

  2014cites this paper
• A Survey of Tabu Search in Combinatorial Optimization

  2014cites this paper
• A MULTITHREADING TABU SEARCH FOR SETUP TIME OPTIMIZATION FOR LIMITED MACHINE MAGAZINES IN THE CELL FORMATION PROBLEM

  2014cites this paper
• Preprocessing Schemes for Tabu search on Asymmetric Traveling Salesman Problem

  2013cites this paper
• A New Approach to the Optimization of the CVRP through Genetic Algorithms

  2012cites this paper
• Metaheuristic Approaches for Solving School Bus Routing Problems: A Comprehensive Review.

  year unknowncites this paper