Time dependent orienteering problem with time windows and service time dependent profits

• New OP variant with service time dependent profits and time dependent travel times. • Mathematical formulation and possible applications of this problem. • Metaheuristic solution approach composed of specific local moves. • Benchmark instances with known optimal solutions to verify the solution approach. • Real data instance to evaluate the proposed model and solution method. This paper addresses the time dependent orienteering problem with time windows and service time dependent profits (TDOPTW-STP). In the TDOPTW-STP, each vertex is assigned a minimum and a maximum service time and the profit collected at each vertex increases linearly with the service time. The goal is to maximize the total collected profit by determining a subset of vertices to be visited and assigning appropriate service time to each vertex, considering a given time budget and time windows. Moreover, travel times are dependent of the departure times. To solve this problem, a mixed integer linear model is formulated and a metaheuristic algorithm based on variable neighborhood search (VNS) is developed. This algorithm uses three specifically designed neighborhood structures able to deal with the variable service times and profits of vertices. Extensive computational experiments are conducted on test instances adapted from the TDOPTW benchmarks, to validate the performance of our solution approach. Furthermore, a real instance for the city of Shiraz (Iran) is generated. Experimental results demonstrate the suitability of the TDOPTW-STP in practice, and demonstrate that the proposed algorithm is able to obtain high-quality solutions in real-time. Sensitivity analyses clearly show the significant impact of the service time dependent profits on the route plan, especially in the presence of travel time dependency and time windows.