The Prize-collecting Travelling Salesman Problem
Date:
Abstract: We study the Prize-collecting Travelling Salesman Problem: given an undirected graph with a cost function on the edges and a prize function on the vertices, find a simple cycle rooted at the origin that minimises the total cost such that total prize is at least some quota. Our aim is to find exact solutions on general graphs where the cost function does not necessarily obey the triangle inequality. We are motivated by the real-world problem of finding a sufficiently long running route in a city that minimises the air pollution exposure of the runner. We propose a new heuristic, valid inequalities and a branch and cut algorithm for solving sparse, non-metric instances. Finally, we analyse the performance of our algorithms on the London air quality dataset and the TSPLIB dataset.