Solving large-scale instances of the multiple traveling repairman problem with profits (MTRPP) poses a significant computational challenge with direct implications for logistics and emergency response. To address this challenge, this work introduces a multi-start hyper-heuristic with a greedy selection mechanism (MSHGSM), an approach specifically developed to solve large and complex MTRPP instances. The approach leverages a multi-start framework to ensure robust coverage of the solution space and a greedy selection mechanism to iteratively apply the most effective move from a pool of twelve low-level heuristics. This process is guided by an adaptive perturbation technique that strategically manages the trade-off between exploiting known solutions and exploring new possibilities. The performance of MSHGSM is validated through extensive experiments on established benchmarks, where it proves significantly superior to existing methods on large instances. MSHGSM not only improves the best-known solutions for 22 out of 30 large instances, but it also exhibits competitive computational efficiency. While other algorithms may be better suited for medium-sized problems, MSHGSM is demonstrably the most effective for solving large, complex MTRPP instances.

This paper presents a multi-start general variable neighborhood search approach (MS_GVNS) for solving the clustered traveling salesman problem with the d-relaxed priority rule (CTSP-d). In clustered traveling salesman problem, vertices excluding the starting vertex or depot, are divided into clusters based on their urgency levels and higher-urgency vertices must be visited before lower-urgency ones. This leads to inefficient travel costs. To address this, a d-relaxed priority rule is employed in CTSP-d to balance travel cost and urgency level by relaxing the urgency-oriented restriction to some extent. CTSP-d is NP -hard as it can be considered as a generalization of traveling salesman problem (TSP). The proposed MS_GVNS approach combines a variable neighborhood descent (VND) strategy utilizing five different neighborhoods with a shaking procedure to enhance the solution. The performance of the MS_GVNS is evaluated on 148 standard benchmark instances from literature. The computational results demonstrate the effectiveness of the proposed approach in generating high-quality solutions within reasonable computational times compared to the existing best approaches. Furthermore, the approach improves upon the best-known solution values on six large instances.

In this paper, we present two multi-start heuristic approaches to solve the clustered traveling salesman problem with d-relaxed priority rule (CTSP-d). In this problem, the nodes (except the starting node or depot) are partitioned into different clusters according to their urgency levels and higher urgency nodes must be visited prior to visiting lower urgency ones, but this could lead to severe inefficiency in travel costs. A rule, called d-relaxed priority rule, provides a trade-off between travel cost and urgency level by relaxing this urgency-oriented restriction to certain extent. This problem is NP-hard as it contains the very well-known traveling salesman problem as a special case. Our first approach is a hyper-heuristic approach that makes multiple starts and utilizes three levels of heuristics. At the top level, this hyper-heuristic approach makes use of two hyper-heuristic approaches as low level heuristics. These two hyper-heuristic approaches in turn use five elementary problem-specific heuristics as low level heuristics to generate a new solution from the current solution. Our second approach is a multi-start iterated local search approach where variable neighborhood descent (VND) is used as local search. VND uses five neighborhoods to improve the solution. Performance of the proposed approaches are experimentally analyzed on 148 standard benchmark instances available in the literature. Computational results on these benchmark instances show the effectiveness of the proposed approaches as they generate high-quality solutions in low computational times compared to the state-of-the-art approaches available in the literature. Our approaches improve the best-known solution values on 20 instances.

This paper addresses a recently introduced problem called traveling repairman problem with profits (TRPP). The problem can be regarded as a variation of the well-known traveling salesman problem, where a repairman does not need to visit all the nodes. In TRPP, each node is linked with a profit, which is time-dependent. The objective of TRPP is to maximize the total revenue obtained. Our approach uses a greedy randomized construction method to generate the initial solution. A hyper-heuristic approach with a greedy selection mechanism (HH-GREEDY) is used for iteratively improving the solution. TRPP instances available in literature are utilized to evaluate the effectiveness of the proposed approach. Our approach obtained solutions of quality comparable to the state-of-the-art approaches at a fraction of time needed by these approaches.

This paper is concerned with an interesting variant of the traveling salesman problem (TSP) called a profitable tour problem (PTP). Unlike TSP, in PTP there is no need to visit all the cities, and each city is associated with a profit which the salesman gets in case he visits that city. Like TSP, a travel cost is incurred in visiting a city that depends on the city visited last before visiting the city in consideration. The goal of the problem is to maximize the total profit minus total travel cost. In this paper, we have proposed three methods, viz. a multi-start hyper-heuristic (MSHH), a multi-start iterated local search (MS-ILS) and a multi-start general variable neighborhood search (MS-GVNS) to solve the PTP. MSHH uses eight different low level heuristics, whereas MS-ILS and MS-GVNS utilize variable neighborhood descent search over five different neighborhoods for local search. To evaluate the performance of the proposed approaches, a set of benchmark instances is generated based on the publicly available TSPLIB instances. Computational results on these instances show the effectiveness of our proposed approaches.