## 7 Experimental Evaluation
### Results for the Full Request Satisfaction Mode
#### 7.2.3 R-DPAP Results  
Figures 13-15 present the results associated with R-DPAP instances in the full request mode satisfaction. The algorithms behave relatively to each other as for the V-DPAP case. More precisely, with respect to the global utility, algorithm util returns the best global utility, then, lex, a-lex, greedy, and n-rr equivalently, and finally, n-rr. Figure 14: Utility profiles (in leximin order) for the first 5 instances for a constellation with 2 orbital planes (4 satellites) and each algorithm (south: best utility over all agents; west: second best utility; north: third best utility; east: worst utility), for full request satisfaction mode and encoded as R-DPAP. Figure 13: Performance metrics obtained by each algorithm for each constellation size, for full request satisfaction mode and encoded as R-DPAP. (**a**) Normalized utility; (**b**) global reward; (**c**) computation time. In comparison with the V-DPAP results, instances encoded in the R-DPAP framework allow a higher utility to be reached. First, the normalized global utility (Figure 13a) is around 0.5 for algorithm \(\mathsf{util}\) with 32 satellites. Note that it is only a little less with 4 satellites (around 0.45). In terms of global reward (Figure 13b), the average score is around 1700 for \(\mathsf{util}\) with 32 satellites. The fact that the utility is higher in the R-DPAP benchmark than in the V-DPAP framework comes from the fact that the first allows the orbit slots to be split while the second does not. Consequently, with R-DPAP, when an agent is given an orbit slot on a path with a non-null utility, overlapping orbit slots for other agents might still be selectable. Such a phenomenon can be confirmed by the radars of Figure 14. Indeed, instance 0 with 2 orbital planes (left radar) shows that it is possible for three agents out of four to have a non-null utility. Such an allocation is obtained with algorithm \(\mathsf{lex}\). In this case, note that algorithm \(\mathsf{a}\)-lex performs worse than \(\mathsf{lex}\) in the sense that two agents have a zero utility with \(\mathsf{a}\)-lex. This is probably due to the fact that both algorithms compute that the worst served agent has a null utility, but \(\mathsf{a}\)-lex has to choose to which agent this null utility is allocated. In the case of a bad choice, this prevents \(\mathsf{a}\)-lex from obtaining a higher utility for the second worst served agent. The left radar of Figure 14 also shows that \(\mathsf{util}\) tends to favor agents with high utilities (two agents with utility equal to 1, and two agents with 0), whereas \(\mathsf{lex}\) splits utility between agents (best agent with utility 1, two others with utility 0.45, and the last with 0). The average utility profiles of Figure 15 confirm this difference of behavior between algorithms \(\mathsf{util}\) and \(\mathsf{lex}\). As for V-DPAP, algorithm \(\mathsf{a}\)-lex's performance is lower than \(\mathsf{util}\) and \(\mathsf{lex}\) with respect to fairness. Other approaches manage on average to serve a second agent but with a very low utility. Finally, the order of magnitude for the time required to compute solutions is the same between V-DPAP and R-DPAP. These results show that, in the case of R-DPAP with full request mode satisfaction, the best trade-off between global utility and computation time is given by algorithm \(\mathsf{util}\)  
Figure 15: Average utility profiles (in leximin order) for each constellation size and each algorithm (south: best utility over all agents; west: second best utility; north: third best utility; east: worst utility), for full request satisfaction mode and encoded as R-DPAP. However, in terms of fairness, this algorithm is not as good as algorithm lex in several instances, even if lex gives larger computation times. Note that R-DPAP is still parametric in the sense that it requires defining the duration \(minD\) (here 120 s) requested in each orbit slot.