Time-expanded network model cuts complexity in mega constellation launch planning

by Riko Seibo
Tokyo, Japan (SPX) Dec 30, 2025
Large Low Earth Orbit (LEO) constellations promise continuous, high-capacity information services, but planners must work within limits set by launch cadence, payload capacity, and orbital mechanics to deploy satellites in batches at reasonable cost. Researchers Junru Lin, Tiantian Zhang, and Min Hu at Space Engineering University in Beijing have developed an optimization framework that keeps detailed timing information while shrinking the underlying mathematical problem, offering a practical tool for deployment of large constellations.

The study introduces a partial time-expanded network that removes more than 90 percent of redundant links using feasibility pruning and hierarchical aggregation and creates time nodes dynamically according to activity durations rather than a global time grid. This structure separates a transport layer for active transitions such as launches and orbital maneuvers from a waiting layer for phases like parking-orbit residence, and it incorporates a dual-channel strategy that combines direct injection with indirect injection from parking orbits to coordinate multi-configuration, multi-batch missions using both primary and auxiliary launch vehicles.

To solve the resulting model, the team applies a hybrid approach that combines column generation with a heuristic A* pricing algorithm and a subproblem filtering mechanism based on dual variables, which focuses computation on capacity-constrained windows and critical arcs. In benchmark tests for the Telesat, OneWeb, and Starlink constellations, the method cuts network size by about 84.7 percent, 99.4 percent, and 88.9 percent respectively compared with a full time-expanded network. The subproblem filter reduces the number of pricing problems by up to roughly 20 percent for OneWeb and 12 percent for Starlink, and overall solution times fall by around 30 percent, with A* consistently outperforming Dijkstra on both pricing counts and runtime.

The framework can also handle trade-offs between cost and time to service by adjusting weights in the objective function, which allows it to generate launcher mixes, batch plans, and orbital injection paths that balance schedule and budget. Simulation results indicate that a dual-launcher, dual-path plan can shorten deployment time by about 9.34 percent relative to a one-to-one scheme, at the cost of approximately an 8.19 percent increase in total expenditure, highlighting the interplay between the throughput and specific cost of primary launchers and the responsiveness of auxiliary vehicles.

The authors describe the method as a unified paradigm for end-to-end constellation deployment planning that jointly optimizes launch timing, vehicle choice, target injection orbits, and subsequent transfer and phasing while enforcing constraints on launch windows, payload limits, and orbital transfer feasibility. Future work will extend the framework to handle uncertainty and real-time replanning by modeling disruptions in production and manifests and weather effects, and will refine representations of multi-plane dispersion tactics, including distributing satellites into several orbital planes from a single launch using J2 perturbations, to improve applicability to operational mega constellations.

Research Report:Optimization strategy for batch launch deployment of large-scale low earth orbit constellations based on multimodal transportation network model