A memetic algorithm for the orienteering problem with hotel selection

• An extensive literature review is presented on node routing problems with intermediate facilities.
• 176 New and larger benchmark instances with known optimal solutions are created.
• A memetic algorithm is designed which improves the results presented in the literature.
• A sensitivity analysis on the critical characteristics of the OPHS is performed.

In this paper, a memetic algorithm is developed to solve the orienteering problem with hotel selection (OPHS). The algorithm consists of two levels: a genetic component mainly focuses on finding a good sequence of intermediate hotels, whereas six local search moves embedded in a variable neighborhood structure deal with the selection and sequencing of vertices between the hotels. A set of 176 new and larger benchmark instances of OPHS are created based on optimal solutions of regular orienteering problems. Our algorithm is applied on these new instances as well as on 224 benchmark instances from the literature. The results are compared with the known optimal solutions and with the only other existing algorithm for this problem. The results clearly show that our memetic algorithm outperforms the existing algorithm in terms of solution quality and computational time. A sensitivity analysis shows the significant impact of the number of possible sequences of hotels on the difficulty of an OPHS instance.