Yusuf Sami- 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.
INTERACTIVE OPERATIONS RESEARCH
Can you match
the optimizer?
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.
PROBLEMMulti-scenario CVRP
SCALE2–4 vehicles · 6–12 nodes
HEURISTICMulti-start GRASP + VND
EXACTHeld–Karp + partition DP
RUNTIMEBrowser only
DECISION LAB / CAPACITATED ROUTING
Route the fleet.
3 SCENARIOS READY
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 →