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

The prize collecting Travelling salesman problem(PCTSP) has been considered as one of the most complicatedproblems. A salesman collects a prize for each visited city andpays a penalty for each non visited city. The problem is NP-Hardand practical large-scale instances cannot be solved by exactalgorithms within acceptable computational times. The aim ofthis study is to presents a hybrid method using tabu search andsimulated annealing technique to solve PCTSP called hybridsimulation annealing (HSA). This proposed HSA not onlyprevents revisiting the solution but also maintains the stochasticnature. Finally the proposed HSA heuristic is tested on eight setsof well-known benchmark, and the preliminary results indicatethat the HSA is capable of solving real-world problems,efficiently.

Keywords:

The prize collecting Travelling salesman problem , Simulated Annealing , Tabu Search , Meta-heuristics Methods