## 2 Related Works
### Problem Definition for MDCOVRPPD  
There are many agents (\(W_{j},\ j=1,2,\ldots,m\)), and many jobs (\(J_{k},\ k=1,2,\ldots,n\)) are arranged in two-dimensional space. In the initial position, the agent (\(W_{j}\)) has a moving speed (\(V_{j}\)), energy level (\(B_{j}\)), residual performance (\(R_{j}\)), and maximum loading capacity (\(L_{j}\)) for multiple job selections. Job (\(J_{k}\)) is a sequence that moves from the starting position (\(S_{k}\)) to the target position (\(T_{k}\)), and a sequence of other jobs may overlap during the execution of the sequence of a job. All jobs must be selected and processed, but not all agents must do the job. The agent may select fewer jobs than their maximum loading capacity and, in some cases, may not select any jobs. The agent can move to the target position of the current job or the starting position of another job after arriving at the starting position of the selected job. According to this selection, the time of travel was calculated as the distance between the positions divided by the moving speed of each agent.  
In the case of a general CVRP, the parameters that define the problem are the number of customers/jobs (\(N\)), the number of vehicles/agents (\(K\)), and the capacity of the vehicle/agent (\(C\)). (\(C\)) has a fixed value based on (\(N\)) and (\(K\)).  
In contrast, the parameters considered in the instance of MDCOVRPPD are the number of jobs (\(N\)), number of agents (\(K\)), payload loading capacity of an agent (\(L\)), velocity of an agent (\(V\)), starting position of a job (\(S\)), target position of a job (\(T\)), energy level of an agent (\(B\)), and residual performance of an agent (\(R\)). When creating each problem instance, all parameters were randomly generated within a specified range, except for (\(N\)) and (\(K\)).  
Figure 1 shows an example of a job assignment. When the number of agents is three and the number of jobs is four, job \(\{I_{1},\ J_{2},\ J_{4}\}\) is assigned to agent \(\{W_{1}\}\), job \(\{J_{3}\}\) is assigned to agent \(\{W_{2}\}\), and agent \(\{W_{3}\}\) is not assigned a job.  
If agent \(W_{i}\) selects \(N\) jobs, the maximum number of state transitions is calculated in Equation (1) as follows:  
\[\#MAX_{TR}\,|\,_{W_{i}}=N*(N+1)*(N-1)!=(N+1)! \tag{1}\]  
The actual number of state transitions is smaller than that of Equation (1) because the target position in which the starting position is not selected in the sequence for the state transition cannot be changed.  
Figure 2 shows an example of a state transition diagram. Agent \(W_{1}\) can display a path of state transitions that can be selected for three jobs \(\{J_{1}(S_{1}\to T_{1}),\ J_{2}(S_{2}\to T_{2}),\ J_{4}(S_{4}\to T_{4})\}\).  
Figure 1: An example of the multi-agent (\(M\) = 3) and multi-job (\(N\) = 4) assignment problem.  
The total cost of the agent \(W_{1}\)'s traveling path is as shown in Equations (2) and (3).  
\[\begin{array}{ll}total\ cost&\mid_{W_{1}}=\sum c\big{(}T_{i},\ T_{j}\big{)}\mid_{W_ {1}}\\ &=\ \mathrm{c}(W_{1},S_{1})\mid_{W_{1}}+c(S_{1},S_{2})\mid_{W_{1}}+c(S_{2},T_{1}) \mid_{W_{1}}+\\ &c(T_{1},S_{4})\mid_{W_{1}}+c(S_{4},T_{4})\mid_{W_{1}}+c(T_{4},T_{2})\mid_{W_{1 }}+\\ &c(T_{2},END)\mid_{W_{1}}\end{array} \tag{2}\]  
\[c\big{(}T_{i},\ T_{j}\big{)}\mid_{W_{1}}=\left\{\frac{0}{\frac{\sqrt{\big{(}T _{iix}-T_{f_{j}}\big{)}^{2}+\big{(}T_{iy}-T_{f_{j}}\big{)}^{2}}}};\ M_{ij}\
eq 0\right. \tag{3}\]