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

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

Abstract

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

CLC Number:

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.

Figures/Tables 13

Fig.1

Fig.2

Fig.3

Fig.4

Table 1

Table 2

Table 3

Table 4

Fig.5

Fig.6

Table 5

Table 6

Fig.7

References 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

Multi-satellite scheduling problem for regional targets with uneven income

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 13

References 31

Related Articles 1

Recommended Articles

Metrics

Comments

算例	卫星个数	单元格数量	观测条带数量	WPSH算法		RNLS算法
算例	卫星个数	单元格数量	观测条带数量	观测收益	用时	观测收益	用时
R01	3	10×10	4 870	743	10	773.2	14
R02	3	12×12	20 140	1 135	25	1 135	39
R03	3	14×14	64 540	1 422	64	1 484.25	93
R04	3	16×16	234 470	1 928	180	2 029.26	221
R05	3	18×18	466 280	2 330	242	2 460.77	324
R06	3	20×20	1 083 360	3 056	706	3 199.06	903
R07	4	10×10	6 331	832	12	872.71	19
R08	4	12×12	26 182	1 317	27	1 317	43
R09	4	14×14	83 902	1 648	67	1 728.14	112
R10	4	16×16	304 811	2 262	192	2 379.94	320
R11	4	18×18	606 164	2 689	481	2 796.86	631
R12	4	20×20	1 408 368	3 342	980	3 507.08	1 238
R13	5	10×10	8 279	871	14	937.14	21
R14	5	12×12	34 238	1 406	33	1 470.15	52
R15	5	14×14	109 718	1 886	85	1 966.77	132
R16	5	16×16	398 599	2 507	248	2 507	388
R17	5	18×18	792 676	2 830	655	3 026.19	898
R18	5	20×20	1 841 712	3 564	1 228	3 815.75	1 506
R19	6	10×10	9 253	949	19	987.29	31
R20	6	12×12	38 299	1 480	39	1 578.88	59
R21	6	14×14	122 626	2 028	101	2 028	156
R22	6	16×16	445 493	2 568	316	2 712.35	403
R23	6	18×18	885 932	2 973	795	3 170.69	967
R24	6	20×20	2 058 384	3 654	2 080	3 901.56	2 656