A new hybrid genetic algorithm for the collection scheduling problem for a satellite constellation

References

• Agnese, J. C., & Bensana, E. (1995). Exact and approximate methods for the daily management of an earth observation satellite. Proceeding of the fifth ESA workshop on artificial intelligence and knowledge based systems for space.
   Google Scholar
• Augenstein, S., Estanislao, A., Guere, E., & Blaes, S. (2016). Optimal scheduling of a constellation of earth-imaging satellites, for maximal data throughput and efficient human management. Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling.
   Google Scholar
• Baek, S.-W., Han, S.-M., Cho, K.-R., Lee, D.-W., Yang, J.-S., Bainum, P.-M., & Kim, H.-D. (2011). Development of a scheduling algorithm and GUI for autonomous satellite missions. Acta Astronautica, 68(7–8), 1396–1402. doi:10.1016/j.actaastro.2010.08.011
   Web of Science ®Google Scholar
• Barbulescu, L., Watson, J.-P., Whitley, L. D., & Howe, A. E. (2004). Scheduling space-ground communications for the air force satellite control network. Journal of Scheduling, 7(1), 7–34. doi:10.1023/B:JOSH.0000013053.32600.3c
   Web of Science ®Google Scholar
• Benoist, T., & Rottembourg, B. (2004). Upper bounds for revenue maximization in a satellite scheduling problem. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2(3), 235–249. doi:10.1007/s10288-004-0044-8
   Google Scholar
• Bensana, E., Verfaillie, G., Agnese, J. C., Bataille, N., & Blumestein, D. (1996). Exact and inexact methods for the daily management of an earth observation satellite. Proceeding of the international symposium on space mission operations and ground data systems, 4, pp. 507–514.
   Google Scholar
• Berger, J., Barkaoui, M., & Boukhtouta, A. (2007). A hybrid genetic approach for airborne sensor vehicle routing in real-time reconnaissance missions. Journal of Aerospace Science and Technology, 11(4), 317–326. Volume Issue doi:10.1016/j.ast.2006.12.006
   Web of Science ®Google Scholar
• Bianchessi, N., Cordeau, J. F., Desrosiers, J., Laporte, G., & Raymond, V. (2007). A heuristic for the multi-satellite, multi-orbit and multi-user management of earth observation satellites. European Journal of Operational Research, 177(2), 750–762. doi:10.1016/j.ejor.2005.12.026
   Google Scholar
• Bianchessi, N., Piuoi, V., Righini, G., Roveri, M., Laneve, G., & Zigrino, A. (2004). An optimization approach to the planning of earth observing satellites. Proceeding of the fourth international workshop on planning and scheduling for space (IWPSS’04).
   Google Scholar
• Bianchessi, N., & Righini, G. (2006). A mathematical programming algorithm for planning and scheduling an earth observing SAR constellation. Proceeding of the fifth international workshop on planning and scheduling for space (IWPSS’06).
   Google Scholar
• Bianchessi, N., & Righini, G. (2008). Planning and scheduling algorithms for the COSMOSkyMed constellation. Aerospace Science and Technology, 12(7), 535–544. doi:10.1016/j.ast.2008.01.001
   Web of Science ®Google Scholar
• Butler, P. J. (2005). Project polar epsilon: Joint space-based wide area surveillance and support capability. Proceedings of the 2005 IEEE International Geoscience and Remote Sensing, Symposium (IGARSS), Vol. 2, pp. 1194.
   Google Scholar
• Chen, X., Reinelt, G., Dai, G., & Wang, M. (2018). Priority-based and conflict-avoidance heuristics for multi-satellite scheduling. Applied Soft Computing, 69, 177–191. doi:10.1016/j.asoc.2018.04.021
   Web of Science ®Google Scholar
• Chu, X., Chen, Y., & Lining, X. (2017a). A branch and bound algorithm for agile earth observation satellite scheduling. Discrete Dynamics in Nature and Society, 2017, 1. Article ID 7345941, doi:10.1155/2017/7345941
   Web of Science ®Google Scholar
• Chu, X., Chen, Y., & Tan, Y. (2017b). An anytime branch and bound algorithm for agile earth observation satellite onboard scheduling. Advances in Space Research, 60(9), 2077–2090. doi:10.1016/j.asr.2017.07.026
   PubMed Web of Science ®Google Scholar
• Gabrel, V. (2006). Strengthened 0-1 linear formulation for the daily satellite mission planning. Journal of Combinatorial Optimization, 11(3), 341–346. doi:10.1007/s10878-006-7912-4
   Web of Science ®Google Scholar
