Metaheuristics for the Orienteering Problem with Hotel Selection

Imagine a tourist who wants to visit a large touristic region such as a part of a country or for instance, Europe in a couple of days. In this case, each day some of the possible attractions should be selected to visit and also an accommodation place should be chosen to stay each night. Obviously, the location of the accommodation has influence on which possible attractions can be visited during the day. In this thesis we have mathematically modeled this situation as a combinatorial optimization problem and used operational research techniques to solve it. The thesis is composed of two main parts. In the first part, the above mentioned situation is mathematically modeled as a new variant of the orienteering problem, namely the orienteering problem with hotel selection, and metaheuristics including a variable neighborhood search and a memetic algorithm are designed to solve this problem. In the second part, another variant of this problem, with time windows for the visited attractions, is addressed. This variant is significantly more complex to solve. This version of the problem is also mathematically modeled and a memetic algorithm as well as a two-stage heuristic are developed to deal with it. Since this is the first research to tackle this new variant of the orienteering problem, a large number of new instances with known optimal solutions for both mentioned versions of the problem are generated. The performance of the newly developed algorithms is evaluated by solving the benchmark instances. The experimental results show that the proposed algorithms obtain high quality solutions in acceptable computation times and can be applied in real applications.