The Multi-stripe Travelling Salesman Problem (Ms-TSP) is an extension of the Travelling Salesman Problem (TSP). In the q-stripe TSP with q ≥ 1, the objective function sums the costs for traveling from one vertex to each of the next q vertices along the tour. To solve medium to large-sized instances, a metaheuristic approach is proposed. The proposed method has two main components, which are construction and improvement phases. The construction phase generates an initial solution using the Greedy Randomized Adaptive Search Procedure (GRASP). In contrast, the optimization phase improves it with several variants of Variable Neighborhood Search (VNS), both coupled with a technique called Shaking Technique to escape from local optima. Besides, the Adaptive Memory (AM) technique is applied to balance between diversification and intensification. To show the efficiency of our proposed metaheuristic algorithms, we extensively implement them on benchmark instances. The results indicate that the developed algorithms can produce efficient and effective solutions at a reasonable computation time. |
