## 2 Methods
### Phase 2  
The initial tour of Phase 1 is iteratively extended with new points from the internal area of polygon \(P(V)\) using the cheapest insertion strategy at Phase 2 [15]. Let \(l\
ot\in T_{h-1}\) be a candidate point to be included in tour \(T_{h-1}\), resulting in an extended tour \(T_{h}\) of iteration \(h>0\), and let \(t_{i}\in T_{h-1}\). Due to the triangle inequality, \(w(t_{i},l)+w(l,t_{i+1})\geq w(t_{i},t_{i+1})\); i.e., _the insertion of point \(l\) between points \(t_{i}\)_ and \(t_{i+1}\), will increase the current total cost \(C(T_{h-1})\) by \(w(t_{i},l)+w(l,t_{i+1})-w(t_{i},t_{i+1})\geq 0\) (see Figure 4). Once point \(l\) is included between points \(t_{i}\) and \(t_{i+1}\), for the convenience of the presentation, we let \(t_{m}:=t_{m-1}\), \(t_{m-1}:=t_{m-2}\), \(\cdots\), \(t_{i+3}:=t_{i+2}\), \(t_{i+2}:=t_{i+1}\) and \(t_{i+1}:=l\) (due to the way in which we represent our tours, this re-indexing yields no extra cost in our algorithm). Figure 4: The triangle inequality. Figure 3: Example that shows the extreme vertices and girding polygon. In Table 3, we give a formal description of our procedure that inserts point \(l\) between points \(t_{i}\) and \(t_{i+1}\) in tour \(T\). Procedure construc_tour  
At each iteration \(h\), the current tour \(T_{h-1}\) is extended by point \(l^{h}\in V\setminus T_{h-1}\) yielding the minimum cost \(c_{l}^{h}\) (defined below), which represents the increase in the the current total cost \(\mathrm{C}(T_{h-1})\) if that point is included into the current tour \(T_{h-1}\). The cost for point \(l\in V\setminus T_{h-1}\) is defined as follows:  
\[c_{l}^{h}=\min_{t_{i}\in T_{h-1}}\{w(t_{i},l)+w(l,t_{i+1})-w(t_{i},t_{i+1})\}. \tag{9}\]  
For further references, we denote by \(i(l)\) the index of point \(t_{i}\) for which the above minimum for point \(l\) is reached, i.e., \(w(t_{i(l)},l)+w(l,t_{i(l)+1})-w(t_{i(l)},t_{i(l)+1})=\min_{t_{i}\in T_{h-1}}\{w (t_{i},l)+w(l,t_{i+1})-w(t_{i},t_{i+1})\}\). Thus, \(l^{h}\) is a point that attains the minimum  
\[\min\{c_{l}^{h}|l\in V\setminus T_{h-1}\}, \tag{10}\]  
whereas the ties can be broken arbitrarily. To speed up the procedure, we initially calculate the minimum cost for each point \(l\in V\setminus T_{h-1}\). After the insertion of point \(l^{h}\), the minimum cost \(c_{l}^{h}\) is updated as follows:  
\[c_{l}^{h}:=\min\{c_{l}^{h-1},w(t_{i},l)+w(l,t_{i+1})-w(t_{i},t_{i+1}),\ w(t_{i+1},l)+w(l,t_{i+2})-w(t_{i+1},t_{i+2})\}. \tag{11}\]  
We can describe now Procedure _construct_tour_ as shown in Table 4.  
The time complexity of the Procedure construct_tour is \(O(n^{2})\). \begin{table}
\begin{tabular}{l l} \hline \hline
**PROCEDURE**_construct_tour_(\(V\), \(T_{0}\) ) \\ \hline
1 & \(h:=1\) \\
2 & **FOR** each point \(l\in V\setminus T_{h-1}\)**DO** \\
3 & \(c_{l}^{h}:=\min_{t_{i}\in T_{h-1}}\{w(t_{i},l)+w(l,t_{i+1})-w(t_{i},t_{i+1})\}\) \\
4 & **WHILE** exists a vertex \(l\in V\setminus T_{h-1}\)**DO** \\
5 & get \(l^{h}\) \\
6 & _insert_point_in_tour_ (\(T_{h-1},l^{h},i(l^{h})\)) \\
7 & **FOR** each point \(l\in V\setminus T_{h}\)**DO** \\
8 & \(c_{l}^{h+1}:=\min\{c_{l}^{h},\ w(t_{i},l)+w(l,t_{i+1})-w(t_{i},t_{i+1}),\ w(t_{i+1},l)+w(l,t_{i+2})-w(t_{ i+1},t_{i+2})\}\) \\
9 & \(h:=h+1\) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Procedure _construct_tour_. \begin{table}
\begin{tabular}{l l} \hline \hline \multicolumn{2}{l}{**PROCEDURE**_insert_point_in_tour_(\(T\), \(l\), \(i\))} \\ \hline
1 & \(p:=|T|\) \\
2 & **IF**\(i<p\)**THEN** \\
3 & \(j:=p+1\) \\
4 & **WHILE**\(j>i+1\)**DO** \\
5 & \(t_{j}:=t_{j-1}\) \\
6 & \(j:=j-1\) \\
7 & \(t_{i+1}:=l\) \\
8 & **RETURN**\(T\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Procedure _insert_point_in_tour_. \(c_{3}^{2}=\{c_{3}^{1},w(4,3)+w(3,6)-w(4,6),w(6,3)+w(3,2)-w(6,2)\}\)  
\(=w(6,3)+w(3,2)-w(6,2)\). Hence, \(\min\{c_{1}^{2},c_{3}^{2}\}=c_{3}^{2}=w(6,3)+w(3,2)-w(6,2)\); \(l^{2}=3\) and \(i(3)=6\). Therefore, point 3 will be included in tour \(T_{2}\) between points 6 and 2 (Figure 7).