面向收益不均等区域目标的多星调度问题

doi:10.3969/j.issn.1001-506X.2020.03.018

摘要/Abstract

摘要：

利用多星对区域目标的协同观测在工程应用方面的需求日益复杂化,当目标区域内待观测目标的重要性不同,其对应的观测收益不同。那么如何在资源有限的情况下,安排观测方案使观测总收益最大是亟待解决的问题。考虑区域目标内部观测收益不均等的实际情况,建立了区域目标内部收益随时间可变的多星调度优化模型,设计了条带动态分割方法(dynamic stripe segmentation method, DSSM),提出了基于权重优先策略的启发式算法(weight priority strategy heuristic, WPSH)和基于随机邻域的局部搜索算法(random neighborhood local search, RNLS),使求解结果对应的观测收益最大,最后通过仿真实验验证DSSM算法比并行分割算法观测收益提高约19%,覆盖率提高约22%;RNLS算法比WPSH算法的基础上平均提升观测收益约4.5%,且求解质量较稳定。

关键词: 多星调度, 区域目标, 动态分割, 权重策略

Abstract:

The need for collaborative observation of multi-satellite regional targets is becoming increasingly complex in engineering applications. However, due to differences in geological structure and character activities in a target to be observed, the importance of the targets to be observed in the target is different, the corresponding observed returns are different. How to arrange the observation program to maximize the total benefit of the observation is a problem that needs to be solved in the case of limited resources. In this paper, considering the actual situation of unequal internal observation income of regional targets, a multi-satellite scheduling optimization model with variable internal income of regional targets is established. The dynamic stripe segmentation method (DSSM) is designed and proposed based on weights. The weight priority strategy heuristic (WPSH) and the random neighborhood local search (RNLS) algorithm maximize the observation benefit corresponding to the solution result. Finally, the simulation experiment proves that the DSSM algorithm improves the observation yield by about 19% and the coverage rate by about 22%. The RNLS algorithm is about 4.5% higher than the WPSH algorithm, and the solution quality is stable.

Key words: multi-satellite scheduling, regional target, dynamic segmentation, weight strategy

中图分类号:

姚靖宇, 靳鹏, 朱外明, 胡笑旋. 面向收益不均等区域目标的多星调度问题[J]. 系统工程与电子技术, 2020, 42(3): 638-645.

Jingyu YAO, Peng JIN, Waiming ZHU, Xiaoxuan HU. Multi-satellite scheduling problem for regional targets with uneven income[J]. Systems Engineering and Electronics, 2020, 42(3): 638-645.

图/表 13

图1

图2

图3

图4

表1

表2

表3

表4

图5

图6

表5

表6

图7

参考文献 31

1	WANG P, GAO P, TAN Y. A model, a heuristic and a decision support system to solve the earth observing satellites fleet scheduling problem[C]//Proc.of the International Conference on Computers & Industrial Engineering, 2009: 322-335.
2	AGN J C , BATAILLE N , BLUMSTEIN D , et al. Exact and approximate methods for the daily management of an earth observation satellite[J]. RAIRO Operations Research, 2007, 41 (4): 381- 398. doi: 10.1051/ro:2007035
3	TANGPATTANAKUL P , JOZEFOWIEZ N , LOPEZ P . Biased random key genetic algorithm for multiuser Earth observation scheduling[J]. In Recent Advances in Computational Optimization, 2015, 201 (5): 143- 160.
4	TANGPATTANAKUL P , JOZEFOWIEZ N , LOPEZ P . A multi-objective local search heuristic for scheduling Earth observations taken by an agile satellite[J]. European Journal of Operational Research, 2015, 245 (2): 542- 554.
5	何苗, 贺仁杰. 考虑云层遮挡的敏捷成像卫星调度方法研究[J]. 科学技术与工程, 2013, 13 (28): 8373- 8379. doi: 10.3969/j.issn.1671-1815.2013.28.027
	HE M , HE R J . Research on agile imaging satellite scheduling method considering cloud occlusion[J]. Science Technology and Engineering, 2013, 13 (28): 8373- 8379. doi: 10.3969/j.issn.1671-1815.2013.28.027
6	WANG J , DEMEULEMEESTER E , QIU D . A pure proactive scheduling algorithm for multiple earth observation satellites under uncertainties of clouds[J]. Computers & Operations Research, 2016, 74 (C): 1- 13.
7	WANG X W , CHEN Z , HAN C . Scheduling for single agile satellite, redundant targets problem using complex networks theory[J]. Chaos Solitons & Fractals, 2016, 83 (20): 125- 132.
8	姜维, 庞秀丽, 郝会成. 成像卫星协同任务规划模型与算法[J]. 系统工程与电子技术, 2013, 35 (10): 2093- 2101. doi: 10.3969/j.issn.1001-506X.2013.10.13
	JIANG W , PANG X L , HAO H C . Model and algorithm of imaging satellite cooperative task planning[J]. Systems Engineering and Electronics, 2013, 35 (10): 2093- 2101. doi: 10.3969/j.issn.1001-506X.2013.10.13
