Memetic algorithm for the multiple traveling repairman problem with profits

摘要

In this study, we extend the traveling repairman problem with profits (TRPP) by considering the use of multiple vehicles, which occurs commonly in practice. We call the resulting problem the multiple traveling repairman problem with profits (MTRPP). In MTRPP, a fleet of identical vehicles is dispatched to visit a subset of nodes in order to collect time-dependent profits. To solve MTRPP, we present a highly effective memetic algorithm, which combines (i) a randomized greedy construction method for initial solution generation, (ii) a variable neighborhood search for local refinement, and (iii) a dedicated route-based crossover operator for solution recombination. Computational experiments performed on a large set of instances reveal the efficiency of the algorithm. Additionally, we demonstrate the relevance of our algorithm for the classic TRPP. The reported computational results serve as a benchmark for future researchers who wish to investigate the problem.