# Efficient Metaheuristics for the Mixed Team Orienteering Problem with Time Windows
###### Abstract  
Given a graph whose nodes and edges are associated with a profit, a visiting (or traversing) time and an admittance time window, the Mixed Team Orienteering Problem with Time Windows (MTOPTW) seeks for a specific number of walks spanning a subset of nodes and edges of the graph so as to maximize the overall collected profit. The visit of the included nodes and edges should take place within their respective time window and the overall duration of each walk should be below a certain threshold. In this paper we introduce the MTOPTW, which can be used for modeling a realistic variant of the Tourist Trip Design Problem where the objective is the derivation of near-optimal multiple-day itineraries for tourists visiting a destination which features several points of interest (POIs) and scenic routes. Since the MTOPTW is a NP-hard problem, we propose the first metaheuristic approaches to tackle it. The effectiveness of our algorithms is validated through a number of experiments on POI and scenic route sets compiled from the city of Athens (Greece). Iterated Local Search; Simulated Annealing; Team Orienteering Problem; Arc Orienteering Problem +
Footnote †: journal:  
0000-000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-0000-00000-00000-00000-00000-00000-00000-00000-00000-00000-  
The Orienteering Problem (OP), an NP-hard problem introduced in [2], has been used in the literature as the baseline optimization problem for modeling the TTDP. The OP seeks for a route which starts and ends at fixed locations and maximizes the total collected profit while maintaining the travel cost under a given value. This definition also includes the case of a cyclic route by simply selecting as a start and destination the same location. Clearly, the OP may be used to model the simplest version of the TTDP wherein the POIs are associated with a profit (_i.e._, a degree of user satisfaction) and the goal is to find a single tourist itinerary that starts and ends at fixed locations and maximizes the profit collected within a given time budget (time allowed for sightseeing in a single day). Extensions of the OP have been successfully applied to model more complex versions of the single itinerary TTDP [1; 3]. The OP with Time Windows (OPTW) considers visits at locations within a predefined time window; this allows modeling opening days/hours of POIs. The Time-Dependent OP (TDOP) considers time dependency in the estimation of time required to move from one location to another and therefore, it is suitable for modeling multi-modal transports among POIs. The Team Orienteering Problem (TOP) is the extension of the OP to multiple routes. The TOP with Time Windows (TOPTW) and the Time-Dependent TOPTW (TDTOPTW) have been used to model different versions of the multiple itinerary TTDP. The Arc Orienteering Problem (AOP), introduced by [PERSON] _et al._ in [4], is the arc routing version of the OP and is applicable to TTDP variants whose modeling involves profits associated with the arcs (rather than the nodes) of the network as some links may be more attractive than others. As an example, consider the problem of deriving personalized bicycle trips. Based on the biker's personal interests, starting and ending point and the available time budget, a personalized trip can be composed using arcs that better match the cyclist's profile (for instance, arc values could indicate the scenic value or the gradient of a route segment). The extension of the AOP to multiple routes, introduced by [PERSON] _et al._ in [5] and named as Team Orienteering Arc Routing Problem (TOARP), may also find applications to the TTDP. The combination of the OP and the AOP is proposed in [3] under the name Mixed Orienteering Problem (MOP). In the MOP, profits are associated with the nodes as well as with the arcs of the graph. The problem can be used to formulate TTDP variants wherein, further to typical attractions, certain routes may be of tourist interest.