A heuristic for the multi-satellite, multi-orbit and multi-user management of Earth observation satellites. (English) Zbl 1102.90327
Summary: Earth observation satellites are platforms equipped with optical instruments that orbit the Earth in order to take photographs of specific areas at the request of users. This article is concerned with the management of several satellites performing multiple orbits over a given planning horizon. It describes a tabu search heuristic for the problem of selecting and scheduling the requests to be satisfied, under operational constraints. An upper bounding procedure based on column generation is used to evaluate the quality of the solutions. The results of extensive computational experiments performed on data provided by the French Centre National d’Études Spatiales are reported.
MSC:
| 90B40 | Search theory |
Keywords:
earth observation satellites; multiple orbits; multiple users; tabu search heuristic; column generationReferences:
| [1] | Barnhart, C.; Johnson, E. L.; Nemhauser, G. L.; Savelsbergh, M. W.P.; Vance, P. H., Branch-and-price: Column generation for solving integer programs, Operations Research, 46, 316-329 (1998) · Zbl 0979.90092 |
| [2] | Bataille, N., Lemaître, M., Verfaillie, G., 1999. Efficiency and fairness when sharing the use of a satellite. In: Proceedings of the 5th International Symposium on Artificial Intelligence, Robotics and Automation in Space, Noordwijk, pp. 465-470.; Bataille, N., Lemaître, M., Verfaillie, G., 1999. Efficiency and fairness when sharing the use of a satellite. In: Proceedings of the 5th International Symposium on Artificial Intelligence, Robotics and Automation in Space, Noordwijk, pp. 465-470. |
| [3] | Bensana, E.; Lemaître, M.; Verfaillie, G., Earth observation satellite management, Constraints, 4, 293-299 (1999) · Zbl 0963.90507 |
| [4] | Cordeau, J.-F.; Laporte, G., Maximizing the value of an Earth observation satellite orbit, Journal of the Operational Research Society, 56, 962-968 (2005) · Zbl 1274.86025 |
| [5] | Desaulniers, G.; Desrosiers, J.; Ioachim, I.; Solomon, M. M.; Soumis, F.; Villeneuve, D., A unified framework for deterministic time constrained vehicle routing and crew scheduling problems, (Crainic, T. G.; Laporte, G., Fleet Management and Logistics (1998), Kluwer: Kluwer Norwell, MA), 57-93 · Zbl 0966.90007 |
| [6] | Ehrgott, M., Multicriteria Optimization, Lecture Notes in Economics and Mathematical Systems, vol. 491 (2000), Springer: Springer New York · Zbl 0956.90039 |
| [7] | Gabrel, V.; Murat, C., Mathematical programming for earth observation satellite mission planning, (Ciriani, T.; Fasano, G.; Gliozzi, S.; Tadei, R., Operations Research in Space and Air (2003), Kluwer: Kluwer Boston), (Chapter 7) · Zbl 1051.90533 |
| [8] | Harrison, S.A., Philpott, M.S., Price, M.E., 1999. Task scheduling for satellite based imagery. In: Proceedings of the 18th Workshop of the UK Planning and Scheduling Special Interest Group, University of Salford, UK, pp. 64-78.; Harrison, S.A., Philpott, M.S., Price, M.E., 1999. Task scheduling for satellite based imagery. In: Proceedings of the 18th Workshop of the UK Planning and Scheduling Special Interest Group, University of Salford, UK, pp. 64-78. |
| [9] | Lemaître, M., Verfaillie, G., Bataille, N., 1999. Exploiting a common property resource under a fairness constraint: A case study. In: Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99), Stockholm, pp. 206-211.; Lemaître, M., Verfaillie, G., Bataille, N., 1999. Exploiting a common property resource under a fairness constraint: A case study. In: Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99), Stockholm, pp. 206-211. |
| [10] | Lemaître, M.; Verfaillie, G.; Jouhaud, F.; Lachiver, J.-M.; Bataille, N., Selecting and scheduling observations of agile satellites, Aerospace Science and Technology, 6, 367-381 (2002) |
| [11] | Lemaître, M., Verfaillie, G., Fargier, H., Lang, J., Bataille, N., Lachiver, J.-M., 2003. Equitable allocation of earth observing satellites resources. In: Proceedings on the 5th ONERA-DLR Aerospace Symposium (ODAS’03) Toulouse.; Lemaître, M., Verfaillie, G., Fargier, H., Lang, J., Bataille, N., Lachiver, J.-M., 2003. Equitable allocation of earth observing satellites resources. In: Proceedings on the 5th ONERA-DLR Aerospace Symposium (ODAS’03) Toulouse. |
| [12] | Morris, R. A.; Bresina, J. L.; Rodgers, S. M., Automatic generation of heuristics for scheduling, (Pollack, M., Proceedings of the 15th International Joint Conference on Artificial Intelligence (1997), Morgan Kaufmann: Morgan Kaufmann Nagoya), 1260-1266 |
| [13] | Moulin, H., Axioms of Cooperative Decision Making (1988), Cambridge University Press: Cambridge University Press Cambridge, MA · Zbl 0699.90001 |
| [14] | Pemberton, J., 2000. Towards scheduling over-constrained remote-sensing satellites. In: Proceedings of the 2nd NASA International Workshop on Planning and Scheduling for Space, San Francisco, pp. 84-89.; Pemberton, J., 2000. Towards scheduling over-constrained remote-sensing satellites. In: Proceedings of the 2nd NASA International Workshop on Planning and Scheduling for Space, San Francisco, pp. 84-89. |
| [15] | Vasquez, M.; Hao, J.-K., A logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an Earth observation satellite, Computational Optimization and Applications, 20, 137-157 (2001) · Zbl 0983.90082 |
| [16] | Vasquez, M.; Hao, J.-K., Upper bounds for the SPOT 5 daily photograph scheduling problem, Journal of Combinatorial Optimization, 7, 87-103 (2003) · Zbl 1046.90030 |
| [17] | Verfaillie, G., Lemaître, M., 2001. Selecting and scheduling observations for agile satellites: Some lessons from the constraint reasoning community point of view. In: Walsh, T. (Ed.), Principles and Practice of Constraint Programming (CP-2001), Paphos, Cyprus, pp. 670-684.; Verfaillie, G., Lemaître, M., 2001. Selecting and scheduling observations for agile satellites: Some lessons from the constraint reasoning community point of view. In: Walsh, T. (Ed.), Principles and Practice of Constraint Programming (CP-2001), Paphos, Cyprus, pp. 670-684. · Zbl 1067.68680 |
| [18] | Verfaillie, G., Lemaître, M., Bataille, N., Lachiver, J.-M., 2002a. Management of the mission of Earth observation satellites. Challenge description, Technical report, Centre National d’Études Spatiales, France.; Verfaillie, G., Lemaître, M., Bataille, N., Lachiver, J.-M., 2002a. Management of the mission of Earth observation satellites. Challenge description, Technical report, Centre National d’Études Spatiales, France. |
| [19] | Verfaillie, G., Lemaître, M., Bataille, N., Lachiver, J.-M., 2002b. Management of the mission of Earth observation satellites. Informal description of the global problem, Technical report, Centre National d’Études Spatiales, France.; Verfaillie, G., Lemaître, M., Bataille, N., Lachiver, J.-M., 2002b. Management of the mission of Earth observation satellites. Informal description of the global problem, Technical report, Centre National d’Études Spatiales, France. |
| [20] | Wolfe, W. J.; Sorensen, S. E., Three scheduling algorithms applied to the Earth observing systems domain, Management Science, 46, 148-168 (2000) · Zbl 1231.90286 |
| [21] | Yager, R., On ordered weighted averaging aggregation operators in multicriteria decision making, IEEE Transactions on Systems Man and Cybernetics, 18, 183-190 (1988) · Zbl 0637.90057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
