Heuristics for the Traveling Repairman Problem with Profits
Thijs Dewilde, Dirk Cattrysse, Sofie Coene, Frits C. R. Spieksma, Pieter Vansteenwegen · Ghent University Academic Bibliography (Ghent University) · 2010
In the traveling repairman problem with profits, a repairman (also known as the server) visits a subset of nodes in order to collect time-dependent profits. The objective consists of maximizing the total collected revenue. We restrict our study to the case of a single server with nodes located in the Euclidean plane. We investigate properties of this problem, and we derive a mathematical model assuming that the number of visited nodes is known in advance. We describe a tabu search algorithm with multiple neighborhoods, and we test its performance by running it on instances based on TSPLIB. We conclude that the tabu search algorithm finds good-quality solutions fast, even for large instances.