A composite algorithm for the team orienteering problem with time windows

In this paper we propose a new heuristic algorithm for the Team Orienteering Problem with Time Windows (TOPTW). This problem is applicable to several real life problems. The route planning of the vehicles which belong to a company or the tourist trip design problem, are some of them. In the first problem, each customer is associated with a profit which can be obtained after visiting them. The objective is to derive a constant number of routes visiting customers such that the profit obtained overall is the maximum possible given that some constraints are satisfied. Specifically, the total cost of transportation of each route must be less than or equal to a certain time budget. In addition, the visit to each customer must occur within a specific time interval. This time interval is termed time window and can be different for each customer. In this sort of problems, the budget may represent the available time for serving customers and the number of routes represents the number of vehicles. In the second problem, the tourist trip design problem, there are some Points of Interest (POIs) which represent tourist sites. Each site is also associated with a profit indicating the interest of a tourist in this attraction. Tourists are looking for a constant number of routes (itineraries) so as to maximize the total profit gained out of the visit of sites included in these itineraries. The time budget and time window constraints are also exist. TOPTW is a generalization of the Orienteering problem. Hence, TOPTW belongs to NP-hard problems. The Iterated Local Search and Average Slack are heuristics that have been proposed in the literature for TOPTW. The proposed heuristic combines the aforementioned heuristics and takes advantage of the best features of both algorithms for providing solutions of higher overall profit.