09-09-2017, 09:42 AM
A new approach has been adopted to parallelize simulated annealing and the results are compared with the traditional annealing algorithm. This approach uses an abbreviated cooling program and achieves superlinear acceleration. A new search technique, called tabu search, has also been adapted to run in a parallel computing environment. The comparison between simulated annealing and tabu search indicates that the tabu search systematically overcomes simulated annealing with respect to the calculation time while giving comparable solutions.
The vendor's problem (TSP) and its allied problems such as the 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 therefore research into the development of algorithms for the TSP has focused on approximate methods in addition to accurate methods. The tabu search is one of the most widely applied metaheuristics to solve TSP. In this article, we review the tabu search literature on the TSP and its variations, point out the trends in it, and bring up some interesting research gaps in this literature.
TSP is known to be NP-hard. This means that no known algorithm is guaranteed to resolve all TSP instances to the optimal one within a reasonable execution time. Thus, in addition to the exact solution approaches, a series of heuristics and metaheuristics have been developed to solve problems approximately. Heuristics and metaheuristics market the optimality of the solutions they produce with execution times. They are used to find "good" quality solutions within reasonable lead times. Meta-heuristics are usually improvement algorithms, that is, they begin with one or more feasible solutions to the problem in question and suggest methods for improving such solutions. Typical examples of metaheuristics include local search, tabu search, simulated annealing, and genetic algorithms. The literature shows that the tabu search is one of the most widely used metaheuristic procedures to solve combinatorial optimization problems. It is an improvement heuristic based on the local search. It starts with an initial solution to the problem (a tour in the case of TSP), calls it a current solution, and looks for the best solution in an appropriately defined neighborhood (a collection of tours that can be "easily" the current solution) the solution. Next, designate the best solution in the neighborhood as the current solution and start the search process again. The tabu search ends when certain termination conditions have been met, whether they imply runtime or maximum iteration count conditions, or solution quality objectives, or both. To prevent the tabu search from considering the solutions it has visited in recent iterations, the tabu search maintains a list of neighboring generation moves that it considers to be forbidden, or taboo (hence the name, taboo search), and ignores the solutions that can be reached using those taboo moves while looking in the neighborhood for a solution. Once a move enters the list of taboo moves, it stays there for a predefined number of tabu search iterations (called the tabu holding of the move). Therefore, the list of taboo moves continuously changes during the execution of the search, making the tabu search an adaptive memory search algorithm. Several researchers have added features that enrich the basic tabu search algorithm described here, such as intermediate term memory structures, long term memory structures, and aspiration criteria, which have been widely applied to tabu search implementations for most of the problems in TSP or in VRP. Other features that have been proposed, but not commonly implemented for the tabu search in TSPs are strategic oscillation, rerouting path, candidate list strategies, etc. In this paper, we review the literature on the application of tabu search to TSPs and problems very closely related to it, such as the problem of vehicle routing and its variations. We reviewed 76 articles on the application of the taboo search to these problems. The papers we reviewed appeared mainly printed in the last twenty years. Classification of the literature based on problem size (Section 2), generation of initial solutions (Section 3), selection of movements (Section 4), choice of short, medium and long term memory structures (Section 5 to Section 7 ) and aspiration criteria (Section 8). We summarize our findings in the Section 9.
The vendor's problem (TSP) and its allied problems such as the 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 therefore research into the development of algorithms for the TSP has focused on approximate methods in addition to accurate methods. The tabu search is one of the most widely applied metaheuristics to solve TSP. In this article, we review the tabu search literature on the TSP and its variations, point out the trends in it, and bring up some interesting research gaps in this literature.
TSP is known to be NP-hard. This means that no known algorithm is guaranteed to resolve all TSP instances to the optimal one within a reasonable execution time. Thus, in addition to the exact solution approaches, a series of heuristics and metaheuristics have been developed to solve problems approximately. Heuristics and metaheuristics market the optimality of the solutions they produce with execution times. They are used to find "good" quality solutions within reasonable lead times. Meta-heuristics are usually improvement algorithms, that is, they begin with one or more feasible solutions to the problem in question and suggest methods for improving such solutions. Typical examples of metaheuristics include local search, tabu search, simulated annealing, and genetic algorithms. The literature shows that the tabu search is one of the most widely used metaheuristic procedures to solve combinatorial optimization problems. It is an improvement heuristic based on the local search. It starts with an initial solution to the problem (a tour in the case of TSP), calls it a current solution, and looks for the best solution in an appropriately defined neighborhood (a collection of tours that can be "easily" the current solution) the solution. Next, designate the best solution in the neighborhood as the current solution and start the search process again. The tabu search ends when certain termination conditions have been met, whether they imply runtime or maximum iteration count conditions, or solution quality objectives, or both. To prevent the tabu search from considering the solutions it has visited in recent iterations, the tabu search maintains a list of neighboring generation moves that it considers to be forbidden, or taboo (hence the name, taboo search), and ignores the solutions that can be reached using those taboo moves while looking in the neighborhood for a solution. Once a move enters the list of taboo moves, it stays there for a predefined number of tabu search iterations (called the tabu holding of the move). Therefore, the list of taboo moves continuously changes during the execution of the search, making the tabu search an adaptive memory search algorithm. Several researchers have added features that enrich the basic tabu search algorithm described here, such as intermediate term memory structures, long term memory structures, and aspiration criteria, which have been widely applied to tabu search implementations for most of the problems in TSP or in VRP. Other features that have been proposed, but not commonly implemented for the tabu search in TSPs are strategic oscillation, rerouting path, candidate list strategies, etc. In this paper, we review the literature on the application of tabu search to TSPs and problems very closely related to it, such as the problem of vehicle routing and its variations. We reviewed 76 articles on the application of the taboo search to these problems. The papers we reviewed appeared mainly printed in the last twenty years. Classification of the literature based on problem size (Section 2), generation of initial solutions (Section 3), selection of movements (Section 4), choice of short, medium and long term memory structures (Section 5 to Section 7 ) and aspiration criteria (Section 8). We summarize our findings in the Section 9.