# An Efficient Local Search Heuristic for Earth Observation Satellite Integrated Scheduling
## 5 Experiment
### Results on Small Instances  
First, we solve the model introduced in Section 3 by CPLEX on the small instances we created. The VTWs are discretized with a step of 10 s when using CPLEX (e.g., a VTW of 100 s contains 11 time points). We compare the results with those of the proposed heuristic algorithm, and the results are shown in Table 2.  
Figure 1: An example for the benchmark instances of area distribution.  
From the result of area distribution, we see that ELSH easily dominates TPGA. For both algorithms, the number of the accomplished user requests and the profit increases as the problem instance becomes larger, but ELSH accomplishes more user requests and produces more profit overall instances. The average improvement compared to TPGA is 13.75%.  
We draw a similar conclusion on world distribution instances. ELSH shows a great advantage over the TPGA. The average improvement compared to TPGA is up to 13.68%.  
In conclusion, the ELSH demonstrates excellent performance on all benchmark instances and easily dominates the state-of-the-art algorithm.  
\begin{table}
\begin{tabular}{r r r r r r r r r r r} \hline \hline  & \multicolumn{3}{c}{**2 Satellites**} & \multicolumn{3}{c}{**3 Satellites**} & \multicolumn{3}{c}{**4 Satellites**} & \multicolumn{3}{c}{**5 Satellites**} & \multicolumn{3}{c}{**6 Satellites**} \\ \hline
**Size** & **ELSH** & **TPGA** & **ELSH** & **TPGA** & **ELSH** & **TPGA** & **ELSH** & **TPGA** & **ELSH** & **TPGA** \\ \hline
200 & 851 & 736 & 866 & 747 & 872 & 770 & 880 & 764 & 892 & 776 \\
400 & 1753 & 1557 & 1755 & 1569 & 1758 & 1572 & 1790 & 1622 & 1809 & 1618 \\
600 & 2689 & 2389 & 2727 & 2395 & 2751 & 2463 & 2808 & 2485 & 2841 & 2510 \\
800 & 3668 & 3198 & 3705 & 3247 & 3752 & 3191 & 3772 & 3306 & 3810 & 3390 \\
1000 & 4475 & 3945 & 4483 & 3928 & 4555 & 4042 & 4604 & 4098 & 4647 & 4159 \\
1200 & 5389 & 4586 & 5290 & 4677 & 5511 & 4754 & 5554 & 4762 & 5598 & 4847 \\
1400 & 6068 & 5515 & 6200 & 5479 & 6403 & 5587 & 6425 & 5727 & 6591 & 5840 \\
1600 & 7007 & 6261 & 7183 & 6316 & 7331 & 6362 & 7343 & 6569 & 7595 & 6597 \\
1800 & 7935 & 6963 & 8246 & 7259 & 8254 & 7289 & 8360 & 7337 & 8530 & 7426 \\
2000 & 8186 & 7168 & 8209 & 7283 & 8430 & 7417 & 8554 & 7745 & 8658 & 7872 \\ \hline \hline \end{tabular}
\end{table}
Table 6: Comparison with TPGA on the total profit on world distribution instances.  
\begin{table}
\begin{tabular}{r r r r r r r r r r r} \hline \hline  & \multicolumn{3}{c}{**2 Satellites**} & \multicolumn{3}{c}{**3 Satellites**} & \multicolumn{3}{c}{**4 Satellites**} & \multicolumn{3}{c}{**5 Satellites**} & \multicolumn{3}{c}{**6 Satellites**} \\ \hline
**Size** & **ELSH** & **TPGA** & **ELSH** & **TPGA** & **ELSH** & **TPGA** & **ELSH** & **TPGA** & **ELSH** & **TPGA** \\ \hline
100 & 443 & 387 & 454 & 399 & 464 & 405 & 469 & 413 & 476 & 409 \\
200 & 883 & 785 & 925 & 814 & 920 & 808 & 937 & 828 & 941 & 842 \\
300 & 1298 & 1141 & 1350 & 1178 & 1391 & 1222 & 1399 & 1215 & 1419 & 1253 \\
400 & 1654 & 1434 & 1837 & 1575 & 1856 & 1642 & 1879 & 1630 & 1881 & 1643 \\
500 & 1945 & 1722 & 2310 & 2017 & 2318 & 2041 & 2363 & 2046 & 2374 & 2116 \\
600 & 2231 & 1984 & 2724 & 2377 & 2842 & 2483 & 2878 & 2470 & 2883 & 2541 \\
700 & 2387 & 2066 & 3141 & 2775 & 3337 & 2930 & 3388 & 2934 & 3391 & 3003 \\
800 & 2552 & 2253 & 3392 & 3044 & 3739 & 3352 & 3782 & 3345 & 3825 & 3328 \\
900 & 2760 & 2427 & 3666 & 3205 & 4277 & 3681 & 4283 & 3693 & 4285