A GRASP+VND Algorithm for the Multiple Traveling Repairman Problem with Distance Constraints

Ban Ha Bang


Multiple Traveling Repairman Problem (MTRP) is a class of NP-hard combinatorial optimization problems. In this paper, an other variant of MTRP, also known as Multiple Traveling Repairman Problem with Distance Constraint (MTRPD) is introduced. In MTRPD problem, a fleet of vehicles serve a set of customers. Each vehicle that starts from the depot is not allowed to travel a distance longer than a limit and each customer must be visited exactly once. The goal is to find the order of customer visits that minimizes the sum of waiting time. To the best of our knowledge, the problem has not been studied much previously, even though it is a natural and practical extension of the Traveling Repairman Problem or Multiple Traveling Repairman Problem case. In our work, we propose a metaheuristic algorithm which is mainly based on the principles of Greedy Randomized Adaptive Search Procedure (GRASP) and Variable Neighborhood Descent (VND) to solve the problem. The GRASP is used to build an initial solution which is good enough in construction phase. In a cooperative way, the VND is employed to generate diverse neighborhoods in improvement phase, therefore, it can prevent the search to escape from local optimal. Extensive numerical experiments on benchmark instances show that our algorithm can find the optimal solutions with up to 50 vertices in several instances. For larger instances, our algorithm obtains provably near-optimal solutions, even for large instances.


Multiple Traveling Repairman Problem with Distance Constraints (MTRPD), GRASP, VND, metaheuristic

Full Text:


DOI: https://doi.org/10.15625/1813-9663/33/3/10511 Display counter: Abstract : 248 views. PDF : 123 views.

Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology