A Metaheuristic for the Bounded Single-Depot Multiple Traveling Repairmen Problem
DOI:
https://doi.org/10.31449/inf.v45i1.2814Abstract
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.References
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.
Downloads
Published
How to Cite
Issue
Section
License
I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.
I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.
In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.
I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal. The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.
Copyright © Slovenian Society Informatika
