## 3 1-Principal-1-Assistant Scenario
### Division and Combination  
The process employs a fact that, in a principal agent route \(principal_{r}\), there exists at least one vertex called the turn vertex \(p_{turn}=\arg\max_{p_{i}\in principal_{r}}{m_{1}(p_{i},v_{0})}\), and the principal agent route \(principal_{r}\) can be split into two sequences at the turn vertex, including the \(\{p_{0},p_{1},...,p_{turn}\}\) and the \(\{p_{turn},...,p_{g-2},p_{g-1}\}\). In Figure 1, \(p_{5}\) is the turn vertex and the principal agent route is split into \(\{p_{0},p_{1},p_{2},p_{3},p_{4},p_{5}\}\) and \(\{p_{5},p_{6},p_{7},p_{8},p_{9}\}\). The partial routes contain monotonic parts and wavy parts [17]. The vertices of the monotonic parts are sorted in some order and the vertices of the wavy parts are disordered. Most of the vertices of the former are in monotonic parts, sorted in the non-decreasing order of the time cost to \(v_{0}\), e.g., \(\{p_{2},p_{3},p_{4},p_{5}\}\). However, there exist some vertices in wavy parts, where a vertex may be closer to \(v_{0}\) than its previous vertex, e.g., \(\{p_{1},p_{2}\}\). In general, the former sequence of the principal agent route \(\{p_{0},p_{1},p_{2},p_{3},p_{4},p_{5}\}\) is the process of leaving from the initial vertex. Similarly, the latter sequence of the principal agent route \(\{p_{5},p_{6},p_{7},p_{8},p_{9}\}\) also has monotonic parts and wavy parts, but it is a return process, where the principal-assistant team returns to the initial vertex. The divisions and combinations are designed based on the feature, which is detailed in Algorithm 1.  
In the division step, the turn vertex and the arrival time to it are selected first. In line 2, each vertex except the initial vertex can be regarded as the turn vertex \(v_{turn}\). \(U_{t}=\{v_{i}\mid m_{1}(v_{i},v_{0})\leq m_{1}(v_{turn},v_{0}),v_{i}\in U\}\) denotes the set of candidate vertices for the principal agent. In line 6, each time \(t\) between \(t_{min}\) and \(t_{max}\) will be regarded as the arrival time to \(v_{turn}\), the time budget of the leave process is \(t\) and the time budget of the return process is \(d_{0}-t\). Given the different subsets and time budgets, the lea processes are generated by CADROUTES. The LR and RR represent the set of candidate leave processes and the set of candidate return processes, respectively. In line 11, the optimal principal-assistant route is found. In line 13, the optimal combination of a leaving process from LR and a return process from RR is selected as the output.  
```
Input: Graphs \(G_{1}=(V,M_{1}),G_{2}=(V,M_{2})\), deadline set \(D\) Output: A principal-assistant route \(r=\{principal_{r},assistant_{r}\}\)
1\(U\gets V-\{v_{0}\}\), \(r\leftarrow\{\}\); for\(v_{turn}\in U\)do
2\(U_{t}=\{v_{i}\mid m_{1}(v_{i},v_{0})\leq m_{1}(v_{turn},v_{0}),v_{i}\in U\}\);
3\(t_{min}\gets m_{1}(v_{0},v_{turn})\);
4\(t_{max}\leftarrow\min\{d_{turn},d_{0}-m_{1}(v_{0},v_{turn})\}\);
5 for\(t\in[t_{min},t_{max}]\)do
6 LR\(\leftarrow\) CADROUTES(\(U,U_{t},v_{0},v_{turn},0,t\));
7\(U^{\prime}\leftarrow\{v_{i}\mid v_{i}\in U,v_{i}\
otin Ir,lr\in\mathrm{LR}\}\);
8\(U^{\prime}_{t}\leftarrow\{v_{i}\mid v_{i}\in U_{t},v_{i}\
otin Ir,lr\in \mathrm{LR}\}\);
9\(\mathrm{RR}\leftarrow\) CADROUTES(\(U^{\prime},U^{\prime}_{t},v_{turn},v_{0},t,d_{0}-t\));
10\(r_{max}\leftarrow\arg\max_{r^{\prime}\in\mathrm{LR},\mathrm{RR}}N(r^{\prime})\);
11 if\(N(r_{max})>N(r)\)then
12\(r\gets r_{max}\);
13
14 return\(r\);
15 Function\(\mathrm{CADROUTES}(U,U_{t},v_{s},v_{e},st,bdg)\)
16 HP\(\leftarrow\) CONSTRUCT(\(U,U_{t},v_{s},v_{e},st,bdg\));
17 ILS\(\leftarrow\) ITERLOCALSEARCH(HP,\(U-\mathrm{HP}\));
18 SA\(\leftarrow\) SIMANNEAL(\(U,U_{t},v_{s},v_{e},st,bdg\));
19 returnHP,ILS,SA;
20 End Function
```  
**Algorithm 1**Hybrid Combination Algorithm