# Efficient Metaheuristics for the Mixed Team Orienteering Problem with Time Windows
## 4 MTOPTW Algorithmic Approaches--Preprocessing Phase  
In the sequel, for the sake of simplicity and ease of the presentation of the algorithmic techniques, a different notation of graph edges is followed. Specifically, an edge \(e\) between two nodes \(u\) and \(v\) will be denoted by \(\{u,v\}\) hereafter. The same notation will be used for assigning direction of traversal to an edge. For instance, the notation \(\{v,u\}\) will denote the traversal of the edge in the direction from \(v\) to \(u\). In case of two edges between the nodes \(u\), \(v\) (one representing a scenic route and the other the shortest path connection), the notation \(\{u,v\}\) will be used for representing either one of the two edges. To distinguish them, we will call an edge \(\{u,v\}\) of the input graph with \(P_{u,v}>0\) which models a scenic route, as _profitable edge_. Similarly, we will call a node \(u\) of the input graph with \(P_{u}>0\) which models a POI, as _profitable node_. With regard to the algorithmic approaches for solving MTOPTW, we propose two metaheuristic approaches, namely an Iterated Local Search approach inspired by the one presented by [PERSON] _et al._vansteenwegen _et al._ (2017) for the TOPTW, and a Simulated Annealing approach. Among other operations, both these approaches repeatedly execute local-search steps. At each of these steps, the neighborhood of the current solution is examined in search of higher profit feasible solutions. Thus, it is important to keep the size of this neighborhood relatively small in order that each local search step can be executed fast. For that reason, the input graph \(G\) should satisfy the following requirements:  
* for each profitable node \(u\) of \(G\) there is no profitable edge incident to \(u\), _i.e._, there is no \(v\) such that \(P_{u,v}>0\), and
* for each profitable edge \(\{u,v\}\) of \(G\) there is no other profitable edge incident to \(u\) or \(v\), _i.e._, there is no node \(w\) such that \(P_{u,w}>0\) or \(P_{w,v}>0\). In the case that \(G\) does not satisfy the above requirements then, in a preprocessing phase, \(G\) is transformed to a new graph \(G^{\prime}\) that satisfies them. This is done in a way that any solution in \(G^{\prime}\) can be easily transformed to an equivalent solution of the same profit in \(G\). Specifically, the transformation first separates all profitable nodes from adjacent profitable edges as follows. For each profitable node \(u\) of the input graph which is connected to at least one profitable edge, we introduce a dummy node \(u^{\prime}\) and a dummy edge \(\{u^{\prime},u\}\) with \(P_{u^{\prime}}=0\), \(T_{u^{\prime}}=0\), \((O^{k}_{u^{\prime},},C^{k}_{u^{\prime}})=(st_{k},et_{k})\) (\(k\in[K]\)) and \(P_{u^{\prime},u}=P_{u,u^{\prime}}=0\), \(T_{u^{\prime},u}=T_{u,u^{\prime}}=0\), \((O^{k}_{u,u^{\prime}},C^{k}_{u,u^{\prime}})=(O^{k}_{u^{\prime},u^{\prime}},C^{ k}_{u^{\prime},u})=(st_{k},et_{k})\) (\(k\in[K]\)). Then, each profitable edge incident to \(u\) in \(G\) is connected to the dummy node \(u^{\prime}\) in \(G^{\prime}\) while each non-profitable edge incident to \(u\) in \(G\) remains connected to \(u\) in \(G^{\prime}\). As an example, Figure 0(a) shows a graph \(G\) with a profitable node \(u\) with two profitable and two non profitable incident edges, while Figure 0(b) shows the corresponding new graph \(G^{\prime}\). Next, all profitable edges incident to the same node are \"separated\" by inserting a corresponding number of dummy nodes and edges whose profit and time attributes are set as above. As an example, Figure 0(c) shows a graph \(G\) with three profitable edges incident to the same node \(u\), while Figure 0(d) shows the corresponding new graph \(G^{\prime}\) which includes three dummy nodes and three dummy edges.