## 3 1-Principal-1-Assistant Scenario
### Heuristic Construction  
The procedure CADROUTES is the core of the algorithm. It provides three partial routes, i.e., HP, ILS, and SA, which are generated by three methods, including the heuristic CONSTRUCT, an iterated local search ITEROCALSERACH, and a simulated annealing procedure, respectively. Heuristics are effective methods to address routing problems [18], so that the procedure CONSTRUCT is designed to find a valid solution. Before describing the method, the features of the routes for the principal-assistant team are provided first. The route \(r=\{principal_{r},assistant_{r}\}\) can be merged into one structure, as in Figure 2, and the route can be rewritten as \(r=\{r_{i}\}\), where \(r_{i}\) is a partial route. The partial routes can be classified into three types of components, including short line segments, simple triangles, and complex triangles. As Figure 2 shows, in a short line segment, the principal agent moves from one vertex to the other directly, serving one vertex, such as the principal agent route \(\{v_{0},v_{6}\}\) and \(\{v_{3},v_{9}\}\) without the assistant agent route. In a simple triangle such as the principal agent route \(\{v_{6},v_{3}\}\) with the assistant agent route \(\{v_{6},v_{5},v_{3}\}\), the principal agent departs from the released vertex, releasing the assistant agent, and moves to retrieved vertex directly, retrieving the assistant agent. The principal-assistant serves two vertices. In a complex triangle, the principal agent moves from the released vertex to the retrieved vertex through other vertices, such as the principal agent route \(\{v_{8},v_{1},v_{2},v_{4}\}\) with the assistant agent route \(\{v_{8},v_{7},v_{4}\}\). It is intuitive to select the partial route that serves the most tasks locally, but a smaller time cost may improve the opportunity to serve more tasks in the future. To balance these two factors, the profit per unit time cost \(\phi(r)\) is defined in Definition 1 to help select the partial routes. At every iteration, the heuristic selects a valid partial route with the highest profit available per unit cost. **Definition 1**. : _The profit available per unit cost can be then defined as follows:_  
\[\phi(r)=\frac{N(r)}{cost(principal_{r})} \tag{29}\]  
_where \(cost(principal_{r})\) is the traveling time of the principal agent in principal\({}_{r}\), and \(N(r)\) is the number of tasks served by route \(r\)._  
It can be derived that at each iteration, there are \(\mathcal{O}(n)\) short line segments, \(\mathcal{O}(n^{2})\) simple triangles, and \(\mathcal{O}(n^{n})\) complex triangles to be selected. The solution space of complex triangles is too large to search quickly. However, a complex triangle \(\{principal_{r},assistant_{r}\}\) can be approximated by a corresponding long line segment \(\{principal_{r},\{\}\}\). It can be derived that  
\[\phi(\{principal_{r},\{\}\})+\epsilon =\phi(\{principal_{r},assistant_{r}\}) \tag{30}\] \[\frac{g-1}{cost(principal_{r})} +\epsilon =\frac{g}{cost(principal_{r})}\]  
where \(\epsilon>0\) is a real number. A larger \(cost(principal_{r})\) indicates a smaller gap between \(\{principal_{r},assistant_{r}\}\) and \(\{principal_{r},\{\}\}\). Because a long line segment can be split into several short line segments, to accelerate the search process, the heuristic only selects partial routes from short line segments and simple triangles. The procedure CONSTRUCT is outlined in Algorithm 2. Based on the above observation, it searches for the partial routes \(r^{\prime}\) with the highest \(\phi(r^{\prime})\) from the short lines and simple triangles and inserts them into the original routes iteratively, until there are no valid partial routes. In line 6, all the short line segments and simple triangles are found and inserted into the set \(R\). From line 8 to line 11, the algorithm selects the partial route \(r^{\prime}\) with the maximum \(\phi(r^{\prime})\).