mothership & drone routing

A single ground vehicle — the mothership — carries a fleet of drones into a delivery region, stops at a small number of launch points, and dispatches drones to serve the surrounding customers. The vehicle and the drones have to agree on where and when they meet, and the drones are constrained by flight endurance. Deciding the launch points, the customer-to-drone assignment, and the timing all at once is what makes the problem hard.

An earlier decomposition of this problem, applied to diagnostic testing kit delivery during the COVID-19 response, is described in (Park et al., 2022). The exact algorithm below is the subject of (Mirjalili & Lim, 2026).

Approach

The model is a set-partitioning formulation whose columns are feasible mothership-and-drone routes. Because there are exponentially many of them, they are generated on demand:

• Restricted master problem. A linear relaxation over the routes generated so far, whose dual values price the customers and the vehicle’s capacity.
• Pricing subproblem. An elementary shortest path problem with resource constraints (ESPPRC), solved with a bidirectional label-setting algorithm. Labels are extended forward from the depot and backward from the sink and joined in the middle, which keeps the label count manageable under tight endurance budgets.
• Cutting planes. Cover, Chvátal–Gomory, and conflict inequalities tighten the relaxation. A hybrid family combining all three closed roughly 8% more of the optimality gap than any one of them alone.
• Branching. Branching is done on the arc-flow variables implied by the columns, so that the pricing subproblem retains its structure at every node.

Results

The valid inequalities improved LP bounds by 5–10%. A bound-inference strategy — using the best known primal bound to prune label extensions before they are generated — reduced the number of pricing calls and improved convergence by 18–50% depending on instance size.

The implementation is in Python with performance-critical labeling routines in Cython, released from the GIL so that the forward and backward label sets can be extended in parallel.