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.
KeywordsTabu SearchTraveling Salesman ProblemVehicle Routing Problem
E. Lawler, J. lenstra, K. Rinnooy and D. Shmoys, “The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization,” Wiley-Interscience Publication, 1985.
R. Karp, “Reducibility among Combinatorial Problems,” Plenum Press, New York, 1972, pp. 85-103.
D. Johnson, G. Gutin, L. McGeoch, A. Yeo, W. Zhang and A. Zverovich, “The Traveling Salesman Problem and Its Variations,” Kluwer Academic Publishers, Boston, 2002.
G. Reinelt, “TSPLIB—A Traveling Salesman Problem Library,” INFORMS Journal of Computing, Vol. 3, 1991, pp. 376-384. doi:10.1287/ijoc.3.4.376
J. Cordeau, G. Laporte and A. Mercier, “A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows,” The Journal of the Operational Research Society, Vol. 52, No. 8, 2001, pp. 928-936. doi:10.1057/palgrave.jors.2601163
A. Bouthillier and T. Crainic, “A Cooperative Parallel Meta-Heuristic for the Vehicle Routing Problem with Time Windows,” Computers & Operations Research, Vol. 32, No. 7, 2005, pp. 1685-1708. doi:10.1016/j.cor.2003.11.023
J. Homberger and H. Gehring, “A Two-Phase Hybrid Metaheuristic for the Vehicle Routing Problem with Time Windows,” European Journal of Operational Research, Vol. 162, No. 1, 2005, pp. 220-238. doi:10.1016/j.ejor.2004.01.027
M. Malek, M. Guruswamy, M. Pandya and H. Owens, “Serial and Parallel Simulated Annealing and Tabu Search Algorithms for the Traveling Salesman Problem,” Annals of Operations Research, Vol. 21, No. 1, 1989, pp. 59-84. doi:10.1007/BF02022093
F. Semet and E. Taillard, “Solving Real-Life Vehicle Routing Problems Efficiently Using Taboo Search,” Annals of Operations Research, Vol. 41, 1993, pp. 469-488. doi:10.1007/BF02023006
B. Garcia, J. Potvin and J. Rousseau, “A Parallel Implementation of the Tabu Search Heuristic for Vehicle Routing Problems with Time Window Constraints,” Computers & Operations Research, Vol. 21, No. 9, 1994, pp. 1025-1033. doi:10.1016/0305-0548(94)90073-6
M. Gendreau, G. Laporte and R. Séguin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Stochastic Demands and Customers,” Operations Research, Vol. 44, No. 3, 1996, pp. 469-477. doi:10.1287/opre.44.3.469
P. Badeau, M. Gendreau, F. Guertin, J.-Y. Potvin and E. Taillard, “A Parallel Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows,” Transportation Research, Vol. 5, 1997, pp. 109-122. doi:10.1016/S0968-090X(97)00005-3
J. Brand?o and A. Mercer, “A Tabu Search Algorithm for the Multi-Trip Vehicle Routing and Scheduling Problem,” European Journal of Operational Research, Vol. 100, No. 1, 1997, pp. 180-191. doi:10.1016/S0377-2217(97)00010-6
O. Br?ysy and M. Gendreau, “Tabu Search Heuristics for the Vehicle Routing Problem with Time Windows,” Technical Report, SINTEF Applied Mathematics, Department of Optimisation, Oslo, 2001.
P. Caricato, G. Ghiani, A. Grieco and E. Guerriero, “Parallel Tabu Search for a Pickup and Delivery Problem Under Track Contention,” Parallel Computing, Vol. 29, No. 5, 2003, pp. 631-639. doi:10.1016/S0167-8191(03)00046-2
H. Lau, M. Sim and K. Teo, “Vehicle Routing Problem with Time Windows and a Limited Number of Vehicles,” European Journal of Operational Research, Vol. 148, No. 3, 2003, pp. 559-569. doi:10.1016/S0377-2217(02)00363-6
C. Lin and R. Kwok, “Multi-Objective Metaheuristics for a Location-Routing Problem with Multiple Use of Vehicles on Real Data and Simulated Data,” European Journal of Operational Research, Vol. 175, No. 3, 2006, pp. 1833-1849.
N. Bianchessi and G. Righini, “Heuristic Algorithms for the Vehicle Routing Problem With Simultaneous Pick-Up and Delivery,” Computers & Operations Research, Vol. 34, No. 2, 2007, pp. 578-594. doi:10.1016/j.cor.2005.03.014
J. Brand?o, “A Deterministic Tabu Search Algorithm For the Fleet Size and Mix Vehicle Routing Problem” European Journal of Operational Research, Vol. 195, 2009, pp. 716-728. doi:10.1016/j.ejor.2007.05.059
J. Potvin, T. Kervahut, B. Garcia and J. Rousseau, “The Vehicle Routing Problem with Time Windows—Part I: Tabu Search,” INFORMS Journal of Computing, Vol. 8, 1996, pp. 158-164. doi:10.1287/ijoc.8.2.158
Y. Sharaiha, M. Gendreau, G. Laporte and I. Osman, “A Tabu Search Algorithm for the Capacitated Shortest Spanning Tree Problem,” Networks, Vol. 29, 1997, pp. 209- 223. doi:10.1002/(SICI)1097-0037(199705)29:3 3.0.CO;2-F
W. Chiang and R. Russell, “A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows,” INFORMS Journal of Computing, Vol. 9, 1997, pp. 417-430. doi:10.1287/ijoc.9.4.417
S. Ho and D. Haugland, “A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows and Split Deliveries,” Computers & Operations Research, Vol. 31, No. 12, 2004, pp. 1947-1964. doi:10.1016/S0305-0548(03)00155-2
H. Tang and E. Hooks, “A TABU Search Heuristic for the Team Orienteering Problem,” Computers & Operations Research, Vol. 32, No. 6, 2005, pp. 1379-1407. doi:10.1016/j.cor.2003.11.008
M. Bolduc, G. Laporte, J. Renaud and F. Boctor, “A Tabu Search Heuristic for the Split Delivery Vehicle Routing Problem with Production and Demand Calendars,” European Journal of Operational Research, Vol. 202, 2010, pp. 122-130. doi:10.1016/j.ejor.2009.05.008
A. Amberg, W. Domschke and S. Vob, “Multiple Center Capacitated Arc Routing Problems: A Tabu Search Algorithm Using Capacitated Trees,” European Journal of Operational Research, Vol. 124, No. 2, 2000, pp. 360- 376.
A. Hertz, G. Laporte and M. Mittaz, “A Tabu Search Heuristic for the Capacitated Arc Routing Problem,” Operations Research, Vol. 48, No. 1, 2000, pp. 129-135. doi:10.1287/opre.48.1.129.12455
W. Nanry and J. Barnes, “Solving the Pickup and Delivery Problem with Time Windows Using Reactive Tabu Search,” Transportation Research Part B: Methodological, Vol. 34, No. 2, 2000, pp. 107-121. doi:10.1016/S0191-2615(99)00016-8
S. Tsubakitani and J. Evans, “Optimizing Tabu List Size for the Traveling Salesman Problem,” Computers & Operations Research, Vol. 25, No. 2, 1998, pp. 91-97. doi:10.1016/S0305-0548(97)00030-0
R. Daniels, J. Rummel and R. Schantz, “A Model for Warehouse Order Picking,” European Journal of Operational Research, Vol. 105, No. 1, 1998, pp. 1-17. doi:10.1016/S0377-2217(97)00043-X
P. Franca, N. Sosa and V. Pureza, “An Adaptive Tabu Search Algorithm for the Capacitated Clustering Problem,” International Transactions in Operations Research, Vol. 6, 1999, pp. 665-678.
P. Augerat, J. M. Belenguer, E. Benavent, A. Corberán and D. Naddef, “Separating Capacity Constraints in the CVRP Using Tabu Search,” European Journal of Operational Research, Vol. 106, No. 2-3, 1998, pp. 546-557. doi:10.1016/S0377-2217(97)00290-7
I. Chao, “A Tabu Search Method for the Truck and Trailer Routing Problem,” Computers & Operations Research, Vol. 29, No. 1, 2002, pp. 33-51. doi:10.1016/S0305-0548(00)00056-3
J. Cordeau and G. Laporte, “A Tabu Search Heuristic for the Static Multi-Vehicle Dial-a-Ride Problem,” Transportation Research Part B: Methodological, Vol. 37, No. 6, 2003, pp. 579-594. doi:10.1016/S0191-2615(02)00045-0
S. Scheuerer, “A Tabu Search Heuristic for the Truck and Trailer Routing Problem,” Computers & Operations Research, Vol. 33, No. 4, 2006, pp. 894-909. doi:10.1016/j.cor.2004.08.002
M. Gendreau, A. Hertz and G. Laporte, “A Tabu Search Heuristic for the Vehicle Routing Problem,” Management Science, Vol. 40, No. 10, 1994, pp. 1276-1290. doi:10.1287/mnsc.40.10.1276
I. Osman, “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem,” Annals of Operations Research, Vol. 41, 1993, pp. 421- 451. doi:10.1007/BF02023004
Y. Rochat and F. Semet, “A Tabu Search Approach for Delivering Pet Food and Flour in Switzerland,” The Journal of the Operational Research Society, Vol. 45, No. 11, 1994, pp. 1233-1246.
J. Brand?o and A. Mercer, “The Multi-Trip Vehicle Routing Problem,” The Journal of the Operational Research Society, Vol. 49, No. 8, 1998, pp. 799-805.
G. Barbarosoglu and D. Ozgur, “A Tabu Search Algorithm for the Vehicle Routing Problem,” Computers and Operations Research, Vol. 26, No. 3, 1999, pp. 255-270. doi:10.1016/S0305-0548(98)00047-1
D. Tuzun and L. Burke, “A Two-Phase Tabu Search Approach to the Location Routing Problem,” European Journal of Operational Research, Vol. 116, 1999, pp. 87- 99. doi:10.1016/S0377-2217(98)00107-6
D. Ahr and G. Reinelt, “A Tabu search Algorithm for the Min-Max k-Chinese Postman Problem,” Computers & Operations Research, Vol. 33, No. 12, 2006, pp. 3403- 3422. doi:10.1016/j.cor.2005.02.011
T. G. Crainic, M. Gendreau, P. Soriano and M. Toulouse, “A Tabu Search Procedure for Multicommodity Location/Allocation with Balancing Requirements,” Annals of Operations Research, Vol. 41, 1993, pp. 359-383. doi:10.1007/BF02023001
B. Crevier, J. Cordeau and G. Laporte, “The Multi-Depot Vehicle Routing Problem with Inter-Depot Routes,” European Journal of Operational Research, Vol. 176, No. 2, 2007, pp. 756-773. doi:10.1016/j.ejor.2005.08.015
E. Zachariadis, C. Tarantilis and C. Kiranoudis, “A Guided Tabu Search for the Vehicle Routing Problem with Two-Dimensional Loading Constraints,” European Journal of Operational Research, Vol. 195, 2009, pp. 729-743. doi:10.1016/j.ejor.2007.05.058
M. Gendreau, G. Laporte and F. Semet, “A Tabu Search Heuristic for the Undirected Selective Travelling Salesman Problem,” European Journal of Operational Research, Vol. 106, 1998, pp. 539-545. doi:10.1016/S0377-2217(97)00289-0
M. Gendreau, G. Laporte and D. Vigo, “Heuristics for the Traveling Salesman Problem with Pickup and Delivery,” Computers & Operations Research, Vol. 26, No. 7, 1999, pp. 699-714. doi:10.1016/S0305-0548(98)00085-9
M. Gendreau, M. Iori, G. Laporte and S. Martello, “A Tabu Search Heuristic for the Vehicle Routing Problem with Two-Dimensional Loading Constraints,” Networks, Vol. 51, No. 1, 2008, pp. 4-18. doi:10.1002/net.20192
N. A. Wassan, A. Wassan and G. Nagy, “A Reactive Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pickups and Deliveries,” Journal of Combinatorial Optimization, Vol. 15, 2008, pp. 368-386. doi:10.1007/s10878-007-9090-4
H. Tamashiro, M. Nakamura, T. Okazaki and D. Kang, “A Tabu Search Approach Combined with an Extended Saving Method for Multi-Depot Vehicle Routing Problems with Time Windows,” Biomedical Soft Computing and Human Sciences, Vol. 15, No. 1, 2010, pp. 31-39.
J. Cordeau and M. Maischberger, “A Parallel Iterated Tabu Search Heuristic for Vehicle Routing Problems,” Computers & Operations Research, Vol. 39, 2012, pp. 2033-2050. doi:10.1016/j.cor.2011.09.021
J. Renaud, G. Laporte and F. Boctor, “A Tabu Search Heuristic for the Multi-Depot Vehicle Routing Problem,” Computers & Operations Research, Vol. 23, 1996, pp. 229-235. doi:10.1016/0305-0548(95)O0026-P
F. Montane and R. Galvao, “A Tabu Search Algorithm for the Vehicle Routing Problem with Simultaneous Pick- Up and Delivery Service,” Computers & Operations Research, Vol. 33, No. 3, 2006, pp. 595-619. doi:10.1016/j.cor.2004.07.009
J. Brand?o, “A Tabu Search Algorithm for the Heterogeneous Fixed Fleet Vehicle Routing Problem,” Computers & Operations Research, Vol. 38, 2011, pp. 140-151. doi:10.1016/j.cor.2010.04.008
S. Thangiah, I. Osman and T. Sun, “Hybrid Genetic Algorithm, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problem with Time Windows,” Technical Report, Computer Science Department, Slippery Rock University, 1994.
Y. Rochat and E. Taillard, “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing,” Journal of Heuristics, Vol. 1, 1995, pp. 147-167. doi:10.1007/BF02430370
V. E. Taillard, P. Badeau, M. Gendreau, F. Guertin, and J.-Y. Potvin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows,” Transportation Science, Vol. 31, No. 2, 1997, pp. 170-186. doi:10.1287/trsc.31.2.170
J. Cordeau, M. Gendreau and G. Laporte, “A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems,” Networks, Vol. 30, No. 2, 1998, pp. 105-119. doi:10.1002/(SICI)1097-0037(199709)30:2 3.0.CO;2-G
P. Toth and D. Vigo, “The Granular Tabu Search and Its Application to the VRP,” Technical Report, University of Bologna, 1998.
E. Zachariadis, C. Tarantilis and C. Kiranoudis, “A Guided Tabu Search for the Vehicle Routing Problem with Two-Dimensional Loading Constraints,” European Journal of Operational Research, Vol. 195, 2009, pp. 729-743. doi:10.1016/j.ejor.2007.05.058
J. C?té and J.-Y. Potvin, “A Tabu Search Heuristic for the Vehicle Routing Problem with Private Fleet and Common Carrier,” European Journal of Operational Research, Vol. 198, 2009, pp. 464-469. doi:10.1016/j.ejor.2008.09.009
C. Tarantilis, “Solving The Vehicle Routing Problem with Adaptive Memory Programming Methodology,” Computers & Operations Research, Vol. 32, No. 9, 2005, pp. 2309-2327. doi:10.1016/j.cor.2004.03.005
G. Clarke and J. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, Vol. 12, 1964, pp. 568-581. doi:10.1287/opre.12.4.568
J. Shen, F. Xu and P. Zheng, “A Tabu Search Algorithm for the Routing and Capacity Assignment Problem in Computer Networks,” Computers & Operations Research, Vol. 32, No. 11, 2005, pp. 2785-2800. doi:10.1016/j.cor.2004.04.004
A. Breedam, “Comparing Descent Heuristics and Metaheuristics for the Vehicle Routing Problem,” Computers & Operations Research, Vol. 24, No. 4, 2001, pp. 289- 315. doi:10.1016/S0305-0548(99)00101-X
M. Gendreau, A. Hertz and G. Laporte, “New Insertion and Post Optimization Procedures for the Traveling Salesman Problem,” Operations Research, Vol. 40, No. 6, 1992, pp. 1086-1094. doi:10.1287/opre.40.6.1086
X. Fan, N. Li, B. Zhang and Z. Liu, “Research on Vehicle Routing Problem with Soft Time Windows Based on Tabu Search Algorithm,” IEEE 18th International Conference, 3-5 September 2011.
D. Paraskevopoulos, P. Repoussis, C. Tarantilis, G. Ioannou and G. Prastacos, “A Reactive Variable Neighborhood Tabu Search for the Heterogeneous Fleet Vehicle Routing Problem with Time Windows,” Journal of Heuristics, Vol. 14, 2008, pp. 425-455. doi:10.1007/s10732-007-9045-z
L. Moccia, J. Cordeau and G. Laporte, “An Incremental Tabu Search Heuristic for the Generalized Vehicle Routing Problem with Time Windows,” Journal of the Operational Research Society, Vol. 63, 2012, pp. 232-244. doi:10.1057/jors.2011.25
T. Wu, C. Low and J. Bai, “Heuristic Solutions to Multi- Depot Location-Routing Problems,” Computers & Operations Research, Vol. 29, No. 10, 2002, pp. 1393-1415. doi:10.1016/S0305-0548(01)00038-7
C. Ting, S. Li and C. Lee, “On the Harmonious Mating Strategy through Tabu Search,” Information Sciences, Vol. 156, No. 3-4, 2003, pp. 189-214. doi:10.1016/S0020-0255(03)00176-2
P. Greistorfer, “A Tabu Scatter Search Metaheuristic for the Arc Routing Problem,” Computers and Industrial Engineering, Vol. 44, No. 2, 2003, pp. 249-266. doi:10.1016/S0360-8352(02)00178-X
R. Russell and W. Chiang, “Scatter Search for the Vehicle Routing Problem with Time Windows,” European Journal of Operational Research, Vol. 169, No. 2, 2006, pp. 606-622. doi:10.1016/j.ejor.2004.08.018
E. Taillard, “Robust Taboo Search for the Quadratic Assignment Problem,” Parallel Computing, Vol. 17, 1991, pp. 433-445. doi:10.1016/S0167-8191(05)80147-4
F. Glover, M. Laguna and C. Reeves, “Tabu Search,” In: C. Reeves, Ed., Modern Heuristic Techniques for Combinatorial Problems, Blackwell Scientific Publications, Oxford, 1993.
J. Crino, J. Moore, J. W. Barnes and W. Nanry, “Solving the Theater Distribution Vehicle Routing and Scheduling Problem Using Group Theoretic Tabu Search,” Mathematical and Computer Modelling, Vol. 139, No. 6-8, 2004, pp. 599-616. doi:10.1016/S0895-7177(04)90543-2
Tabu Search Implementation on Traveling Salesman Problem and Its Variations: A Literature Survey — Oak Academic Publishing