An effective hybrid search algorithm for the multiple traveling repairman problem with profits
This work addresses a combinatorial optimization problem relevant to logistics and routing, offering incremental improvements in solution quality for specific benchmark instances.
The paper tackled the multiple traveling repairman problem with profits by proposing a hybrid search algorithm based on a memetic framework, achieving new best records for 137 out of 470 benchmark instances and matching results for 330 others.
As an extension of the traveling repairman problem with profits, the multiple traveling repairman problem with profits consists of multiple repairmen who visit a subset of all customers to maximize the revenues collected through the visited customers. To solve this challenging problem, an effective hybrid search algorithm based on the memetic algorithm framework is proposed. It integrates two distinguished features: a dedicated arc-based crossover to generate high-quality offspring solutions and a fast evaluation technique to reduce the complexity of exploring the classical neighborhoods. We show the competitiveness of the algorithm on 470 benchmark instances compared to the leading reference algorithms and report new best records for 137 instances as well as equal best results for other 330 instances. We investigate the importance of the key search components for the algorithm.