## 7 Experimental Evaluation
### Benchmarks
#### 7.1.5 Experimental Conditions  
Our experimental environment has been implemented in Java 1.8 and executed on a 20-core Intel(R) Xeon(R) CPU E5-2660 v3 @ 2.60 GHz, 62 GB RAM, Ubuntu 18.04.5 LTS. Utilitarian, leximin, and approximate leximin make use of the Java API of IBM CPLEX 20.1 (using a 2 min timeout). Note that the computation time does not need to be as tight as in Earth observation scheduling problems. In fact, in EOSPs, it might be operationally required to generate a schedule within a few minutes. Such operational constraints are not relevant for orbit slot allocation problems as plans are computed months in advance. Nevertheless, we limit the time taken by each call to the MILP solver. For each pair (problem type, request satisfaction mode) in {V-DPAP, R-DPAP} \(\times\) {full, partial}, we have generated four types of plots. The first and second types of plots (e.g., Figure 10(a),b) allow visualization of the average normalized global utility and the average global reward (i.e., utility not normalized), respectively, both with \([0.05,0.95]\) as a confidence interval 2 for each constellation size and for each algorithm. In the second type of plot (e.g., Figure 10(c)), the average computation time (logarithmic time scale) is indicated, also for each constellation size and each algorithm. Finally, the fourth type of plot (e.g., Figures 12) allows us to analyze the fairness of the resulting allocations. More precisely, we show the average utility profile in all instances for each algorithm and for each constellation size. Such a utility profile is in leximin order: for each radar, among the four agents, the south represents the agent having the best utility over all agents, the west is the second best utility, the north is the third best utility, and the east corresponds to the agent with the worst utility. For some cases, we sometimes detail utility profiles obtained by each algorithm in some specific instances. We first present results associated with the full request satisfaction mode, and then results associated with the partial request satisfaction mode. \begin{table}
\begin{tabular}{c c c} \hline \hline \multicolumn{2}{c}{**Generation Parameters**} & **Values** \\ \hline \multirow{4}{*}{Constellation} & Altitude & 500 km \\  & Number of orbital planes \(n_{p}\) & 2, 4, 8, 16 \\  & Number of satellites/plane & 2 \\  & Inclination & 40\({}^{\circ}\) \\ \hline Scheduling & Start & 1 January 2020 \\ horizon & Duration & 180 days \\ \hline \multirow{2}{*}{Problems} & Number of users & 4 \\  & Type & V-DPAP, R-DPAP \\ \hline \multirow{4}{*}{Requests} & Number of requests/user & 2 \\  & Requested observation Times & 3 RTs/request \\  & Maximum random time shift \(\delta_{r}\) & 1 h \\  & Tolerance \(\Delta\) & 1 h \\  & Minimum slot duration \(minD\) & 120 s \\  & Satisfaction mode & full, partial \\ \hline \multirow{2}{*}{Algorithms} & Type & \multirow{2}{*}{util, lex, a-lex, greedy, p-rr, n-rr} \\  & CPLEX time limit & & 120 s \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Generation parameters along with their possible values for configuring instances. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Problem**} & **Properties** & \multicolumn{4}{c}{\(n_{p}\)} \\ \cline{3-6}  & & **2** & **4** & **8** & **16** \\ \hline \multirow{4}{*}{V-DPAP} & Conflicts & 37,715.34 & 74,009.12 & 146,657.94 & 291,831.52 \\  & Conflict size & 2.0 & 2.0 & 2.0 & 2.0 \\  & Slots per RT & 1.94 & 3.81 & 7.54 & 15.01 \\  & Slot duration (s) & 618.10 & 616.44 & 616.91 & 616.66 \\ \hline \multirow{4}{*}{R-DPAP} & Conflicts & 1715.38 & 3527.42 & 6981.19 & 13,929.55 \\  & Conflict size & 3.28 & 3.17 & 3.21 & 3.19 \\  & Slots per RT & 1.94 & 3.81 & 7.54 & 15.01 \\  & Slot duration (s) & 618.10 & 616.44 & 616.91 & 616.66 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Properties of generated problems used in the experimental evaluation (average values over 100 instances per configuration are reported).