# Efficient Metaheuristics for the Mixed Team Orienteering Problem with Time Windows
## 3 Problem Definition  
The MTOPTW formulates realistic TTDP variants where multiple tourist itineraries should be determined. Also, profits are associated to POIs (nodes of the network) as well as to routes (edges of the network) as certain routes may be more interesting for traversal than others. In addition, the POIs are associated with visiting times and visiting time windows. Similarly, the routes are associated with traversing times and traversing time windows. To formally define the problem we need to employ windy graphs. We define the MTOPTW on windy multigraphs (A multigraph is a graph where for each pair of nodes there could be more than one edges connecting these nodes.) as follows: Let \(G=(V,E)\) be a windy multigraph where \(V=\{u_{1},u_{2},\ldots,u_{N}\}\) denotes the node set and \(E\) the edge set. Each edge \(e\) can be _traversed_ in two directions and let \(e^{+}\) and \(e^{-}\) be the corresponding directions. The head and the tail of each direction \(e^{d}\) (\(d\in\{+,-\}\)) will be denoted by \(h(e^{d})\) and \(t(e^{d})\), respectively. The edge set \(E\) is partitioned into two sets, \(E^{\prime}\) and \(E^{\prime\prime}\) (\(E=E^{\prime}\cup E^{\prime\prime}\)), defined as follows:  
* The set \(E^{\prime}\) contains an edge for any pair of nodes in \(V\) representing the shortest path connection between these nodes. Specifically, for each pair of nodes \(u_{i}\) and \(u_{j}\) in \(V\), the set \(E^{\prime}\) contains an edge \(e\) which connects the two nodes and represents the shortest path route connecting these two nodes in the city road network. The time required for traversing the edge \(e\) in the direction from \(u_{i}\) to \(u_{j}\) may be different from the travelling time in the opposite direction; thus, we use the notations \(T(e^{+})\) and \(T(e^{-})\) for the different travelling times in the two directions (This clearly implies that the shortest path routes may be different between two nodes in the two opposite directions.). Clearly, all these time costs obey the triangle inequality, for instance, it holds that \(T(e^{d})\leq T(e_{1}^{d})+T(e_{2}^{d})\) where \(t(e^{d})=t(e_{1}^{d})\), \(h(e^{d})=h(e_{2}^{d})\), \(h(e_{1}^{d})=t(e_{2}^{d})\) for \(d\in\{+,-\}\). Essentially, each edge \(e\) in \(E^{\prime}\) is used solely for moving between interesting sites in the city (either POI or scenic route) and thus traversing such an edge does not yield any profit. Therefore, each edge \(e\) in \(E^{\prime}\) is associated with profit equal to zero (\(P_{e}=0\)). * The set \(E^{\prime\prime}\) contains all the edges modelling the scenic routes. Specifically, if there is a scenic route between nodes \(u_{i}\) and \(u_{j}\) then there is an edge \(e\in E^{\prime\prime}\) connecting these nodes. Each edge in \(E^{\prime\prime}\) can be traversed in both directions and \(T(e^{d})\) is again the traversal time in direction \(d\) for \(d\in\{+,-\}\). Note that the scenic route is not necessarily the shortest one between \(u_{i}\) and \(u_{j}\) and thus the travelling time \(T(e^{d})\) may not obey the triangle inequality property. Each edge \(e\) in \(E^{\prime\prime}\) is associated with a profit, \(P_{e}\), which is a measure of the attractiveness of the scenic route. Overall, between any two nodes in \(G\), there will be at most two edges connecting them, one being the shortest path route and the other being the scenic route (if exists). In case that the scenic route is also the shortest one between two nodes, the two edges are maintained although they actually represent the same route in the road network. This redundancy greatly facilitates the integer programming formulation of the problem which follows. It is also worth mentioning that \(G(V,E^{\prime})\) is a complete graph while \(G(V,E^{\prime\prime})\) may be not. For each node \(u\in V\), there are two possibilities. First, the node can be _visited_ in a walk with \(T_{u}\) being the visit duration and \(P_{u}\) being a non-negative number denoting the profit gained from that visit.