A GRASP with iterated local search for the traveling repairman problem with profits

- The traveling repairman problem with profits is addressed.
- A new mixed-integer linear model is developed for the problem.
- A simple metaheuristic algorithm is developed for its solution.
- The algorithm integrates GRASP with ILS.
- 46 best results are improved for the TRPP instances.

Traveling Repairman Problem with profits (TRPP) is an extension of the Traveling Repairman Problem (TRP), where there is not an obligation to visit all vertices. A time-dependent profit is associated with each vertex and the objective is to maximize the total collected revenue. In this paper, we initially develop a new mixed-integer linear model capable of solving small size instances for the TRPP. To solve medium and large size instances, a simple and effective metaheuristic algorithm (GRASP-ILS) is introduced for the TRPP, which combines Greedy Randomized Adaptive Search Procedure (GRASP) for initial solution construction and Iterated Local Search (ILS) with an adaptive perturbation mechanism for solution improvement. The proposed GRASP-ILS is tested on the TRPP benchmark instances derived from the literature. The results indicate that the developed GRASP-ILS can produce efficient and effective solutions for the TRPP. Particularly, it has been observed that the developed GRASP-ILS has improved the best solutions for 46 instances and obtained all the best known results for the remaining instances in a reasonable computation time.