Opposition-Based Variable Neighborhood Descent Algorithm for the Traveling Salesperson Problem with Hotel Selection

Abstract

In this study, The Traveling Salesperson Problem with Hotel Selection (TSPHS) is considered. TSPHS includes daily working time/distance restrictions. This constraint does not allow visiting all points at once. For this reason, the traveler stops (roosts) at a suitable waiting point (hotel) at the end of the day and continues the next day's trip from the point (hotel) where he stayed. There is no obligation to visit each hotel, and a hotel can be visited more than once. A set of ordered nodes starting and ending at a hotel is called a trip, and a set of ordered trips covering all nodes is called a tour. The primary objective of the problem is to minimize the number of trips. The secondary objective is to minimize the total distance of the tour, provided that the time/distance per trip does not exceed the daily working time limit. Since this problem belongs to the NP-hard problem class, the use of the heuristic method has an advantage in terms of the solution time. In our solution approach, the initial solution is obtained using The Nearest Neighbor Algorithm (NN). To improve this solution, the Opposition-Based Variable Neighborhood Descent (OBVND) is used. The performance of the algorithm is evaluated on the test problems in the literature using various criteria. The results are compared with the best solutions available in the literature. The overall results show us that the proposed OBVND approach can find better quality solutions in 2 out of 16 problems in the Set 1 data; in 24 out of 52 problems in the Set 2 data; and in 9 out of 38 problems in Set 3 data.