A Branch-and-Cut and MIP-based heuristics for the Prize-Collecting Travelling Salesman Problem

¹ Universidade Federal do Rio de Janeiro, PESC-COPPE, Cidade Universitária, Centro de Tecnologia, Bloco H, 21941-972 Rio de Janeiro, Brazil
² Universidade Federal Fluminense, Instituto de Computação, Rua Passo da Pátria 156 São Domingos, 24210-240 Niterói, RJ, Brazil

^* Corresponding author: glaubos@cos.ufrj.br

Received: 12 August 2019
Accepted: 23 December 2019

Abstract

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.