Interplanetary Vehicle Routing Problem (IVRP)

The Interplanetary Vehicle Routing Problem (IVRP) extends the capacitated Vehicle Routing Problem with Time Windows (VRPTW) to multi-spacecraft mission design. A fleet 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. 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. Limitations are stated explicitly: no gravity assists, mandatory return to depot, a single phase configuration per instance, and optima that are exact for the discretised model and upper bounds on the continuous problem. Related formulations are discussed, including concurrent and prior work on spacecraft routing with dynamics-derived transfer costs.