9	阮启明.面向区域目标的成像侦察卫星调度问题研究[D].长沙:国防科学技术大学, 2006.
	RUAN Q M. Research on imaging reconnaissance satellite scheduling problem for regional targets[D].Changsha: National University of Defense Technology, 2006.
10	WALTON J . Models for the management of satellite-based sensors[J]. Massachusetts Institute of Technology, 1993, 15 (5): 23- 30.
11	LEMAIÎTRE M , GÉRARD V , JOUHAUD F , et al. Selecting and scheduling observations of agile satellites[J]. Aerospace Science and Technology, 2002, 6 (5): 367- 381. doi: 10.1016/S1270-9638(02)01173-2
12	白国庆, 白保存, 徐一帆, 等. 多星协同对区域目标观测的动态划分方法[J]. 测绘科学, 2010, 35 (6): 32- 34.
	BAI G Q , BAI B C , XU Y F , et al. Dynamic partitioning method for multi-satellite coordination on regional target observation[J]. Journal of Surveying and Mapping, 2010, 35 (6): 32- 34.
13	李曦.多星区域观测任务的效率优化方法研究[D].长沙:国防科学技术大学, 2005.
	LI X. Research on efficiency optimization method of multi-satellite observation mission[D].Changsha: National University of Defense Technology, 2005.
14	阮启明, 谭跃进, 李菊芳, 等. 对地观测卫星的区域目标分割与优选问题研究[J]. 测绘科学, 2006, 31 (1): 98- 100. doi: 10.3771/j.issn.1009-2307.2006.01.034
	RUAN Q M , TAN Y J , LI J F , et al. Research on regional target segmentation and optimization of Earth observation satellites[J]. Journal of Surveying and Mapping, 2006, 31 (1): 98- 100. doi: 10.3771/j.issn.1009-2307.2006.01.034
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[J]. Computational Optimization and Applications, 2001, 20 (2): 137- 157. doi: 10.1023/A:1011203002719
16	BENSANA E, VERFAILLIE Y, AGNESE J, et al. Exact and inexact methods for the daily management of Earth observation satellite[C]//Proc.of the 5th Space Symposium on Space Mission Operations and Ground Data Systems, 1996: 394-507.
17	BENSANA E , LEMAITRE M , VERFAILLIE G . Earth observation satellite management[J]. Constraints, 1999, 4 (3): 293- 299. doi: 10.1023/A:1026488509554
18	VERFAILLIE G, LEMAITRE M, SCHIEX T. Russian doll search for solving constraint optimization problems[C]//Proc.of the 13th National Conference on Artificial Intelligence 1996, 1: 181-187.
19	WU G , LIU J , MA M , et al. A two-phase scheduling method with the consideration of task clustering for earth observing satellites[J]. Computers & Operations Research, 2013, 40 (7): 1884- 1894.
20	VASQUEZ M , HAO J K . Upper bounds for the SPOT 5 daily photograph scheduling problem[J]. Journal of Combinatorial Optimization, 2003, 7 (1): 87- 103. doi: 10.1023/A:1021950608048
21	ZHU W M , HU X X , XIA W , et al. A two-phase genetic annealing method for integrated Earth observation satellite scheduling problems[J]. Soft Computing, 2019, 23 (1): 181- 196. doi: 10.1007/s00500-017-2889-8
22	LIU X L , BAI B C , CHEN Y W , et al. Multi satellites scheduling algorithm based on task merging mechanism[J]. Applied Mathematics and Computation, 2014, 230, 687- 700. doi: 10.1016/j.amc.2013.12.109
23	BIANCHESSI N , CORDEAU J , DESROSIERS J , et al. Aheuristic for the multi-satellite, multi-orbit and multi-user management of earth observation satellites[J]. European Journal of Operational Research, 2007, 177 (2): 750- 762.
24	GLOBUS A , CRAWFORD J , LOHN J , et al. A comparison of techniques for scheduling fleets of earth-observing[J]. Journal of the Operational Research Society, 2003, 56 (8): 962- 968.
25	GLOBUS A , CRAWFORD J , LOHN J , et al. Scheduling earth observing satellites with evolutionary algorithms[J]. Proceedings of the Conference on Space Mission Challenges for Information Technology (SMC-IT), 2003, 45 (4): 15- 27.
26	BARBULESCU L , HOWE A , WHITLEY D . AFSCN scheduling: how the problemand solution have evolved[J]. Mathematical and Computer Modelling, 2006, 43 (9/10): 1023- 1037.
27	FLORIO S. Performances optimization of remote sensing satellite constellations: a heuristic method[C]//Proc.of the 5th InterNational Workshop on Planning and Scheduling for Space, 2006: 567-578.
28	ZUFFEREY N , AMSTUTZ P , GIACCARI P . Graph colouring approaches for asatellite range scheduling problem[J]. Journal of Scheduling, 2008, 11 (4): 263- 277. doi: 10.1007/s10951-008-0066-8
29	HABET D , VASQUEZ M , VIMONT Y . Bounding the optimum for the problem of scheduling the photographs of an agile earth observing satellite[J]. Computational Optimization and Applications, 2010, 47 (2): 307- 333. doi: 10.1007/s10589-008-9220-7
30	WOLFE W J , SORENSEN S E . Three scheduling algorithms applied to the earth observing systems domain[J]. Management Science, 2000, 46 (1): 148- 166. doi: 10.1287/mnsc.46.1.148.15134
31	WANG X W , CHEN Z , HAN C . Scheduling for single agile satellite, redundant targets problem using complex networks theory[J]. Chaos Solitons & Fractals, 2016, 8 (3): 125- 132.

