## 3 1-Principal-1-Assistant Scenario
### Heuristic Construction
If more than one partial route has the same \(\phi(\cdot)\), the partial route with the minimum \(d_{i}\), which is the deadline of the end vertex of the partial route, is selected. **Theorem 2**. : _The Construct Algorithm proposed in Algorithm 2 is an \(\mathcal{O}(\frac{l_{min}}{g,l_{max}})\)-approximation algorithm, where \(l_{min}\) is the minimum distance between any two vertices in \(G_{1}\) and \(l_{max}\) is the maximum distance between any two vertices in \(G_{1}\)._  
Proof of Theorem 2.: To prove the approximation ratio, the upper bound of the optimum and the lower bound of the Construct Algorithm need to be provided firstly. Assume that the optimum \(r^{\star}\) serves \(q^{\star}\) tasks and the route \(r^{\prime}\) pair created by Construct Algorithm serves \(q^{\prime}\) tasks. In the optimal case, \(r^{\star}\) is totally constituted by simple triangles, each of which serves two tasks and costs \(l_{min}\). Hence, for the optimum,  
\[\frac{q^{\star}}{cost(q^{\star})}\leq\frac{2}{l_{min}}. \tag{31}\]  
Figure 2: The structure of a principal–assistant route \(r\): The principal agent serves circle and square vertices. The assistant agent serves triangle vertices. The principal agent releases or retrieves the assistant agent at square vertices. On the other hand, there exists a lower bound of its profit per unit cost. Assume \(r^{\prime}=(r_{0},r_{1},\cdots)\) and each component \(r_{i}\) serves \(q_{i}\) vertices and costs \(cost(r_{i})\) time steps. It can be derived that  
\[\frac{q^{\prime}}{cost(r^{\prime})}=\frac{\sum_{r_{i}\in r^{\prime}}q_{i}}{\sum _{r_{i}\in r^{\prime}}cost(r_{i})}\geq\min_{r_{i}\in r^{\prime}}\frac{q_{i}}{ cost(r_{i})} \tag{32}\]  
\(\frac{q^{\prime}}{cost(r^{\prime})}\) is greater than or equal to the minimum local profit per unit cost. In the worst case, the component departs from the start vertex and directly moves to serve the farthest vertex and returns, costing \(l_{max}\). Thus,  
\[\frac{q^{\prime}}{cost(r^{\prime})}\geq\min_{r_{i}\in r^{\prime}}\frac{q_{i}}{ cost(r_{i})}=\frac{1}{l_{max}}. \tag{33}\]  
The approximate ratio can be calculated by  
\[\frac{q^{\prime}/cost(r^{\prime})}{q^{\star}/cost(r^{\star})}\geq\frac{1/l_{ max}}{2/(l_{min})}=\frac{l_{min}}{2\cdot l_{max}}. \tag{34}\]  
Thus, the Construct Algorithm proposed in Algorithm 2 is an \(\mathcal{O}(\frac{l_{min}}{2\cdot l_{max}})\)-approximation algorithm. ```
1 Function\(\text{CONSTRUCT}(U,U_{t},v_{s},v_{e},st,bdg)\)
2\(principal_{r}\gets\{v_{s},v_{e}\}\);
3\(assistant_{r}\leftarrow\{\}\);
4\(p_{cur}\gets v_{s}\);
5 while\(cost(principal_{r})\leq budget\)do
6\(R\leftarrow\{r^{\prime}\mid principal_{r^{\prime}}\leftarrow\{p_{cur},v_{i}\},assistant_{r^{\prime}}\leftarrow\{(p_{cur},v_{j},v_{i})\},v_{j}\in U_{t},v_{i}\in U _{t},v_{i}\
otin v_{j}\}\);
7\(maxval\gets 0,d\gets d_{0},r_{max}\leftarrow\emptyset\);
8 for\(r^{\prime}\in R\)do
9 if\(r^{\prime}\) is validthen
10 if\(\phi(r^{\prime})>maxval\)then
11\(maxval\_{\phi}(r^{\prime}),d\gets d_{i},r_{max}\gets r^{\prime}\);
12
13 if\(r_{max}\
eq\emptyset\)then
14\(principal_{r}\leftarrow\{v_{s},...,p_{cur},v_{i},v_{e}\}\);
15\(assistant_{r}\gets assistant_{r}\cup assistant_{r_{max}}\);
16\(U\gets U-\{v_{i},v_{j}\},U_{t}\gets U_{t}-\{v_{i}\}\);
17
18\(p_{cur}\gets v_{i}\);
19
20 else
21 break;
22
23 return\(r=\{principal_{r},assistant_{r}\}\);
24 End Function
```  
**Algorithm 2**Construct Algorithm