Academic Research
IVRP · Formulation
The Interplanetary Vehicle Routing Problem models spacecraft as vehicles and planets as customers requiring periodic supply. The objective is to schedule a fleet of spacecraft to visit a set of planets within time windows, minimizing total Δv expenditure while satisfying mass, capacity, and orbital mechanics constraints.
Preprint
Interplanetary Vehicle Routing Problem (IVRP)
A novel optimization variant extending the capacitated Vehicle Routing Problem with Time Windows to multi-spacecraft mission design. A fleet of spacecraft departs from a central orbital depot and must visit a set of planetary targets delivering cargo subject to payload and propellant constraints. Lambert's problem computes time-dependent Δv transfer costs in place of static road distances — fundamentally distinguishing IVRP from all existing VRP variants. Proved NP-hard via reduction from CVRPTW; solved with a greedy + ALNS metaheuristic.
Problem Definition
Let G = (V, A) be a complete directed graph where V = {0} ∪ C, with 0 representing the depot (e.g. Earth), and C = {1,…,n} the set of planet customers. Each arc (i, j) has a travel cost cij(t) representing the Δv required for a Hohmann transfer departing at time t.
Each customer i ∈ C has demand di, time window [ei, li], and service time si. A fleet of K identical spacecraft with capacity Q and Δv budget Δvmax must service all customers, returning to the depot.
Objective Function
min Σk=1K Σ(i,j) ∈ rk cij(tij)
Minimise total Δv expenditure across all spacecraft routes.
Key Constraints
Capacity
Σ d_i ≤ Q for each spacecraft route k.
Time windows
e_i ≤ t_i ≤ l_i per visit; orbital alignment required.
Δv budget
Σ c_ij(t) ≤ Δv_max per spacecraft.
Hohmann transfer
Transit time and cost from synodic geometry. No instantaneous travel.
Fleet size
At most K spacecraft depart the depot.
Single visit
Each planet customer visited exactly once per planning horizon.
Complexity
IVRP is NP-hard by reduction from CVRPTW. The time-dependent arc costs (departure-date-sensitive Δv) add an additional combinatorial layer absent from terrestrial VRP variants. Even restricted to two planets and one spacecraft, finding the optimal launch window is equivalent to minimum-cost flow on a time-expanded graph — polynomially solvable only for special cost structures.
In the general multi-planet, multi-spacecraft case with arbitrary time windows and non-convex Δv landscapes (characterized by porkchop plot ridges), the problem is strongly NP-hard. This motivates the ALNS metaheuristic over exact methods for realistic instance sizes.
ALNS Solver
The solver combines a greedy construction heuristic with Adaptive Large Neighbourhood Search (ALNS). The greedy phase builds an initial feasible solution by repeatedly inserting the cheapest (min-Δv, earliest-window) unvisited planet into any open route.
Destroy Operators
- Random removal
- Worst removal (highest Δv legs)
- Shaw removal (similar orbits)
- Time-window removal
Repair Operators
- Greedy insertion (min-Δv position)
- Regret-2 insertion
- Earliest-window insertion
- Random insertion
Related Work
Englander & Conway (2017)
Automated trajectory planning via MIRAGE — differentiable transcription of multi-flyby missions. Single spacecraft, no fleet VRP.
Ho et al. (2019)
On-orbit servicing mission planning. Closest antecedent to IVRP; restricted to GEO belt, no time windows or demand heterogeneity.
Arnas et al. (2021)
Space logistics network design using integer programming. Static supply routes; no adaptive metaheuristic component.
Laporte (1992)
The Vehicle Routing Problem — foundational survey. IVRP inherits structural properties but adds Keplerian arc costs.