An adaptive large neighborhood search approach for multiple traveling repairman problem with profits

摘要

The Multiple Traveling Repairman Problem with Profits (MTRPP) is a generalization of the Traveling Repairman Problem with Profits (TRPP) by considering multiple servers. In the MTRPP, each vertex is associated with a time-dependent profit. The objective of the MTRPP is to maximize the total profit collected by the servers. In this study, a mixed-integer linear programming model is developed for the MTRPP. To solve the problem, an adaptive large neighborhood search (ALNS) approach is proposed. The performance of the proposed ALNS is tested on a set of generated MTRPP instances as well as on the TRPP instances from the literature. The computational results reveal that the proposed ALNS is an effective and time efficient solution approach for the MTRPP. Especially, it has been observed that the developed ALNS has improved the best-known solutions for 36 out of 40 large-size TRPP instances. (C) 2019 Elsevier Ltd. All rights reserved.