Vehicle Routing
Find optimal routes for a fleet of vehicles serving multiple locations under constraints like time windows, capacity limits, and driver regulations.
NP-hardComplexity
Why Vehicle Routing Is Hard
Combinatorial explosion
50 trucks with 200 stops creates more possible route combinations than atoms in the observable universe. No brute-force approach can check them all.
Interdependent constraints
Time windows, capacity limits, and driver regulations all interact. Satisfying one constraint may violate another. The feasible region is sparse and fragmented.
Dynamic conditions
Traffic, cancellations, and new orders change the problem mid-execution. The optimal plan from this morning may be suboptimal by noon.
Real-World Example
What This Looks Like in Practice
A logistics company operates 47 trucks serving 2,847 delivery points across 6 countries. Each delivery has a 6-hour time window. Trucks vary in capacity from 3 to 12 tons. EU driver regulations limit driving to 9 hours with mandatory breaks. The space of possible solutions has more entries than particles in the observable universe. Excel can't solve this. No human can. Mathematics can.
Approach
How kint Solves Vehicle Routing Problems
Formulate as Mixed-Integer Program
Each route decision becomes a binary variable. Constraints become linear equations. The objective minimizes total cost.
Apply cutting planes
Mathematical techniques tighten the feasible region, eliminating billions of suboptimal solutions without evaluating them.
Branch and bound with ML warm-start
Machine learning predicts a good starting solution. The solver proves optimality from there, reducing search time dramatically.
Verify and report
The optimality gap measures how close the solution is to mathematical perfection. 0.00% means no better solution exists.
Technical Details
The Vehicle Routing Problem (VRP) and its variants (CVRPTW, PDPTW, MDVRP) are NP-hard combinatorial optimization problems. kint formulates these as mixed-integer programs and solves them using branch-and-bound with cutting planes, combined with ML-based warm-starting for faster convergence.
Impact
What Changes
Total distance
12,400 km
9,100 km (-27%)
Active routes
47
38 (-19%)
Fuel cost
€4,280/day
€3,510/day (-18%)
Planning time
6 hours
2 minutes
On-time delivery
84%
96%
Example
Input
Optimize delivery routes for 47 trucks across 2,847 delivery points with 6-hour time windows and EU driver regulations.
Output
Optimal route assignment with 38 active routes, respecting all constraints. 23% fewer kilometers, 18% lower fuel costs.
-23%
distance reduction
-18%
fuel cost savings
2 min
solve time
Connections
Related Problem Types
Have a Vehicle Routing Problem?
Show us your data. We'll show you what optimal looks like. No commitment.