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

Ban Ha Bang


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.

Full Text:



bibitem{bib01} A. Archer, A. Levin, and D. Williamson, ``A Faster, Better Approximation Algorithm For The Minimum Latency Problem", J. SIAM, Vol. 37, No. 1, 2007, pp. 1472-1498.

bibitem{bib02} F. Afrati, S. Cosmadakis, C. Papadimitriou, G. Papageorgiou, and N. Papakostantinou, ``The Complexity Of The Travelling Repairmen Problem", J. Informatique Theorique Et Applications, Vol. 20, pp.79–87.

bibitem{bib03} A. Blum, P. Chalasani, D. Coppersmith, W. Pulleyblank, P. Raghavan, and M. Sudan, ``The Minimum Latency Problem", Proc. STOC, 1994, pp.163-171.

bibitem{bib04} I. O. Ezzine, and Sonda Elloumi, ``Polynomial Formulation and Heuristic Based Approach For The k-Travelling Repairmen Problem", Int. J. Mathematics In Operational Research, Vol. 4, No. 5, 2012, pp. 503-514.

bibitem{bib05} T.A. Feo, and M.G.C. Resende, ``Greedy Randomized Adaptive Search Procedures", J. Global Opt., 1995, pp. 109–133.

bibitem{bib06} F. Jittat, C. Harrelson, and S. Rao, ``The k-Traveling Repairmen Problem", Proc. ACM-SIAM, 2003, pp.655-664.

bibitem{bib07} D. S. Johnson, and L. A. Mcgeoch, ``The Traveling Salesman Problem: A Case Study In Local Optimization In Local Search In Combinatorial Optimization", E. Aarts and J. K. Lenstra, Eds., pp. 215-310.

bibitem{bib08} R. Jothi, and B. Raghavachari, ``Minimum Latency Tours and The k-Traveling Repairmen Problem", Proc. LATIN, 2004, pp. 423–433.

bibitem{bib09} O. Martin, S. W. Otto, and E. W. Felten, ``Large-Step Markov Chains For The Traveling Salesman Problem", J. Complex Systems, Vol. 5, No. 3, 1991, pp. 299-326.

bibitem{bib10} N. Mladenovic, and P. Hansen, ``Variable Neighborhood Search", J. Operations Research, Vol.24, No. 11 24, 1997, pp.1097-1100.

bibitem{bib11} R. Necula, M. Breaban, M. Raschip, ``Performance Evaluation of Ant Colony Systems for the Single-Depot Multiple Traveling Salesman Problem", Proc. HAIS, vol. 9121, pp. 257-268, 2015.

bibitem{bib12} S. Nucamendi-Guillén, I. Martínez-Salazar, F. Angel-Bello, and J. M. Moreno-Vega, ``A Mixed Integer Formulation and An Efficient Metaheuristic Procedure For The K-Travelling Repairmen Problem", J. JORS, Vol. 67, No. 8, 2016, pp. 1121-1134.

bibitem{bib13} M. Silva, A. Subramanian, T. Vidal, and L. Ochi, ``A simple and effective metaheuristic for the Minimum Latency Problem", J. Operations Research, Vol 221, No. 3, 2012, pp.513-520.

DOI: https://doi.org/10.31449/inf.v45i1.2814

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.