# Efficient Metaheuristics for the Mixed Team Orienteering Problem with Time Windows
## 3 Problem Definition
The other possibility is that the walk _passes_ by the node on the way to the next scenic route or POI. In this case, there is no profit from this node and the delay \(T_{u}\) is not incurred. Also, an integer \(K\) is given denoting the number of the walks that will be constructed. Now, each node or edge \(x\) is associated with \(K\) time windows \([O^{i}_{x},C^{i}_{x}]\) (\(i=1,\ldots,K\)) where \(O^{i}_{x}\) is the opening time and \(C^{i}_{x}\) is the closing time of the \(i^{th}\) time window of node or edge \(x\). The visit at a node (or the traversal of an edge) can only take place within one its time windows. However, for just passing by a node, this condition does not apply. Also, for each walk \(W_{i}\) (\(i=0,\ldots,K-1\)) a starting node \(sl_{i}\) and an ending node \(el_{i}\) are given (\(sl_{i},el_{i}\in V\)), as well as a starting time \(st_{i}\) and an ending time \(et_{i}\). An implicit assumption here is that for each node or edge \(x\), only one its time windows may be \"active\" during a walk, namely, for each walk \(W_{i}\), \([O^{i}_{x},C^{i}_{x}]\cap[st_{i},et_{i}]=\emptyset\) where \(i,j=1,\ldots,K\) with \(i\
eq j\). This is a reasonable assumption considering the common scenario where each walk \(W_{i}\) takes place on different day and \([O^{i}_{x},C^{i}_{x}]\) is the interval in that day during which the route or POI is open. A feasible solution of the MTOPTW consists of \(K\) walks \(W_{0},W_{1},\ldots,W_{K-1}\) with \(W_{i}=(w^{i}_{0},w^{i}_{1},\ldots,w^{i}_{i-1})\) such that \(w^{i}_{0}=sl_{i}\), \(w^{i}_{i-1}=el_{i}\), the arrival time at \(sl_{i}\) equals to \(st_{i}\) and the arrival time at \(el_{i}\) is at most \(et_{i}\). For each edge of the walk \(\{w^{i}_{m},w^{i}_{m+1}\}\), its traversal should take place within its time window. The same holds for all nodes \(w^{i}_{m}\) which are actually visited and not just passed by. The profit of the solution is equal to the sum of the profits of the visited nodes and the traversed edges. The goal of the MTOPTW is to construct the feasible solution of the highest profit. As has been mentioned above, if an edge appears (_i.e._, is traversed) more than once in a solution, its profit is counted only once (independently of the direction of the traversal) while the travel cost is charged as many times as it is traversed. The facts that (i) there is no profit gain when revisiting an edge and (ii) there exists a shortest path edge between any two nodes in the graph which obeys the triangle inequality, imply that each edge needs to be traversed at most once in the optimal solution. Likewise, we assume that the no additional profit is gained after the first visit of a node. Thus, it can be easily seen that there is an optimal solution which visits each node at most once due to the aforementioned fact that no additional profit is gained from multiple visits. However, a node may appear more than once in a solution, _i.e._, as an endpoint of its incident edges which are traversed in the solution. In all these occurrences, the node is only passed by and not visited. The MTOPTW can be formulated as a mixed integer programming problem. We use the following variables:  
* \(y^{k}(e^{d})\): a binary variable whose value is \(1\) if the edge \(e\) is traversed in the direction \(d\) (\(\in\{+,-\}\) ) in the walk \(W_{k}\), and \(0\), otherwise, for \(k=0,\ldots,K-1\). * \(z^{k}_{u}\): a binary variable which takes value \(1\) if the node \(u\) is visited in the walk \(W_{k}\), \(k=0,\cdots,K-1\), and \(0\) otherwise. * \(p^{k}(e^{d})\): a binary variable which is equal to \(1\) if, the traversal of the edge \(e\) along \(W_{k}\) is done in the direction \(d\in\{+,-\}\) immediately before the visit at the node \(h(e^{d})\). Otherwise, \(p^{k}(e^{d})=0\). For instance, \(p^{k}(e^{d})=0\) in the case that the edge \(e\) is traversed in direction \(d\) (\(y^{k}(e^{d})=1\)) but the head of the edge \(h(e^{d})\) is only passed by.