Decomposition-Based QAOA for Maximum Coverage Location Problem in Satellite Constellation Design

Jul 16, 2026

Earth observation missions drive the need for efficient satellite constellation design and optimization, where maximizing target coverage under limited orbital resources forms a challenging combinatorial problem. The maximum covering location problem (MCLP) is NP-hard and becomes computationally intractable for large constellations. Classical methods can reach optimal or near-optimal solutions but scale poorly. This paper presents a scalable quantum optimization framework that decomposes large MCLP instances into subgraphs, solves them with quantum approximate optimization circuits, and reconstructs a global solution. Results show better scalability in less time while preserving competitive coverage.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages21

Reading Time53 min

Abstract

Problem Context: MCLP in Satellite Constellation Design

Related Work in Constellation Optimization

Limitations of Classical and Existing Quantum Approaches

Proposed Decomposition-Based Quantum Optimization Framework

Decomposition-Based QAOA for Maximum Coverage Location Problem in Satellite Constellation Design DIVYA SISODIYA1 , AMIRATABAK BAHENGAM2 , HANG WOON LEE3 ,(Member, IEEE), AND HAO CHEN2 ,(Member, IEEE) 1Department of Physics, Stevens Institute of Technology, Hoboken, NJ 07030 USA 2Department of Systems Engineering, Stevens Institute of Technology, Hoboken, NJ 07030 USA 3Department of Mechanical, Materials and Aerospace Engineering, West Virginia University, Morgantown, WV 26506 USA Corresponding author: Hao Chen ([e-mail: hao.chen@stevens.edu](e-mail: hao.chen@stevens.edu)). [ quant-ph] 9 Jul 2026 ABSTRACT An increase in earth observation missions has increased the demand of efficient design and optimization of satellite constellations. Maximizing coverage of the target while effectively utilizing the limited orbital resources is one of the critical design challenges for complex combinatorial optimization problems. The maximal covering location problem (MCLP), serves as a base for orbital coverage modeling, is NP-hard and computationally intractable for large-constellation instances. Using heuristics, metaheuristics, and mixed-integer linear programming, classical solvers have achieved optimal or near-optimal results, yet their scalability is limited as the problem size increases. Quantum computing advancements, includingthe quantum approximate optimization algorithms, offer a potential solution to NP-hard combinatorial optimization problems. Current quantum hardware limitations, such as low qubit counts and circuit depth, restrict solutions for small-scale instance problems. To address this challenge, this paper proposes a scalable quantum optimization framework for MCLP in satellite constellation design. A decompositionbased quantum methodology is proposed, in which large MCLP instances are partitioned into subgraphs by classical decomposition, optimized independently via quantum optimization circuits, and combined using quantum reconstruction strategies. Computational results across different constellation sizes reveal betterscalability in less time while maintaining competitive coverage performance compared to classical solvers. INDEX TERMS divide-and-conquer algorithms, graph partitioning, quantum approximate optimization algorithm, maximum coverage location problem, quadratic unconstrained binary optimization, and satellite While multiple formulation frameworks exist for constellation design, including the set covering location problem (SCLP), partial set covering location problem (PSCLP), and maximum covering location problem (MCLP), the MCLP framework is particularly well-suited for the resourceconstrained satellite constellation design problem. The significance of MCLP applied to the constellation configuration design optimization is that it enables the user to design a constellation where the number of satellites to be used is a parameter and the objective is to obtain the maximum observational rewards over a set of targets [1] . This objective is distinctive from those of SCLP and PSCLP, which seek to provide continuous coverage or a percentage of coverage over the targets while considering the number of satellites asa decision variable instead of a parameter [1] . Originally, it was developed by Church and ReVelle, MCLP formulation maps orbital slots to facility locations, represents satellites as limited resources, and ground targets as demand nodes requiring coverage [2] . Previous work on the satellite constellation optimization included complex mathematical and heuristic methodologies of several types. The optimal configuration of the satellite constellation is modeled as a multi-objective mixed integer programming problem, and a metaheuristic optimization method is applied to optimize the configuration and number of satellite ground tracks and orbital planes [3] . An integer linear programming (ILP) based framework for common ground track constraints reduces the worst-case revisit time by ove

FAQs

Why is the maximum covering location problem important for satellite constellation design?

It enables designing constellations where the number of satellites is a parameter while maximizing observational rewards over a set of targets, using orbital slots mapped to facility locations and ground targets as demand nodes requiring coverage.

What makes large MCLP instances difficult to solve?

MCLP is NP-hard, and exact methods become computationally intractable as constellation size grows, leading to limited scalability in classical solvers and related formulations.

How does the proposed decomposition-based QAOA framework work?

Large MCLP instances are partitioned into subgraphs via classical decomposition, each subgraph is optimized independently using quantum optimization circuits, and then the subproblem results are combined through quantum reconstruction strategies.

Jul 16, 2026

Upload by Theodora