Route Optimization of Airplane Travel Plans Using the Tabu-Simulated Annealing Algorithm to Solve the Traveling Salesman Challenge 2.0

摘要

Traveling Salesman Problem (TSP) has been emerged as NP-hard problem in which there is no exact algorithm that can solve it in polynomial time. There has been an increasing interest in implementing TSP to find the shortest travel route where the trip starts from a city and must end in the same city as the departure city in a condition that every city has to be visited exactly once. Another important feature of TSP is to find travel routes with the lowest possible cost. This paper investigates a new variant of TSP to solve airplane travel plans problem in the Travelling Salesman Challenge (TSC) 2.0. A hybrid Tabu Search and Simulated Annealing was used to solve the problem. The results show that the proposed algorithm can solve the problem and outperforms great deluge algorithm, i.e. 48.54% vs 41.33% measured by the improvement from the initial solution.