Scientific Program > Talks by Speaker > Divsalar Ali

The Orienteering Problem with Hotel Selection and Time Windows (OPHSTW) is a recent variant of the Orienteering Problem (OP) in which a visiting tour starts in a given initial hotel and ends in a given final hotel. This tour is composed of a given number of trips, each limited by a time budget. Each trip starts and ends in one of the available hotels. Next to the hotels, a number of vertices with an assigned score can be visited within each trip respecting their time windows. The goal is to maximize the total score collected by visiting vertices in the tour. Various applications are considered for this problem such as tourist trip planning, military reconnaissance activity, and truck drivers with limited driving time. In this research, a Lagrange Relaxation (LR) method is implemented to 395 benchmark instances with known optimal solutions from the literature. In each iteration of the proposed LR method, a smart heuristic approach is used to tackle the sub-tour elimination constraints and obtain a feasible solution. The experimental results show that the solution method is able to improve the best known solution for larger instances of the problem.