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

作　　者：Sumanta Basu 

机构地区：[1]Indian Institute of Management Calcutta, Kolkata, India

出　　处：《American Journal of Operations Research》2012年第2期163-173,共11页美国运筹学期刊（英文）

摘　　要：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.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.

关 键 词：Tabu SEARCH TRAVELING SALESMAN PROBLEM Vehicle ROUTING PROBLEM 

分 类 号：TP1[自动化与计算机技术—控制理论与控制工程]