Σ

OM / SCM / BA

Interactive Learning Module

Chenhao Zhou
PhD Candidate | Lecturer

Vehicle Routing Optimization: The Traveling Salesman Problem

Algorithms for Last-Mile Delivery and Logistics Network Efficiency

📚 Learning Objectives

1

Understand the structure and computational complexity of the Traveling Salesman Problem (TSP) as NP-hard optimization

2

Compare heuristic algorithms including Nearest Neighbor, 2-opt local search, and Christofides' algorithm for approximation

3

Evaluate trade-offs between solution quality and computational time in practical routing applications

4

Apply routing optimization concepts to last-mile delivery, field service, and supply chain logistics challenges

⚙️ Route Parameters
5 10 stops 25
$1 $3.0 $10
15 25 mph 45

TSP Formulation

min Σᵢ Σⱼ cᵢⱼ · xᵢⱼ
s.t. Σⱼ xᵢⱼ = 1, ∀i
     Σᵢ xᵢⱼ = 1, ∀j
     subtour elimination

O(n!) complexity → heuristics essential for n > 15

NP-Hard Combinatorial Heuristics Last-Mile
Depot (Start/End)
Delivery Stop
Visited
Optimal Route
📍
0
Stops
🛣️
0
Distance (mi)
⏱️
0
Time (hrs)
💰
$0
Cost
📦
0
Packages
📊
-
vs Optimal
📈 Algorithm Comparison
📊 Distance by Segment
📋 Route Sequence
- Generate stops to see route -
📊 Performance Metrics
Algorithm Nearest Neighbor
Computation Time 0 ms
Lower Bound (MST) - mi
Gap to LB -%
AlgorithmDistanceGap
✨ Optimal-0%
Nearest Neighbor--
2-Opt--
Insertion--
Christofides--
💡 Strategic Insights
📌 Click "Generate" to create delivery stops, then "Calculate Route" to find an optimized path.

🎯 Key Managerial Insights

The Last-Mile Challenge

Last-mile delivery often represents 50%+ of total logistics costs. Efficient routing directly impacts profitability, customer satisfaction through shorter delivery windows, and environmental sustainability through reduced fuel consumption.

Heuristics vs. Optimality

For practical problem sizes (20+ stops), exact optimal solutions are computationally infeasible. Well-designed heuristics like 2-opt typically achieve within 5% of optimal while running in seconds rather than hours.

Dynamic Routing Evolution

Modern logistics uses real-time traffic data, dynamic customer requests, and machine learning to continuously re-optimize routes. The static TSP is a foundational building block for these advanced systems.

📚 Academic References

Applegate, D. L., Bixby, R. E., Chvátal, V., & Cook, W. J. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press. • Toth, P., & Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM. • Lin, S., & Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498-516. • Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report, Carnegie Mellon University.