Optimization
Quantum Satellite Routing
A QUBO formulation of satellite routing as a Traveling Salesman Problem, solved with quantum-inspired optimization.
Formulation
QUBO / Ising
Problem class
Traveling Salesman
Input
Live TLE orbital data
01
Overview
Servicing, inspecting, or de-orbiting multiple satellites in a single mission requires choosing a visiting order that minimizes total maneuvering cost — a Traveling Salesman Problem where the “cities” are moving targets in orbit.
This project formulates that routing problem as a Quadratic Unconstrained Binary Optimization (QUBO) model, the native input format of quantum annealers, and solves it with quantum-inspired techniques using real orbital data from TLE catalogs.
02
Technical approach
- 01
Cost matrix from orbital mechanics
Transfer costs between satellite pairs are derived from their orbital elements, so the optimizer works with physically meaningful maneuver costs rather than abstract distances.
- 02
TSP to QUBO encoding
The tour is encoded with binary variables x(i,t) — satellite i visited at step t. Tour-validity constraints (each satellite once, one satellite per step) become quadratic penalty terms added to the cost objective.
- 03
Penalty weight calibration
Penalty coefficients are tuned so constraint violations are always more expensive than any cost saving, without flattening the optimization landscape.
- 04
Quantum-inspired solving
The resulting QUBO is solved with simulated annealing-style samplers, with solution quality benchmarked against classical heuristics on the same instances.
03
Architecture
01
TLE Data
Orbital elements per satellite
02
Cost Matrix
Pairwise transfer costs
03
QUBO Encoding
Binary variables + penalties
04
Annealing Solver
Quantum-inspired sampling
05
Optimal Route
Decoded visiting order
04
Challenges
Quadratic variable growth
An n-satellite tour needs n² binary variables, so problem size grows quickly. Keeping instances within solver limits required careful pruning of the candidate set.
Constraint encoding
Unlike classical solvers, QUBO has no hard constraints — everything is a penalty. Badly scaled penalties either permit invalid tours or drown out the actual objective.
Moving targets
Transfer costs between orbits are not static, which breaks the symmetric-TSP assumption and required simplifying assumptions about maneuver timing.
05
Results
A complete QUBO formulation of satellite routing validated on real TLE-derived instances.
Quantum-inspired solvers recover valid, low-cost tours that match or beat greedy classical baselines on test instances.
A reusable encoding framework for mapping other constrained orbital optimization problems to QUBO form.
06
Media & links
More projects