Solving the profitable tour problem using ant colony system

Abstract

The Traveling Salesman Problem (TSP) is one of the most widely studied combinatorial optimization problems. Many heuristic algorithms such as tabu search, genetic algorithm, and simulated annealing are applicable to this problem. There are some extensions of the TSP such as the Profitable Tour Problem (PTP), the Orienteering Problem (OP) and Prize-Collecting TSP (PCTSP). The PTP includes a different objective function than the TSP where the objective is to maximize the profit while minimizing the traveling cost. Hence, it is not an obligation to visit all of the cities. In this thesis, a hybrid version of the ACS is used to solve the PTP for the first time in the literature. A local search model which includes inversion, insertion, double insertion, extraction and double extraction procedures is proposed. The ACS algorithm is adjusted to be used in the PTP. Four different strategies are presented in the paper and their results are compared with the optimal solutions found by using the Cplex solver. Results show that the PTP can efficiently be solved by the ACS algorithm.