# Efficient Metaheuristics for the Mixed Team Orienteering Problem with Time Windows
## 2 Related Work  
Although numerous research works concern the OP as well as many extensions and variants of the OP, only a very limited body of literature concerns the AOP, the MOP and their extensions. [PERSON] _et al._ in [4] use the AOP to model and solve the problem of planning cycle trips in the province of East Flanders. Their solution approach is based on a Greedy Randomized Adaptive Search Procedure (GRASP), while experimental results are based on instances generated from the East Flanders network. In [6] the cycle trip planning problem (CTPP) is introduced and studied. The CTPP is a variant of AOP considering no fixed starting point for the tour. [PERSON] _et al._ propose a formulation for the Team Orienteeering Arc Routing Problem (TOARP) [5], a variant of the extension of AOP to multiple tours where two types of arcs are considered: the arcs that have to be served (compulsory arcs), and the arcs that are associated with profit and may be served if beneficial (profitable arcs). Given a specific number of tours \(k\), the goal is to design \(k\) tours including the required arcs and a set of the profitable arcs which maximizes the total profit without exceeding the allowed duration of each tour. [PERSON] _et al._ study a relaxation of the polyhedron modelling of the problem and then develop a branch-and-cut algorithm. [PERSON] _et al._ in [7] propose a matheuristic approach for the TOARP. Experimental results show that the algorithm gives an average percentage error with respect to the optimal solution which is lower than 1%. The Undirected Capacitated Arc Routing Problem with Profits (UCARPP), the arc routing counterpart of the capacitated TOP, is considered in [8]. In this problem a profit and a nonnegative demand is associated with each arc and the objective is to determine a tour for each available vehicle in order to maximize the total collected profit, without violating the capacity and time limit constraints of each vehicle. A potential application of the UCARPP is the creation of personalized bicycle trips. An exact approach for solving the problem along with several heuristics has been proposed in [8]. The problem has also been studied by [PERSON] and [PERSON] in [9] who investigated a local search procedure. To the best of our knowledge, the research works mostly relevant to the MOP are the one-period Bus Touring Problem (BTP) introduced by [PERSON] and [PERSON] [10], the Outdoor Activity Tour Suggestion Problem (OATSP) introduced by [PERSON] _et al._[11], and the Most Attractive Cycle Tourist Path Problem (MACTPP) introduced by [PERSON] _et al._[12]. In the BTP, given a constraint on the total touring time, the objective is to select a subset of profitable nodes and arcs which maximize the total profit of the tour. In this problem, the profit of nodes and arcs which are visited multiple times is counted only once. In [10], a heuristic approach is employed to solve the BTP. In [11], an efficient heuristic solution to the OATSP is presented. This problem finds attractive closed paths in a transportation network, tailored to a specific outdoor activity such as hiking and mountain biking. The total path attractiveness is estimated as the sum of the average arc attractiveness and the profits of the nodes along the path. The objective is to find a closed path of maximal attractiveness given a target path's length and tolerance. Notice that the OATSP requires a target path's length instead of a maximal travel time required by the BTP; hence, this gives rise to a path length window constraint. In MACTPP [12], the objective is to construct a new bicycle route between two locations with maximum attractiveness, subject to budget and duration constraints. The problem models a real situation in Trebon, Czech Republic where local administrators face the problem of optimally investing scarce resources to set up a network of cycle tracks, exploiting existing trails or by reconstruction works. In this problem, arcs and nodes can be visited more than once, obtaining a decreasing profit after each visit.