A Hybrid Simulated Annealing Algorithm for the Prize Collecting Travelling Salesman Problem

International audienceA salesman who travels between pairs of cities and collects a prize for each visited city and pays a penalty for each non visited city is considered as one of the most complex problems called The prize collecting Travelling salesman problem (PCTSP). The problem is NP-Hard and large-scale operations cannot be solved with exact algorithms at acceptable computational times. The purpose of this study is to provide hybrid simulation annealing (HSA) that is a hybrid method using the tabu search and simulated annealing technique to solve PCTSP. This HSA proposal not only prevents revisiting the solution but also preserves the stochastic nature. Finally the proposed HSA heuristic has been tested on eight sets of well-known benchmark, and the preliminary results indicate that the HSA is capable of solving real-world problems