## 4 \(m\)-Principal-\(u\)-Assistant Scenario
### Principal-Assistant Route Construction
#### 4.3.2 Principal Agent Route Construction  
The construction of the principal agent routes with temporal constraints is a classic problem, called the orienteering problem with time windows (OPTW) [21; 24], where a traveler needs to serve vertices during their time windows and then return to the initial vertex. Two efficient algorithms can be used in the principal agent route construction, including the line construction [21] and an iterated local search algorithm [15]. The outline of the line construction is to insert an unserved vertex between two vertices in a valid route iteratively and ensure that the resulting route is also valid until no vertex can be inserted. If there is more than one option, the operation adding the minimum time cost will be selected. The iterated local search algorithm (ILS) is a two-step process. First, it creates a valid route by line construction, and then the perturbation and local search techniques are used to improve the route within a certain iteration. Two algorithms will be embedded into our integrated algorithm individually, and their performances will be evaluated. The above two methods outperform the other routing algorithms [23] in the principal agent route construction, but in the construction of the principal-assistant routes, they ignore the influence of the assistant agent routes and result in poor performance in some situations. An example is displayed in Figure 3. In Figure 3, the line construction creates \(\mathit{principal}_{t}=\{v_{0},v_{3},v_{0}\}\), and the assistant agent routes \(\mathit{assistant}_{t}^{1}\), \(\mathit{assistant}_{r}^{2}\) are empty. However, there is an obvious better principal-assistant route, \(\mathit{principal}_{r}=\{v_{0},v_{2},v_{0}\}\), \(\mathit{assistant}_{r}^{1}=\{(v_{2},v_{1},v_{0})\}\), and \(\mathit{assistant}_{r}^{2}=\emptyset\). It demonstrates a phenomenon that if a principal agent travels to a vertex surrounded by some assistant agent-accessible tasks, it is possible to serve tasks then directly move to a task costing less time. Inspired by the influence of the assistant agents, the density of the vertex is defined in Definition 2. The \(\mathit{density}_{i}\) of \(v_{i}\) is influenced by the number of assistant agent-accessible tasks and their distances to \(v_{i}\) in graph \(G_{2}\). The distances are squared to improve their weight; the vertex with the most assistant agent-accessible tasks located in an adjacent area is preferred. **Definition 2**. : _The density of the task \(v_{i}\) is as follows:_  
\[\mathit{density}_{i}^{S}=\frac{1}{u}\cdot\sum_{\mathit{dur}=1}^{\eta}\frac{ \left|V_{\mathit{dur}}^{i}\right|}{(0.5\cdot\mathit{dur})^{2}} \tag{52}\]  
_where \(V_{\mathit{dur}}^{i}=\{v_{j}\in S\mid 2*m_{2}(v_{i},v_{j})=\mathit{dur}\}\)._  
The density-based construction algorithm is designed based on the line construction and the concept of the density of a task, which is shown in Algorithm 5. Before using line construction, all the provided tasks are sorted in ascending order based on the density of each task, and a factor \(0.0<\zeta<1.0\) decides how many tasks have high priority to be inserted in the principal agent route. Assume that \(V^{\prime}\) is the sorted set of tasks; first, \(\lceil|V^{\prime}|\cdot\zeta\rceil\) tasks in \(V^{\prime}\) have high priority. The tasks with high priority will be stored in order in list \(H\), and the rest of the tasks with low priority will be stored in order in \(L\). Thetasks in \(H\) will be inserted into principal agent route \(principal\), by the line construction \(lineInsert(principal,S)\), until there is no vertex that can be inserted.