Solving the traveling repairman problem with profits: A Novel variable neighborhood search approach

Abstract

The Traveling Repairman Problem with profits generalizes the Traveling Repairman Problem, by taking into account the variability of the repairman's profit over different time steps in order to maximize the total profit. In this paper, we first analyze the complexities of several neighborhood structures and the efficient updating of objective values of solutions from those neighborhoods. Then we present a new heuristic based on General variable neighborhood search, that uses a local search that combines those neighborhoods in an effective way. Detailed experiments on benchmark instances show that our new method outperforms all previous heuristics. Out of 60 instances tested, it was able to replicate the best known solutions in 20 of them and find new best solutions in the remaining 40.