位置点	经度/(°)	纬度/(°)	面积/km²
左上角	110	20	408 750
右上角	114	20
右下角	114	24
左下角	110	24

卫星名称	卫星国际编号	载荷分辨率(全色)/m	幅宽/km
GAOFEN 2	2014-049A	2	66
GAOFEN 3	2016-059A	2.5	65
YAOGAN 15	2012-029A	0.5	60
YAOGAN 16A	2012-066A	0.8	60
YAOGAN 17A	2013-046A	2	60
YAOGAN 18	2013-059A	0.5	55

传感器名	日期	时间窗开始时间	时间窗结束时间	持续时间/s
Sensor4	11Jan 2019	1:58:22	2:00:01	99
Sensor6	11Jan 2019	2:40:07	2:41:12	65
Sensor2	11Jan 2019	10:28:48	10:29:52	64
Sensor5	11Jan 2019	11:46:56	11:48:11	75
Sensor1	11Jan 2019	15:12:47	15:13:56	69
Sensor4	11Jan 2019	15:37:05	15:37:45	40
Sensor3	11Jan 2019	19:08:35	19:09:59	84
Sensor2	11Jan 2019	22:45:45	22:46:58	73
Sensor5	12Jan 2019	1:24:44	1:26:14	90
Sensor6	13Jan 2019	14:06:13	14:07:20	67
Sensor4	14Jan 2019	1:20:38	1:22:10	92
Sensor1	14Jan 2019	3:51:15	3:52:22	67
Sensor5	14Jan 2019	11:08:57	11:10:27	90
Sensor5	15Jan 2019	0:46:52	0:48:15	83
Sensor3	15Jan 2019	7:47:56	7:49:16	80
Sensor3	16Jan 2019	7:31:57	7:33:13	76
Sensor2	16Jan 2019	10:21:56	10:23:09	73
Sensor1	16Jan 2019	15:16:31	15:17:40	69
Sensor2	16Jan 2019	22:38:58	22:40:06	68

算例	卫星数量	单元格数量	观测条带数量	时间/s	观测收益	覆盖率/%
R01	3	10×10	4 870	10	743	55.00
R02	3	12×12	20 140	25	1 135	63.89
R03	3	14×14	64 540	64	1 422	70.92
R04	3	16×16	234 470	180	1 928	78.52
R05	3	18×18	466 280	242	2 330	82.10
R06	3	20×20	1 083 360	706	3 056	82.75
R07	4	10×10	6 331	12	832	68.00
R08	4	12×12	26 182	27	1 317	77.08
R09	4	14×14	83 902	67	1 648	77.55
R10	4	16×16	304 811	192	2 262	89.45
R11	4	18×18	606 164	481	2 689	90.74
R12	4	20×20	1 408 368	980	3 342	92.00
R13	5	10×10	8 279	14	871	81.00
R14	5	12×12	34 238	33	1 406	86.11
R15	5	14×14	109 718	85	1 886	88.27
R16	5	16×16	398 599	248	2 507	95.30
R17	5	18×18	792 676	655	2 830	95.30
R18	5	20×20	1 841 712	1 228	3 564	97.53
R19	6	10×10	9 253	19	949	82.00
R20	6	12×12	38 299	39	1 480	90.90
R21	6	14×14	122 626	101	2 028	95.41
R22	6	16×16	445 493	316	2 568	97.56
R23	6	18×18	885 932	795	2 973	99.38
R24	6	20×20	2 058 384	2 080	3 654	100.00

算例	最小值	最大值	均值	标准差
R01	743	774	773.2	15.5
R02	1 135	1 135	1 135	0
R03	1 463	1 493	1 484.25	15
R04	2 025	2 031	2 029.26	3
R05	2 408	2 481	2 460.77	36.5
R06	3 113	3 235	3 199.06	61
R07	857	878	872.71	10.5
R08	1 317	1 317	1 317	0
R09	1 682	1 752	1 728.14	35
R10	2 325	2 387	2 379.94	31
R11	2 749	2 829	2 796.86	40
R12	3 380	3 570	3 507.08	95
R13	890	946	937.14	28
R14	1 428	1 483	1 470.15	27.5
R15	1 886	1 998	1 966.77	56
R16	2 507	2 507	2 507	0
R17	2 849	3 078	3 026.19	114.5
R18	3 589	3 873	3 815.75	142
R19	949	1 001	987.29	26
R20	1 480	1 596	1 578.88	58
R21	2 028	2 028	2 028	0
R22	2 568	2 745	2 712.35	88.5
R23	2 973	3 211	3 170.69	119
R24	3 721	3 989	3 901.56	134