• Gabrel, V., Moulet, A., Murat, C., & Paschos, V. T. (1997). A new single model and derived algorithms for the satellite shot planning problem using graph theory concepts. Annals of Operations Research, 69, 115–134. doi:10.1023/A:1018920709696
   Web of Science ®Google Scholar
• Gabrel, V., & Murat, C. (2003). Mathematical programming for earth observation satellite mission planning. In: Ciriani TA, Fasano G, Gliozzi S, Tadei R, editors. Operations research in space and air. New York: Springer.
   Google Scholar
• Gabrel, V., & Vanderpooten, D. (2002). Enumeration and interactive selection of efficient paths in a multiple criteria graph for scheduling an earth observing satellite. European Journal of Operational Research., 139(3), 533–542. doi:10.1016/S0377-2217(01)00188-6
   Web of Science ®Google Scholar
• Galceran, E., & Carreras, E. (2013). A survey on coverage path planning for robotics. Robotics and Autonomous Systems. 61(12), 1258–1276. doi:10.1016/j.robot.2013.09.004
   Google Scholar
• Globus, A., Crawford, J., Lohn, J., & Morris, R. (2002). Scheduling earth observing fleets using evolutionary algorithms: Problem description and approach. Proceeding of the third international NASA workshop on planning and scheduling for space.
   Google Scholar
• Globus, A., Crawford, J., Lohn, J., & Pryor, A. (2003). A comparison of techniques for scheduling fleets of earth-observing satellites. Journal of the Operational Research Society, 56(8), 962–968.
   Google Scholar
• Habet, D. (2009). Tabu search to solve real-life combinatorial optimization problems: A case of study. In: Abraham A, Hassanien AE, Carvalho AP, editors. Foundations of computational intelligence (pp. 129–151). New York: Springer.
   Google Scholar
• Habet, D., & Vasquez, M. (2004). Solving the selecting and scheduling satellite photographs problem with a consistent neighborhood heuristic. Proceeding of the sixteenth IEEE international conference on tools with artificial intelligence (ICTAI’04).
   Google Scholar
• Habet, D., Vasquez, M., & Vimont, Y. (2010). Bounding the optimum for the problem of scheduling the photographs of an agile earth observing satellite. Computational Optimization and Applications, 47(2), 307–333. doi:10.1007/s10589-008-9220-7
   Web of Science ®Google Scholar
• Hall, N. G., & Magazine, M. J. (1994). Maximizing the value of a space mission. European Journal of Operational Research, 78(2), 224–241. doi:10.1016/0377-2217(94)90385-9
   Web of Science ®Google Scholar
• Lemaître, M., Verfaillie, G., Jouhaud, F., Lachiver, J. M., & Bataille, N. (2000). How to manage the new generation of agile earth observation satellites. Proceeding of the international symposium on artificial intelligence, robotics and automation in space (ISAIRAS’00).
   Google Scholar
• Lemaître, M., Verfaillie, G., Jouhaud, F., Lachiver, J. M., & Bataille, N. (2002). Selecting and scheduling observations of agile satellites. Aerospace Science and Technology, 6, 367–381. doi:10.1016/S1270-9638(02)01173-2
   Web of Science ®Google Scholar
• Li, Y., Wang, R., & Xu, M. (2014). Rescheduling of observing spacecraft using fuzzy neural network and ant colony algorithm. Chinese Journal of Aeronautics, 27, 678–687. doi:10.1016/j.cja.
   Web of Science ®Google Scholar
• Li, Y., Xu, M., & Wang, R. (2007). Scheduling observations of agile satellites with combined genetic algorithm. Proceedings of the 3rd international conference on natural computation (ICNC 2007): Vol. 3, pp. 29–33, Haikou, China.
   Google Scholar
• Liao, D., & Tang, Y. (2005). Satellite imaging order scheduling with stochastic weather condition forecast. Proceeding of the IEEE international conference on systems, man and cybernetics, Vol. 3, pp. 2524–2529.
   Google Scholar
• Liao, D.-Y., & Yang, Y.-T. (2007). Imaging order scheduling of an earth observation satellite. IEEE Transactions on Systems, Man and Cybernetics, Part C (Applications and Reviews), 37(5), 794–802. doi:10.1109/TSMCC.2007.900668
   PubMed Web of Science ®Google Scholar
• Lin, W., & Chang, S. (2005). Hybrid algorithms for satellite imaging scheduling. Proceeding of the IEEE international conference on systems, man and cybernetics, Vol. 3, pp. 2518–2523.
   Google Scholar
• Lin, W., & Liao, D. (2004). A tabu search algorithm for satellite imaging scheduling. Proceeding of the IEEE international conference on systems, man and cybernetics, Vol. 2, pp. 1601–1606.
   Google Scholar
