## 3 1-Principal-1-Assistant Scenario
### Iterated Local Search and Simulated Annealing  
It is possible for the procedure CONSTRUCT to be trapped in local optimum; thus, the iterated local search [15] and the simulated annealing [19; 20] are incorporated to improve the opportunity of escaping from local optimum. The two methods contain some basic operations on the principal-assistant routes. There are six basic operations that refer to the operations mentioned by [PERSON] et al. [21], as shown in Table 2. The operation Swap and Replace ensures that the new principal-assistant route serves at least as many tasks as the old one does. The operation Insert inserts an unserved task into the principal agent route and deletes the resulting infeasible partial routes of the assistant agent. The operation Subjoin inserts the partial assistant agent route with the minimum time cost. If more than one assistant agent route has the same time cost, it selects the assistant agent route with the minimum \(d_{i}\), which is the deadline of the served vertex \(v_{i}\). The operation Removet deletes one vertex in the principal agent route and the resulting invalid assistant agent routes. The operation Removet is a safe operation and decreases the quality of the current solution but may lead to a better solution in the following process. The procedure ITERLOCALSERACH proposed in Algorithm 3 is a metaheuristic algorithm, which starts from the initial solution HP created by the CONSTRUCT and adopts four operations, i.e., Swap, Replace, Insert and Subjoin, to orderly search the neighbor solutions. The operations will be used iteratively. At Step 1, Swap is used to operate two vertices in the principal agent route, except the start vertex and end vertex. If the Swap operation reduces the time cost, it is adopted to update the route. At Step 2, Replace is used to operate any vertex except the start vertex and end vertex. If it is valid, the operation will be accepted, and the replaced position will not be operated again. Replace is similar to Swap, as it also updates the route and terminates when there is no valid operation. At Step 3, Insert is used to fully utilize the budget. One valid vertex is inserted into the first available position, and the principal agent route is updated. Then, Insert continues to be used in the new route. At Step 4, Subjoin is used to plan new partial routes for the assistant agent. The valid simple or complex triangles that serve other tasks are sorted in the increasing order of their time cost. The triangle with the smaller time cost is subjoined preferentially. The ITERLOCALSERACH will execute until the principal-assistant route cannot be improved or the number of iterations reaches the upper limit cntlimit. ```
1 Function ITERLOCALSERACH(\(route,U,U_{t},budget\))
2 Swap;
3 Replace;
4 Insert;
5 Subjoin;
6 returnILS;
7 End Function
```  
**Algorithm 3**ITERLOCALSERACH  
The route ILS generated by the ITERLOCALSERACH is not necessarily better than the HP but provides another possible partial principal-assistant route that can be combined with others to generate a better entire partial route. Simulated annealing can converge to the global optimum in some probabilistic sense [19] and has been applied in many optimization problems [18]. Simulated annealing is different from the iterated local search. It has an environment temperature which will decrease as the procedure runs; when the temperature is smaller than a minimum temperature, the procedure terminates. At the temperature decreasing moment, it generates a new partial route; the new one will be accepted and will replace the current principal-assistant route if the new one is better; otherwise, the new one will be accepted as the current one