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

Zenodo · Preprint CC BY 4.0 Work in Progress

Interplanetary Vehicle Routing Problem (IVRP)

Guilherme Almeida Zeni · ⬤ ORCID

A fleet of spacecraft departs a central orbital depot and must visit a set of planetary targets, delivering cargo subject to payload and propellant (Δv budget) constraints, then return. Arc costs are not fixed distances but time-dependent transfer costs obtained by solving Lambert's problem for a chosen departure epoch and time of flight. Each target carries a hard arrival window derived from synodic alignment, and departure is bounded separately by a stay interval the optimizer chooses, since waiting at a target for a favourable alignment is the dominant lever on total Δv. The problem is shown NP-complete by reduction from VRPTW, and a Mixed-Integer Linear Program over a time-expanded graph is solved to proved optimality for every instance from two targets up to all seven planets.

DOI: 10.5281/zenodo.22710075 ↗ Read v2 on Zenodo

All versions

  • v2 11 September 2026 Corrects two constraints from v1, adds stay time, reports exact results.
  • v1 8 April 2026 Original formalization, no computational results.

Cite all versions with the concept DOI 10.5281/zenodo.19475128, which always resolves to the latest.

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): the Δv of the transfer departing at time t, obtained by solving Lambert's problem over the admissible times of flight.

Each customer i ∈ C has demand di, time window [ei, li] on arrival, and a stay interval [si, smax] bounding departure. 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 ≤ arrival ≤ l_i per visit; orbital alignment required.

Δv budget

Σ c_ij(t) ≤ Δv_max per spacecraft.

Lambert transfer

Arc cost solves Lambert's problem for the chosen time of flight. No instantaneous travel.

Stay time

Departure no earlier than arrival + s_i, no later than arrival + s_max.

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. Hardness is asymptotic, though: every instance reported on the results page, up to all seven planets, was solved to proved optimality by the exact MILP in seconds. The tractability limit of exact solving has not yet been located.

Solution Methods

Exact MILP. Every result reported on this site comes from a Mixed-Integer Linear Program over the time-expanded graph, solved with HiGHS. It returns a dual bound alongside the objective, so a solution can be stated as a proved optimum rather than an estimate. This is the method behind the instance library.

Greedy construction. A nearest-Δv heuristic that inserts the cheapest unvisited planet into any open route, taking the earliest departure whose arrival lands inside the target's window. Because it never waits for a cheaper alignment, it does not produce feasible solutions once the Δv budget binds, and it is not used for any figure published here.

Adaptive Large Neighbourhood Search. A metaheuristic seeded from the greedy solution, intended for instances beyond the reach of exact solving. It inherits the construction limitation above, so it is reported here as implemented rather than as a source of results.

Destroy Operators

  • Random removal
  • Worst-cost removal (highest Δv legs)
  • Time-window removal

Repair Operators

  • Greedy insertion (min-Δv position)
  • Regret insertion
Operator weights updated each iteration using roulette-wheel selection with decay factor λ = 0.8. Score increases when an operator yields a new global best, a new accepted solution, or any feasible solution.

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.

View Results → Open Simulator →