• Lin, W., Liao, D., Liu, C., & Lee, Y. (2005). Daily Imaging Scheduling of an Earth Observation Satellite. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 35(2), 213–223. doi:10.1109/TSMCA.2005.843380
   Web of Science ®Google Scholar
• Lin, W., Liu, C., Liao, D., & Lee, Y. (2003). Daily imaging scheduling of an earth observation satellite. Proceeding of the IEEE international conference on systems, man and cybernetics, Vol. 2, pp. 1886–1891.
   Google Scholar
• Luo, K., Wang, H., Li, Y., & Li, Q. (2017). High-performance technique for satellite range scheduling. Computers & Operations Research, 85, 12–21. doi:10.1016/j.cor.2017.03.012
   Web of Science ®Google Scholar
• Maillard, A., Verfaillie, G., Pralet, C., Jaubert, J., & Lhermitte, J. (2016). Adaptable data download schedules for agile earth-observing satellites. Journal of Aerospace Computing, Information and Communication, 13 (8), 280–300.
   Google Scholar
• Mansour, M. A. A., & Dessouky, M. M. (2010). A genetic algorithm approach for solving the daily photograph selection problem of the SPOT5 satellite. Computers & Industrial Engineering, 58(3), 509–520. doi:10.1016/j.cie.2009.11.012
   Web of Science ®Google Scholar
• Marinelli, F., Nocella, S., Rossi, F., & Smriglio, S. (2011). A Lagrangian heuristic for satellite range scheduling with resource constraints. Computers & Operations Research, 38(11), 1572–1583. doi:10.1016/j.cor.2011.01.016
   Web of Science ®Google Scholar
• Nelson, F. (2012). Scheduling optimization for imagery satellite constellations using column generation, PhD Thesis, George Mason University, Department of Systems Engineering and Operations Research, Volgenau School of Engineering.
   Google Scholar
• Niu, X., Tang, H., & Wu, L. (2018). Multi-satellite observation scheduling for large area disaster emergency response. ISPRS—International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 42, 1327–1331. doi:10.5194/isprs-archives-XLII-3-1327-2018
   Google Scholar
• Niu, X., Tang, H., Wu, L., Deng, R., & Zhai, X. (2015). Imaging-duration embedded dynamic scheduling of earth observation satellites for emergent events. Mathematical Problems in Engineering, 2015, 1. doi:10.1155/2015/731734
   Web of Science ®Google Scholar
• Osman, I. H. (1993). Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Annals of Operations Research, 41(4), 421–451. doi:10.1007/BF02023004
   Google Scholar
• Pinto, M., Barros, A., Noomen, R., Gelder, P., & Tessensohn, T. (2018). A new model proposal for integrated satellite constellation scheduling within a planning horizon given operational constraints. Proceedings of the 7th International Conference on Operations Research and Enterprise Systems, pp. 312–319.
   Google Scholar
• Qiu, D., He, C., Liu, J., & Ma, M. (2013). A dynamic scheduling method of earth-observing satellites by employing rolling horizon strategy. The Scientific World Journal, doi:10.1155/2013/304047
   Web of Science ®Google Scholar
• Sarkheyli, A., Vaghei, B. G., & Bagheri, A. (2010). New tabu search heuristic in scheduling earth observation satellites. Proceeding of the second international conference on software technology and engineering (ICSTE’10).
   Google Scholar
• Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In M. Maher and J.-F. Puget (Eds.) Principles and practice of constraint programming, lecture notes in computer science (pp. 417–431). New York: Springer-Verlag.
   Google Scholar
• Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254–265. doi:10.1287/opre.35.2.254
   Web of Science ®Google Scholar
• Soma, P., Venkateswarlu, S., Santhalakshmi, S., Bagchi, T., & Kumar, S. (2004). Multi-satellite scheduling using genetic algorithms. Proceeding of the eighth international conference on space operations (SpaceOps’04).
   Google Scholar
• Song, Y., Huang, D., Zhou, Z., & Chen, Y. (2018). An emergency task autonomous planning method of agile imaging satellite. Journal of Image and Video Processing, 2018, 2–11. doi:10.1186/s13640-018-0268-8
   Web of Science ®Google Scholar
• Spangelo, S., Cutler, J., Gilson, K., & Cohn, A. (2015). Optimization-based scheduling for the single-satellite, multi-ground station communication problem. Computers & Operations Research, 57, 1–16. doi:10.1016/j.cor.2014.11.004
   Web of Science ®Google Scholar
• Tangpattanakul, P., Jozefowiez, N., & Lopez, P. (2012). Multi-objective optimization for selecting and scheduling observations. In C.A. Coello, V. Cutello, K. Deb, S. Forrest, G. Nicosia, & M. Pavone (Eds.) Lecture notes in computer science. New York: Springer.
   Google Scholar
