1 October 2019 in Expert Systems with Applications
GRGlaydston Mattos Ribeiro
IHIvone Catarina Simões Hoffmann
Ivone Catarina Simões Hoffmann
+3
2 March 2021 in RAIRO - Operations Research
The Prize Collecting Traveling Salesman Problem (PCTSP) represents a generalization of the well-known Traveling Salesman Problem. The PCTSP can be associated with a salesman that collects a prize in each visited city and pays a penalty for each unvisited city, with travel costs among the cities. The objective is to minimize the sum of the costs of the tour and penalties, while collecting a minimum amount of prize. This paper suggests MIP-based heuristics and a branch-and-cut algorithm to solve the PCTSP. Experiments were conducted with instances of the literature, and the results of our methods turned out to be quite satisfactory.
1 May 2021 in RAIRO - Operations Research
This paper presents a Greedy Randomized Adaptive Search Procedure (GRASP) for the Prize-Collecting Covering Tour Problem (PCCTP), which is the problem of finding a route for traveling teams that provide services to communities geographically distant from large urban locations. We devised a novel hybrid heuristic by combining a reactive extension of the GRASP with Random Variable Neighborhood Search (VND) meta-heuristic for the purpose of solving the PCCTP. Computational experiments were conducted on a PCCTP benchmark from the literature, and the results demonstrate our approach provides a significant improvement in solving PCCTP and comparable with the state-of-the-art, mainly regarding the computational processing time.
29 May 2018 in International Transactions in Operational Research
30 June 2026 in Electric Power Systems Research
ASAna Lúcia Gouveia de Sabóia
Ana Lúcia Gouveia de Sabóia