- Construct: build 96 deterministic randomized-greedy solutions from restricted candidate lists while preserving feasible capacity packing.
- Improve: 2-opt repairs each route; fleet-wide VND exchanges equal-demand node sets between vehicles until no improving move remains.
- Select: keep the best local optimum across all starts. It has no optimality proof—the exact DP provides that certificate.
Decision Lab
Assign and order demand across a growing fleet, watch the routes run, and compare your decision with a fast routing heuristic and a provably optimal solution.
Routing challenge
Route the fleet.
3 scenarios
GUIDED Two vehicles and six nodes. Learn how capacity changes an otherwise short-looking route.
VEHICLES 02NODES 06CAPACITY 07 EACH
DISTANCE MODEL
The 3:2 grid is fixed at every screen size. One square equals 5 distance units, and the solver uses the exact same on-screen proportions.
NORMALIZED DISTANCE GRID / 3:2YOUR PLAN / BUILDING
D0DEPOT
Y / 100
1 SQUARE = 5 UNITS
SIMULATION / COMPLETE
Plan evaluated.
METHODDISTANCEOVER CAP.VS OPT.STATUS
YOUR PLAN————
GRASP + VND————
EXACT DP SOLVER—0BASELINEOPTIMAL
OBJECTIVE Minimize total straight-line distance. Capacity overflow adds 200 penalty units; the exact solver only accepts capacity-feasible routes.
VISUALIZE
- Route DP: Held–Karp finds the shortest depot tour for every capacity-feasible subset of nodes.
- Fleet DP: a set-partition dynamic program assigns those subsets across all vehicles with minimum combined distance.
- Proof: — feasible subsets and — partition states were evaluated for this scenario.
EXACT SOLVER / MATHEMATICAL FORMULATION
Subset tours, then fleet partitioning.
This is a custom browser-side dynamic program—not OR-Tools, Gurobi, or a remote solver. The formulation below is exactly what the implementation evaluates.
VEHICLES / K2
NODES / |N|6
CAPACITY / Q7
DP STATES—
Let 𝒮 be all capacity-feasible node subsets and C(S) the shortest closed depot tour through subset S. Binary yₖₛ selects subset S for vehicle k.
min Σₖ Σₛ∈𝒮 C(S) · yₖₛΣₖ Σₛ∋ᵢ yₖₛ = 1 ∀ i ∈ NΣₛ∈𝒮 yₖₛ = 1 ∀ k ∈ Kyₖₛ ∈ {0, 1}D(S,j) is the shortest depot path visiting every node in S and ending at j. Closing that path produces the exact subset-tour cost.
D({j}, j) = c₀ⱼD(S,j) = minᵢ∈ₛ\{j} [D(S\{j},i) + cᵢⱼ]C(S) = minⱼ∈ₛ [D(S,j) + cⱼ₀]Σᵢ∈ₛ qᵢ ≤ QF(k,S) is the minimum distance for serving node set S with exactly k vehicles. Every transition assigns one feasible subset T to the next vehicle.
F(0, ∅) = 0F(k,S) = minₜ⊆ₛ [F(k−1,S\T) + C(T)]subject to Σᵢ∈ₜ qᵢ ≤ Qz* = F(K,N)You make the trade-offs.
Choose both assignment and visit sequence while balancing total distance and vehicle capacity. A visually short route is not useful if its assigned demand breaks the hard capacity limit.
Search beyond one local choice.
GRASP constructs 96 diverse capacity-feasible plans. A fleet-wide variable-neighborhood descent then combines intra-route 2-opt with demand-preserving exchanges between vehicles.
A proof-sized benchmark.
Held–Karp solves the shortest tour for every feasible node subset; partition DP combines those tours across the fleet. Larger real-world instances call for mathematical programming or metaheuristics. See the full routing work →