Hybrid algorithms with detection of promising areas for the prize collecting travelling salesman problem

New heuristics to solve the PCTSP are approached, using a hybrid evolutionary algorithm, called evolutionary clustering search (ECS) and an adaptation of this, called *CS, where the evolutionary component is substituted by the metaheuristics GRASP and VNS.

Abstract

The prize collecting travelling salesman problem (PCTSP) is a generalization of the travelling salesman problem. It can be associated to a salesman that collects a prize in each city visited and pays a penalty for each city not visited, with travel costs among the cities. The objective is to minimize the sum of the costs of the trip and penalties, including in the tour an enough number of cities that allow collecting a minimum prize. This paper approaches new heuristics to solve the PCTSP, using a hybrid evolutionary algorithm, called evolutionary clustering search (ECS) and an adaptation of this, called *CS, where the evolutionary component is substituted by the metaheuristics GRASP and VNS. The validation of the obtained solutions are through the comparison with the results found by a commercial solver that was able to solve only small size problems.