# Efficient Metaheuristics for the Mixed Team Orienteering Problem with Time Windows
## 3 Problem Definition
Constraints (2) and (3) ensure that the walk \(W_{k}\) starts at node \(sl_{k}\) and ends at node \(el_{k}\) for \(k=0,\cdots K-1\). We also take into account that there may be multiple traversals through \(sl_{k}\) and \(el_{k}\) along the same walk. Constraints (4) are flow conservation constraints while Constraints (5) ensure that each edge is traversed at most once in total for both traversal directions. As has been mentioned before, the optimal solution needs to traverse each edge only once and hence these constraints are surely satisfied by such a solution. If those constraints were omitted, then an optimal solution could have been derived with even higher profit. However, this better solution may traverse an edge two times, once in each direction, getting the edge profit twice. Thus, the obtained solution would not be a valid solution in our problem setting. Regarding Constraints (6), these constraints guarantee that each node is visited at most once, in total. Constraints (7) necessitate the visit at the endpoints \(sl_{k}\) and \(el_{k}\). The visit of \(sl_{k}\) takes place at the moment of departure from \(sl_{k}\) (Constraints (23)). Similarly, the visit of \(el_{k}\) is at the end of the walk \(W_{k}\) and before time \(et_{k}\) (Constraints (24)). Constraints (8)-(15) ensure that the values of variables \(p^{k}(e^{d})\), \(q^{k}(e^{d})\), \(r^{k}(e^{d},e^{\prime d^{\prime}})\) are consistent with those of variables \(y^{k}(e^{d})\) and \(z_{u}^{k}\). Specifically, Constraints (8) combined with the Constraint (7) reflect the fact that the walk \(W_{k}\) starts with the visit of \(sl_{k}\). Thus, there cannot be preceding edges in \(W_{k}\) leading to that particular node. A symmetric condition is described in the Constraints (9). Constraints (10) and (11) ensure that the variables \(p^{k}(e^{d})\), \(q^{k}(e^{d})\) cannot have value 1 if the edge \(e\) has not been traversed in the direction \(d\) along the walk \(W_{k}\). Constraints (12) ensure that for each visited node \(u\) along \(W_{k}\) except the node \(sl_{k}\), only one of the edges leading to \(u\) has been traversed along \(W_{k}\) and indeed just before the visit of that node. Symmetrically, Constraints (13) guarantee that for each visited node \(u\) along \(W_{k}\) except the node \(el_{k}\), only one of the edges starting from \(u\) has been traversed along \(W_{k}\), immediately after the visit of that node. Constraints (14) reflect the fact that when an edge \(e\) is traversed along the walk \(W_{k}\) (\(y^{k}(e^{d})=1\)), one of the two mutually exclusive possibilities can occur before this traversal: either the tail node of \(e\) has been visited (\(q^{k}(e^{d})=1\)) and thus all \(r\)-variables are zero or that visit did not take place (\(q^{k}(e^{d})=0\)) and thus only one of the \(r\)-variables is 1, that corresponding to the edge \(e^{\prime}\) traversed just before \(e\) in the walk \(W_{k}\). In case that the edge \(e\) is not traversed, (\(y^{k}(e^{d})=0\)), all variables in these constraints are forced to be 0. Constraints (15) have a similar explanation and determine what is possible after the traversal of an edge. Constraints (16)-(18) ensure that the sequence of starting times of node visits and edge traversals along a walk is feasible. For instance, Constraints (16) ensure that the visit at a node along a walk can start only after the edge which is just before that node on the walk (\(p^{k}(e^{d})=1\)) has been traversed. Constraints (19) and (20) indicate that the start of a visit at a node can only take place during its time window. Similarly, Constraints (21) and (22) ensure that the edge traversal can only take place during its time window. Finally, Equations (23) and (24) require that the walk \(W_{k}\) should start at time \(st_{k}\) and be completed no later than \(et_{k}\). As has already been mentioned, the MTOPTW problem is a NP-hard problem which models the core task of suggesting interesting itineraries for tourists.