VRPOD MILP — Vehicle Routing with Occasional Drivers

Mixed-Integer Linear Programming formulation of the Vehicle Routing Problem with Occasional Drivers (Archetti et al. 2016), solved with scipy.optimize.milp (HiGHS). On a toy 8-customer / 2-truck / 3-shipper instance, crowd-shipping reduces total cost by 38.5%.

GitHub

Highlights

Replicates the foundational paper of the entire crowd-shipping literature
Demonstrates OR maturity through LaTeX-rendered formulation in README

Problem

The Aston PhD posting names 'optimisation' as an essential requirement. The Archetti, Savelsbergh & Speranza (2016) VRPOD is the canonical formal model for crowd-shipping, but the reference implementation is not publicly available.

Approach

Decision variables: y[m,c] for occasional driver m delivers customer c; z[k,c] for truck k delivers customer c
Objective: minimise truck cost + crowd-shipper compensation, with capacity constraints + detour pre-processing
Solver: scipy.optimize.milp (HiGHS branch-and-bound) — no external solver install needed
Visualisation: side-by-side baseline vs with-crowd-shippers route plots with savings annotation

Stack

Pythonscipy.optimize.milp (HiGHS)numpymatplotlibnetworkxJupyter

Outcome

13 files, 793 lines, publicly available on GitHub
Toy instance result: baseline cost 63.84 → with crowd-shippers 39.29 = 38.5% savings
Phase B extension plan: explicit MTZ subtour-elimination, scale to 20-50 customers