Solving the vehicle routing problem for optimizing shipment delivery
summary
Variant of capacitated VRP with time windows, implemented as a custom solver because off‑the‑shelf OR‑Tools gives overlapping, elongated routes. Solution uses a greedy construction heuristic plus an ejection–reinsert heuristic with simulated annealing acceptance, and adds concrete penalties for travel time, normalized fairness (coeff‑of‑variation), an outlier score from α‑percentile nearest‑neighbor modified z‑scores, and an 80th‑percentile compactness metric. Example runtime: 800 shipments ~25–30 min. Results cut compactness from 2900 to 768 and lower overall cost.
AI-written summary · about
chapters (23)
- 0:00Intro
- 1:10Wider context
- 3:08Manual process
- 7:02Custom solver
- 7:53Problem setup
- 10:50Intuition
- 11:36Action Definition
- 13:09Algorithms
- 13:44Approximate Algorithms
- 17:46Infeasible Solutions
- 18:27Computational Complexity
- 18:59Insertion Cost
- 20:23Unrealistic Example
- 21:17General Methods
- 27:33Results
- 28:37Cost
- 29:27Questions
- 29:44Algorithm
- 30:23Challenges
- 31:15Factoring in carriers
- 31:36Capacity constraint
- 32:10Inhouse vs external vendors
- 33:48Runtime
related talks
23mRevolutionizing Secondary Mile: Transforming VRP with Meta Heuristics
30mBuild on-demand logistics apps with Python, OR-Tools, and DecisionOps
20mRoute Optimization Engine for the Real World
21mCombinatorial Optimization of Train Timetable Fulfilment After Incidents
15mComputational Mobility: Learning, Prediction, and Algorithms
39mPractical Optimization for Stats Nerds
01h 10mMulti-Dimensional and Non-Linear Mechanism Design and Approximation II
36mSmarter Tools for (Citi)Bike-Sharing