In this paper, we present the orienteering problem with hotel selection (OPHS), an extension of the orienteering problem (OP). In the OPHS, a set of vertices with a score and a set of hotels are given. The goal is to determine a fixed number of connected trips that visits some vertices and maximizes the sum of the collected scores. Each trip is limited in length and should start and end in one of the hotels. We formulate the problem mathematically, explain the differences with related optimization problems and indicate what makes this problem inherently more difficult. We use a skewed variable neighborhood search that consists of a constructive initialization procedure and an improvement procedure. The algorithm is based on a neighborhood search operator designed specifically for the hotel selection part of this problem, as well as some typical neighborhoods for the regular OP. We generate a set of 155 benchmark instances of varying sizes with known optimal solutions. For 76 of these instances our algorithm finds the optimal solution, the average gap with the optimal solution over all these instances is only 1.71% and the average computation time is 0.3 s.
کلید واژگان :Orienteering problem, Hotel selection, Variable neighborhood search
ارزش ریالی : 600000 ریال
با پرداخت الکترونیک