Paper Info
Title
Hybrid Algorithms with Detection of Promising Areas for the Prize Collecting Travelling Salesman Problem
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.
Year
DOI
Venue
2005
10.1109/ICHIS.2005.57
HIS
Keywords
Field
DocType
travelling salesman,wide variety,heuristic search,hybrid algorithms,evolutionary algorithm,promising areas,natural selection,increasing interest,travelling salesman problem,evolutionary computation,hybrid algorithm
Memetic algorithm,Bottleneck traveling salesman problem,Nearest neighbour algorithm,Mathematical optimization,Travelling salesman problem,Christofides algorithm,2-opt,Mathematics,Metaheuristic,Lin–Kernighan heuristic
Conference
ISBN
Citations 
PageRank 
0-7695-2457-5
6
0.73
References 
Authors
9
2
Name
Order
Citations
PageRank
Antonio Augusto Chaves111610.24
Luiz Antonio Nogueira Lorena249836.72