Introduction
Under heuristic methods, the tabu search algorithm belongs to the meta-heuristic method. It has been designed to optimize VRP solutions. It is based on the principles of human memory. Tabu search algorithm prevents repetitions by prohibiting or punishing them in the following step. Tabu algorithm’s primary goal is to satisfy the deficient parts of simple hill climbing heuristic (HC).
The proximity between a new solution and a desired outcome is determined in HC by comparing new solution candidates with old ones. In this case, the old solution will replace the closest candidate between new and old solutions. In HC, this factor may create a vicious cycle, as it may be stuck between more than two neighborhoods.
Searches that do not utilize a control mechanism and do not choose the most suitable HC may route to the best local points depending on the properties of the searched area. Real-life problems have many local bests, but fewer global bests, and in some cases there is only one, so a vicious cycle is inevitable. In this case, tabu recommends using memory usage to avoid a vicious cycle. In a short period of time, candidates that have already been visited or should not be visited are stored in a list, called a tabu list.
Therefore, the related list steps do not appear on the page for a short period of time. Avoiding local searches results in more accurate results. A tabu search algorithm consists of a starting solution, movement mechanisms, neighborhood, memory, tabu list, tabu destroy criteria, and stopping.
It is necessary to have a starting point in order to solve the tabu search algorithm. Many methods can be used to acquire a starting point. Heuristic methods can also produce random results. To gain the starting solution in the project, an overly greedy approach is used. A greedy approach chooses the closest possible solution. A city is chosen as a starting point, followed by the next closest city, and finally a city list is compiled by adding the last city to the list. A movement mechanism is responsible for gaining new solutions with the alteration of existing solutions.
In the existing solution, the neighborhood table represents the possible movements in the movement mechanism. These movements can be between routes or for routes. A neighborhood structure is one of the most important components of the tabu search algorithm. The main goal of optimizing the solution is to choose the best movements. In order to get true results from the algorithm, neighbor selection is also crucial. While choosing the neighbors, n?1 neighbors should be chosen for n points. Memory is another component of the tabu search algorithm. Tabu list is a list of the states that are arose during the tabu search algorithm and the states that should not be searched. These states are called tabu. Memory is temporary and is used to avoid a vicious cycle. After a while, these movements are removed from the tabu list and can be used.
The Tabu list keeps track of states that should not be looked at during the search. The size of the Tabu list influences the results. Tabu destroy criteria are states in which the tabu disappears. The tabu destroy criterion is getting closer to the produced solution than the older solution, and as a result, the tabu is destroyed. Utilizing this criterion increases the effectiveness of the tabu search algorithm. The tabu search algorithm continues to search until one or more stopping rules are provided. The algorithm gets stuck and does not produce better results when the chosen neighbor solution has no neighbor, when it reaches a definite number of iterations, when it reaches a definite value of a solution.