A General Variable Neighborhood Search Approach for the Clustered Traveling Salesman Problem with d-Relaxed Priority Rule

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 \(\mathcal{N}\mathcal{P}\) -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.