A Two-Phase Approximate Exact Approach: A Case of Active-imaging Satellite Mission Planning Problem

2026-99-2509

11/20/2026

Authors
Abstract
Content
The Active-Imaging Satellite Mission Planning Problem (AI-SMPP) requires planners to manage task selection, scheduling, and observation durations simultaneously, while also balancing changing image quality against fluctuating energy limits. The problem builds on the classic Vehicle Routing Problem with Time Windows (VRPTW), but with a critical difference: AI-SMPP treats observation durations and image quality as variables rather than fixed values. This difference creates a tightly coupled, high-dimensional search space.We introduce a two-phase hybrid architecture called DPA-MHA (Dynamic Programming Approach integrated with Meta-Heuristic Algorithms) to handle this NP hard problem. Phase one fixes the observation parameters, reducing AI-SMPP to a standard VRPTW. A dynamic programming solver then establishes an optimal baseline sequence. Phase two relaxes those temporal constraints. At this stage, we use five meta-heuristics. Adaptive Large Neighborhood Search (ALNS), Ejection Chain, GRASP, Differential Evolution and Simulated Annealing to traverse the search space broadly. Each candidate generated by these heuristics then undergoes an exact refinement step via dynamic programming. Benchmark evaluations confirm a clear advantage for DPA-MHA. The proposed hybrid framework consistently surpasses standalone exact or conventional heuristic methods in computational efficiency, solution quality, and population diversity. Notably, the adaptive search module integrated with dynamic routing initialization demonstrates exceptional robustness in circumventing premature convergence to suboptimal solutions. Merging the accuracy of exact methods with the capacity to adjust to heuristics, this offers a viable strategy for high-dimensional aerospace operations. In such settings, standalone heuristics lack precision.
Meta TagsDetails
Citation
Chang, K., Zhu, Z., Ma, R., Wen, Q., et al., "A Two-Phase Approximate Exact Approach: A Case of Active-imaging Satellite Mission Planning Problem," 2026 5th International Conference on Aerospace, Aerodynamics and Mechatronics Engineering (AAME2026), Nanchang, China, April 17, 2026, .
Additional Details
Publisher
Published
29 minutes ago
Product Code
2026-99-2509
Content Type
Technical Paper
Language
English