## 7 Experimental Evaluation
### Results for the Partial Request Satisfaction Mode
#### 7.3.1 V-DPAP Results  
Figures 16 and 17 show the results for instances encoded as V-DPAP. From Figure 16a, we can observe that the normalized utility is much higher than with instances encoded in V-DPAP with the request full satisfaction mode. For instance, for a constellation involving 4 satellites, algorithms util, lex and a-lex almost reach a 0.6 normalized utility value. For 32 satellites, this normalized utility is equal to 0.85. In terms of reward (Figure 16b), the global reward is also much higher. Note that the relative performance of the algorithms is the same as for V-DPAP with the full satisfaction mode, i.e., algorithm util returns the allocation with the best global utility, then lex, a-lex, p-rr, greedy, and n-rr. Nevertheless, with 32 satellites, all algorithms except n-rr return allocations with approximately the same global utility. This increase in performance with the change in request mode satisfaction shows that even if paths conflict, the skip possibility allows many more requests to be tackled. Figure 16: Performance metrics obtained by each algorithm for each constellation size, for flexible requests encoded as V-DPAP. (**a**) Normalized utility; (**b**) global reward; (**c**) computation time. From Figure 16c, we can first notice that the time required by algorithms lex and a-lex is much higher than for V-DPAP with request full satisfaction mode. In fact, for algorithm lex, 10 s are required for V-DPAP with request full satisfaction mode but 100 for V-DPAP with request partial satisfaction mode. However, for these algorithms, the order of magnitude does not change with the constellation size. Such a phenomenon is probably due to the fact that there are a lot of complex paths (i.e., paths that are not \(\mathit{source}\rightarrow\mathit{sink}\)) with the same utility, which makes it harder to compute the worst utility for a given agent. Algorithms greedy, p-rr, and n-rr also require much more time than for instances in V-DPAP with full request satisfaction mode. This can be explained by the fact the number of paths is much larger but that nodes still belong to several conflicts. Therefore, every time a path is selected in a graph, other graphs have many nodes that are deactivated, which forces new best paths to be computed and overall requires some computation time. In comparison, algorithm util requires approximately the same time in the partial and full satisfaction modes. Next, Figures 17 and 18 show that in the partial satisfaction mode, the utility profiles are much more balanced between agents. The radars in Figure 17 allow the algorithms' behaviors to be compared over some instances involving two satellites. It shows that algorithm util favors high utilities, which is sometimes quite fair (instance 3) and sometimes not (instance 0). Algorithm greedy serves very well one agent but cannot serve well the others because of conflicts between paths. Algorithm p-rr performs a little better than greedy in terms of fairness. Algorithms lex and a-lex allow the utility to be balanced between the agents. For instance, the top line radars show that it is possible to reach a solution where all agents have approximately the same utility (around 0.6). Algorithm n-rr is also quite fair but the utility per agent is much lower (0.2). Figure 18 shows that these comments can be generalized to all instances on average. In the case of a larger constellation, the algorithms (except n-rr) behave almost the same in terms of leximin vectors, and there exist solutions where all agents can be served quite well. These results show that in the case of V-DPAP with requests partial satisfaction mode, algorithm util offers the best utility/time trade-off. However, in terms of fairness, such an algorithm gives good performance only for constellations with at least 8 orbital planes (16 satellites). For a smaller number of satellites, algorithms lex and a-lex can be much fairer (depending on the instance), despite a greater computation time.