Opposition-based variable neighborhood descent algorithm for the travelling salesperson problem with hotel selection

In this dissertation, The Travelling Salesperson Problem with Hotel Selection (TSPHS), which is a variant of The Travelling Salesperson Problem (TSP), is considered. TSP consist of a salesman and set of nodes known distances between them. The salesman has to visit each one of the nodes starting from a certain one and returning to the same node. The goal is to have the least cost tour during the salesman's trip. TSPHS includes daily working time / distance restriction. This constraint does not allow to visit all points at once. For this reason, the traveler stops (roosts) at a suitable waiting (hotel) point at the end of the day (limited working time / distance) and continues on the next day's trip from the hotel point 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. In the dissertation, an algorithm based on Variable Neighborhood Descent algorithm is developed for the solution of this problem. The starting solution with The Nearest Neighbor Principle (NNP) is obtained. Opposition Based Variable Neighborhood Descent (OBVND) Algorithm is applied to improve this solution. The results are compared with the other heuristic algorithms in the literature. As a result of the analysis, better results are obtained in 35 of 120 problem. In addition, the results are compared with those obtained with Cplex solvent, which is also available in the literature. In 17 of 78 problems, either optimal results are obtained or better results are obtained than the best known results.