A Metaheuristic for the Bounded Single-Depot Multiple Traveling Repairmen Problem

Abstract

Multiple Traveling Repairmen Problem (mTRP) is a class of NP-hard combinatorial optimization problems which has many practical applications. In this paper, a general variant of mTRP, also known as Bounded Single-Depot Multiple Traveling Repairmen Problem (Bounded-mTRP) is introduced. In Bounded-mTRP problem, fleet of identical vehicles is dispatched to serve a set of customers. Each vehicle that starts from the depot is only allowed to visit the number of customers within a predetermined interval and each customer must be visited exactly once. Such restrictions appear in real-life applications where the purpose is to have a good balance of workloads for the repairmen. The goal is to find the order of customer visits that minimizes the sum of waiting times. 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 Search (VNS) to solve the problem. GRASP is used to build an initial solution in a construction phase. In a cooperative way, VNS is employed to generate various neighborhoods in an improvement phase, therefore, it can prevent the search to escape from local optimal. In addition, we also introduce a new novel neighborhoods' structure in VNS for the problem. Extensive numerical experiments on benchmark instances show that our algorithm can reach the optimal solutions for the problems with 50 vertices in a reasonable amount of time. Moreover, the new best known solutions can be found in comparison with the state-of-the-art metaheuristic algorithms.