• Toth, P., & Vigo, D. (2014). Vehicle routing: Problems, methods, and applications (2nd ed.). Philadelphia, PA: Society for Industrial and Applied Mathematics.
   Google Scholar
• Vasquez, M., & Hao, J. (2001). A logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite. Computational Optimization and Applications, 20(2), 137–157. doi:10.1023/A:1011203002719
   Web of Science ®Google Scholar
• Vasquez, M., & Hao, J. (2003). Upper bounds for the SPOT 5 daily photograph scheduling problem. Journal of Combinatorial Optimization, 7(1), 87–103. doi:10.1023/A:1021950608048
   Web of Science ®Google Scholar
• Vazquez, A. J., & Erwin, R. S. (2015). An introduction to optimal satellite range scheduling. New York: Springer.
   Google Scholar
• Verfaillie, G. (2013). Planning and scheduling activities for earth surveillance and observation satellites: A constraint-based perspective, ICAPS 2013 Summer School, Perugia, Italy.
   Google Scholar
• Verfaillie, G., & Lemaître, M. (2006). Tutorial on Planning Activities for Earth Watching and Observation satellites and Constellations: from Off-line Ground Planning to On-line On-board Planning, ICAPS 2006, The English Lake District, Cumbria, UK (http://icaps06.icaps-conference.org/).
   Google Scholar
• Verfaillie, G., Lemaître, M., & Schiex, T. (1996). Russian doll search for solving constraint optimization problems. Proceeding of the thirteenth national conference on Artificial intelligence (AAAI’96); pp. 181–187.
   Google Scholar
• Verfaillie, G., & Schiex, T. (1994). Solution reuse in dynamic constraint satisfaction problems. Proceeding of the twelfth national conference on artificial intelligence (AAAI’94), pp. 307–312.
   Google Scholar
• Wall, M. (1995). GAlib - A C++ Genetic Algorithms Library, Version 2.4, MIT, Boston.
   Google Scholar
• Wang, H., Xu, M., Wang, R., & Li, Y. (2009). Scheduling earth observing satellites with hybrid ant colony optimization algorithm. Proceeding of the international conference on artificial intelligence and computational intelligence (AICI’09).
   Google Scholar
• Wang, J., Demeulemeester, E., Dishan, Q., & Liu, J. (2015a). Exact and Inexact Scheduling Algorithms for Multiple Earth Observation Satellites Under Uncertainties of Clouds. SSRN: https://ssrn.com/abstract=2634934 or doi:10.2139/ssrn.2634934.
   Google Scholar
• Wang, J., Demeulemeester, E., & Qiu, D. (2014). A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds. Computers & Operations Research, 74, 1–13. doi:10.1016/j.cor.2016.04.014
   Web of Science ®Google Scholar
• Wang, J., Jing, N., Li, J., & Chen, Z. H. (2007). A multi-objective imaging scheduling approach for earth observing satellites. Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (GECCO ’07), pp. 2211–2218, London, UK.
   Google Scholar
• Wang, J., Zhu, X., Yang, T., Zhu, J., & Ma, M. (2015b). Towards dynamic real-time scheduling for multiple earth observation satellites. Journal of Computer and System Sciences, 81(1), 110–124. doi:10.1016/j.jcss.2014.06.016
   Web of Science ®Google Scholar
• Wang, Y., Sheng, M., Zhuang, S., Zhang, S., Zhang, N., Liu, R., & Li, J. (2018). Multi-resource coordinate scheduling for earth observation. IEEE Journal on Selected Areas in Communications, 36 (2), 268–279.
   Web of Science ®Google Scholar
• Wolfe, J., & Stephen, S. E. (2000). Three scheduling algorithms applied to the earth observing systems domain. Management Science, 46(1), 148–168. doi:10.1287/mnsc.46.1.148.15134
   Web of Science ®Google Scholar
• Wu, G., Liu, J., Ma, M., & Dishan, Q. (2013). A two-phase scheduling method with the consideration of task clustering for earth observing satellites. Computers and Operations Research, 40(7), 1884–1894. doi:10.1016/j.cor.2013.02.009
   Web of Science ®Google Scholar
• Zhai, X., Niu, X., Tang, H., Wu, L., & Shen, Y. (2015). Robust satellite scheduling approach for dynamic emergency tasks. Mathematical Problems in Engineering, 2015, 1. doi:10.1155/2015/482923
   Web of Science ®Google Scholar
• Zufferey, N., Amstutz, P., & Giaccari, P. (2008). Graph colouring approaches for a satellite range scheduling problem. Journal of Scheduling, 11(4), 263–277. doi:10.1007/s10951-008-0066-8
   Web of Science ®Google Scholar