A Guided Quantum Particle Swarm Optimization approach for the traveling repairman problem

This paper focuses on the Traveling Repairman Problem (TRP), an extension of the Traveling Salesman Problem (TSP), which has gained significant attention in various practical fields such as humanitarian logistics, machine scheduling, computer networking, and service-based distribution. Previous research on the TRP has primarily focused on exact and approximate algorithms, with limited attention given to heuristics. This paper introduces a new hybrid method called Guided Quantum Particle Swarm Optimization (GQPSO) to effectively solve the TRP. This GQPSO approach combines the Quantum Particle Swarm Optimization (QPSO) metaheuristic with the Guided Local Search (GLS) algorithm. We introduced several enhancements to improve the efficiency of QPSO when addressing the TRP: (ⅰ) The initialization phase of the QPSO algorithm is modified. (ⅱ) A guided local search method is integrated within QPSO and used as an intensification strategy for each position generated throughout the search process. (ⅲ) Several acceleration strategies are implemented to expedite the process of the local search procedure. Experimental results obtained on a collection of benchmark problems from the literature illustrate the performance of the proposed hybrid approach to the TRP. When compared to the existing best heuristic methods, our GQPSO approach provides optimal solutions for all small- and medium-sized instances and achieves best-known solutions for most of the large-sized instances. It demonstrates a high competitiveness against state-of-the-art algorithms, occasionally outperforming them, particularly on larger instances, and surpasses other approaches in both solution quality and computational efficiency. These experimental results provide additional validation of the effectiveness and robustness of GQPSO as a powerful alternative for solving the TRP.