## 3 DTSPN Intersecting Regions Algorithm
### Stage 1  
We begin by restating the problem above in a compact manor to facilitate the discussion. Problem \((P0)\) is a GTSP defined by the graph \(\mathcal{G}^{0}:=(\mathcal{N}^{0},\mathcal{A}^{0},\mathcal{V}^{0})\) with the corresponding cost vector \(c^{0}\). An example of Problem (P0) is shown in Figure 1(b). The first stage converts the GTSP \((P0)\) to a new problem \((P1)\) which is a GTSP with mutually exclusive node sets. This is done by first eliminating any arcs from \(\mathcal{A}^{0}\) that do not enter at least one new node set. Problem \((P1)\) is a GTSP defined by the graph \(\mathcal{G}^{1}:=(\mathcal{N}^{1},\mathcal{A}^{1},\mathcal{V}^{1})\) with the corresponding cost vector \(c^{1}\). Where \(\mathcal{N}^{1}=\mathcal{N}^{0}\), and \(\mathcal{V}^{1}=\mathcal{V}^{0}\). The arc set \(\mathcal{A}^{1}\) is formed by first setting \(\mathcal{A}^{1}=\mathcal{A}^{0}\), and then removing any edges that do not enter at least one new node set. Let \(\mathcal{M}(i)\) denote the set of node sets of which node \(i\) is a member, _i.e._, if \(i\in\mathcal{V}_{k}\), then \(k\in\mathcal{M}(i)\). For every \((i,j)\in\mathcal{A}^{0}\), if \(\mathcal{M}(j)\subset\mathcal{M}(i)\), then remove the arc \((i,j)\) from set \(\mathcal{A}^{1}\), see Figure 2(a). Figure 1: Example DTSPN with the corresponding “GTSP with intersecting node sets”. (**a**) Example instance of DTSPN with three circular regions \(\mathcal{R}_{1},\mathcal{R}_{2},\text{ and }\mathcal{R}_{3}\) and samples \(S_{1},S_{2},\dots,S_{8}\). The circuit through samples \(S_{2},\text{ and },S_{8}\) is the optimal tour; (**b**) Problem (P0): A GTSP with intersecting node sets representation of the DTSPN example. Note: only an essential subset of arcs is shown for clarity of illustration. Next, a constant is added to the cost of each arc entering a new node set. Problem \((P2)\) is a GTSP defined by the graph \(\mathcal{G}^{2}:=(\mathcal{N}^{2},\mathcal{A}^{2},\mathcal{V}^{2})\) with the corresponding cost vector \(c^{2}\). Where \(\mathcal{N}^{2}=\mathcal{N}^{1}\), \(\mathcal{A}^{2}=\mathcal{A}^{1}\), and \(\mathcal{V}^{1}=\mathcal{V}^{0}\). Notice that all arc costs are nonnegative. We now define a finite, positive constant \(\alpha\) as,  
\[\infty>\alpha\geq\sum_{(i,j)\in\mathcal{A}^{1}}c^{1}_{i,j} \tag{3}\]  
For every arc \((i,j)\in\mathcal{A}^{1}\), set the cost of the arc \((i,j)\in\mathcal{A}^{2}\) in the following manner,  
\[c^{2}_{i,j}=(|\mathcal{M}(j)-\{\mathcal{M}(i)\cap\mathcal{M}(j)\}|)\alpha+c^{ 1}_{i,j} \tag{4}\]  
Here \(|Z|\), represents the cardinality of the set \(Z\). Notice that Equation (4) adds to the original arc cost an additional cost of \(\alpha\) for each new node set entered by arc \((i,j)\). An example of Problem (P2) can be seen in Figure 2(b), where \(\hat{c}_{i,j}\) represents \(c^{2}_{i,j}\). Next, any nodes that belong to more than one node set are duplicated and placed in different node sets so as to allow each node to have membership in only one node set. Problem \((P3)\) is a GTSP over the graph \(\mathcal{G}^{3}:=(\mathcal{N}^{3},\mathcal{A}^{3},\mathcal{V}^{3})\) with the corresponding cost vector \(c^{3}\). The set of nodes \(\mathcal{N}^{3}\) will be populated with the same set of nodes in \(\mathcal{N}^{2}\) plus the additional nodes created to account for the nodes that fall into multiple node sets. For every \(i\in\mathcal{N}^{2}\), create \(|\mathcal{M}(i)|\) nodes and assign each to a different node set. For all \(k\in\mathcal{M}(i)\), add the node \(i_{k}\) to \(\mathcal{N}^{3}\), and to the node set \(\mathcal{V}^{3}_{k}\). This insures that \(|\mathcal{M}(i_{k})|=1\). Any arcs to and from the original nodes are duplicated as well. For every arc \((i,j)\in\mathcal{A}^{2}\), create the arc \((i^{p},j^{q})\in\mathcal{A}^{3}\) with the corresponding cost \(c^{3}_{i^{p},j^{q}}=c^{2}_{i,j}\) for every \(p\in\mathcal{M}(i)\) and \(q\in\mathcal{M}(j)\). In addition, zero cost arcs  
Figure 2: Example of Problem (P1) and Problem (P2) from Stage 1 of transformation.