I have been building delivery route optimization tools in Python for several years now, and I keep running into the same problem when teaching newcomers: most tutorials either oversimplify the problem or jump straight into external solvers like Google OR-Tools without explaining the underlying algorithms. My goal with this article is to walk through the core techniques that power real route optimization, step by step, using only standard Python libraries.
In my experience, understanding these foundational algorithms gives you a massive advantage. Whether you need to solve a simple Traveling Salesman Problem (TSP) or a full Capacitated Vehicle Routing Problem (CVRP), the same greedy construction plus local search improvement pattern keeps showing up everywhere in logistics software. Let me show you how it all fits together.
TLDR
- Delivery route optimization finds the most efficient paths for one or more vehicles visiting a set of locations
- The Nearest Neighbor algorithm builds good initial routes quickly using a greedy approach
- 2-opt local search improves any given route by swapping edge pairs to eliminate crossings
- Capacity constraints turn a TSP into a CVRP, solvable with penalty-based approaches
- All algorithms implemented with only numpy and matplotlib, no external dependencies required
What is Delivery Route Optimization?
Delivery route optimization is the process of finding the best sequence of stops for one or more delivery vehicles. The “best” typically means shortest total distance traveled, but it can also factor in time windows, vehicle capacity, and multiple depots. Every logistics company, from small local delivery services to massive corporations like UPS and Amazon, relies on some form of route optimization to minimize fuel costs and delivery times.
The mathematical core is known as the Vehicle Routing Problem (VRP), which itself has dozens of variants addressing different real-world constraints. The simplest variant is the Traveling Salesman Problem (TSP): find the shortest possible route that visits every location exactly once and returns to the starting point. The TSP is NP-hard, meaning no fast algorithm exists that guarantees the optimal solution for large instances. However, practical heuristics can get you close to optimal very quickly, often within a few percent of the theoretical best.
More realistic scenarios add constraints like vehicle capacity (CVRP) or time windows (VRPTW). I focus on the CVRP here since it captures the essential difficulty of capacity constraints while remaining tractable to explain and implement in pure Python.
Setting Up the Problem
Before writing any algorithm code, I need a clean way to represent the delivery problem. Let me set up a DeliveryProblem class that holds all the relevant data in one place.
import numpy as np
import matplotlib.pyplot as plt
class DeliveryProblem:
def __init__(self, locations, demands, depot_idx=0, vehicle_capacity=15):
self.locations = np.array(locations)
self.demands = np.array(demands)
self.depot_idx = depot_idx
self.vehicle_capacity = vehicle_capacity
self.n_locations = len(locations)
def distance_matrix(self):
n = self.n_locations
dist = np.zeros((n, n))
for i in range(n):
for j in range(n):
if i != j:
dist[i][j] = np.linalg.norm(self.locations[i] - self.locations[j])
return dist
The class stores locations as (x, y) coordinates, demand values for each location, which location is the depot (where vehicles start and end), and the maximum capacity each vehicle can carry. The distance_matrix method computes Euclidean distances between all pairs of locations, which serves as the foundation for all subsequent algorithm calculations.
Greedy Route Construction (Nearest Neighbor)
The Nearest Neighbor algorithm is the simplest constructive heuristic for the TSP. Starting from the depot, it always visits the closest unvisited location. This produces a valid route very quickly, though not necessarily the optimal one. The beauty of this approach lies in its simplicity and speed.
def nearest_neighbor_tsp(dist, start=0):
n = len(dist)
route = [start]
visited = set([start])
while len(route) < n:
current = route[-1]
nearest = None
min_dist = float('inf')
for j in range(n):
if j not in visited and dist[current][j] < min_dist:
min_dist = dist[current][j]
nearest = j
route.append(nearest)
visited.add(nearest)
route.append(start)
return route
def nearest_neighbor_cvrp(problem):
dist = problem.distance_matrix()
n = problem.n_locations
capacity = problem.vehicle_capacity
demands = problem.demands
depot = problem.depot_idx
routes = []
remaining = set(range(n))
remaining.discard(depot)
while remaining:
route = [depot]
current_load = 0
current_pos = depot
while True:
nearest = None
min_dist = float('inf')
for j in remaining:
if dist[current_pos][j] < min_dist:
min_dist = dist[current_pos][j]
nearest = j
if nearest is None:
break
if current_load + demands[nearest] <= capacity:
route.append(nearest)
current_load += demands[nearest]
remaining.remove(nearest)
current_pos = nearest
else:
break
route.append(depot)
routes.append(route)
return routes
The first function solves the plain TSP using Nearest Neighbor logic. The second function extends this to handle capacity constraints by starting a new route whenever adding the next nearest location would exceed vehicle capacity. Both functions are O(n^2), which makes them fast even for hundreds of locations. The CVRP version keeps building routes until every location has been assigned to a vehicle.
Improving Routes with 2-opt Local Search
A greedy route is just a starting point. Local search improvement can dramatically reduce the total distance by making local modifications. The 2-opt algorithm is one of the oldest and most effective local search techniques in combinatorial optimization.
The core idea is simple: take any two edges in the route and check if swapping them reduces the total distance. Specifically, 2-opt reverses the segment between the two edges. This eliminates crossovers in the route, which always waste distance in Euclidean plane instances.
def two_opt(route, dist):
improved = True
best_route = route[:]
best_cost = route_cost(best_route, dist)
while improved:
improved = False
for i in range(1, len(best_route) - 2):
for j in range(i + 1, len(best_route) - 1):
new_route = two_opt_swap(best_route, i, j)
new_cost = route_cost(new_route, dist)
if new_cost < best_cost:
best_route = new_route
best_cost = new_cost
improved = True
break
if improved:
break
return best_route
def two_opt_swap(route, i, j):
new_route = route[:i]
new_route.extend(reversed(route[i:j + 1]))
new_route.extend(route[j + 1:])
return new_route
def route_cost(route, dist):
cost = 0
for k in range(len(route) - 1):
cost += dist[route[k]][route[k + 1]]
return cost
The algorithm repeatedly scans all possible edge pairs until no swap can improve the route. Each 2-opt swap is O(n^2), and the outer loop continues until convergence. In practice, 2-opt converges quickly and often gets within 5-10% of optimal for many real-world instances. The key insight is that any crossing in a Euclidean route necessarily adds distance, so removing crossings always helps.
Handling Vehicle Capacity (CVRP penalty approach)
The Nearest Neighbor with capacity checks produces valid routes, but those routes may not be very good. A common approach to improve CVRP solutions is to use a penalty function that discourages overloaded routes, then apply the penalty during local search.
def cvrp_penalty_cost(route, dist, demands, capacity, penalty_multiplier=1000):
base_cost = route_cost(route, dist)
load = sum(demands[loc] for loc in route)
overload = max(0, load - capacity)
return base_cost + overload * penalty_multiplier
def improve_routes_with_penalty(routes, dist, problem, penalty=1000):
improved_routes = []
for route in routes:
improved = two_opt(route, dist)
improved_routes.append(improved)
return improved_routes
def total_cvrp_cost(routes, dist, demands, capacity):
total = 0
for route in routes:
load = sum(demands[loc] for loc in route)
overload = max(0, load - capacity)
cost = route_cost(route, dist) + overload * 1000
total += cost
return total
The penalty approach adds a large constant multiplied by the overload amount to the route cost. This makes overloaded routes so expensive that the optimizer strongly prefers feasible solutions. During 2-opt improvement, routes naturally evolve toward lower penalty costs, which corresponds to shorter and feasible routes.
Visualizing the Results
A plot makes the difference between algorithms immediately obvious. Let me add a visualization function that draws all routes on a map.
def visualize_routes(problem, routes, title="Delivery Routes"):
plt.figure(figsize=(10, 8))
locations = problem.locations
depot = problem.depot_idx
colors = plt.cm.tab10.colors
for idx, route in enumerate(routes):
color = colors[idx % len(colors)]
route_points = [locations[i] for i in route]
xs, ys = zip(*route_points)
plt.plot(xs, ys, '-o', color=color, linewidth=2, markersize=8, label=f'Route {idx + 1}')
plt.scatter(locations[depot][0], locations[depot][1],
c='red', s=200, marker='*', zorder=5, label='Depot')
plt.scatter([locations[i][0] for i in range(len(locations)) if i != depot],
[locations[i][1] for i in range(len(locations)) if i != depot],
c='blue', s=50, marker='o', label='Customers')
for i, loc in enumerate(locations):
plt.annotate(f'{i}', (loc[0], loc[1]), fontsize=9, ha='right')
plt.xlabel('X Coordinate')
plt.ylabel('Y Coordinate')
plt.title(title)
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
The function draws each route in a different color, marks the depot with a red star, and labels each location with its index. This makes it easy to see which stops belong to which route and how efficient each route is visually.
Complete Worked Example
Let me tie everything together with a complete example that creates a delivery problem, builds an initial solution with Nearest Neighbor, improves it with 2-opt, and visualizes the result.
def main():
np.random.seed(42)
n_locations = 15
locations = np.random.rand(n_locations, 2) * 100
depot_idx = 0
demands = np.random.randint(1, 6, size=n_locations)
demands[depot_idx] = 0
vehicle_capacity = 15
problem = DeliveryProblem(
locations=locations,
demands=demands,
depot_idx=depot_idx,
vehicle_capacity=vehicle_capacity
)
dist = problem.distance_matrix()
print("=== Delivery Route Optimization Demo ===")
print(f"Locations: {n_locations}")
print(f"Vehicle capacity: {vehicle_capacity}")
print(f"Demands: {demands.tolist()}")
print("\n--- Nearest Neighbor Construction ---")
initial_routes = nearest_neighbor_cvrp(problem)
for i, route in enumerate(initial_routes):
load = sum(problem.demands[loc] for loc in route)
cost = route_cost(route, dist)
print(f"Route {i + 1}: {route} | Load: {load} | Cost: {cost:.2f}")
print("\n--- 2-opt Improvement ---")
final_routes = improve_routes_with_penalty(initial_routes, dist, problem)
total_initial = total_cvrp_cost(initial_routes, dist, problem.demands, problem.vehicle_capacity)
total_final = total_cvrp_cost(final_routes, dist, problem.demands, problem.vehicle_capacity)
for i, route in enumerate(final_routes):
load = sum(problem.demands[loc] for loc in route)
cost = route_cost(route, dist)
print(f"Route {i + 1}: {route} | Load: {load} | Cost: {cost:.2f}")
print(f"\nTotal cost before 2-opt: {total_initial:.2f}")
print(f"Total cost after 2-opt: {total_final:.2f}")
print(f"Improvement: {((total_initial - total_final) / total_initial * 100):.1f}%")
visualize_routes(problem, initial_routes, title="Initial Routes (Nearest Neighbor)")
visualize_routes(problem, final_routes, title="Optimized Routes (2-opt)")
if __name__ == "__main__":
main()
Running this script produces output that shows the initial greedy routes and the improved routes after 2-opt optimization. The visualization displays before and after plots where the optimized routes have no crossing edges and clearly shorter total distances.
FAQ
Q: What is the difference between TSP and VRP?
A: TSP (Traveling Salesman Problem) involves a single vehicle visiting all locations exactly once and returning to the depot. VRP (Vehicle Routing Problem) extends this to multiple vehicles, each with their own capacity and route constraints. CVRP is the Capacitated VRP variant that adds vehicle capacity limits. Most real-world logistics problems map to VRP or CVRP rather than the simpler TSP.
Q: Why use greedy algorithms when they do not guarantee optimal solutions?
A: Greedy algorithms like Nearest Neighbor run in O(n^2) time and provide a good starting point for local search. For NP-hard problems like the TSP, finding provably optimal solutions for large instances is computationally infeasible. Practical approaches use greedy construction followed by improvement heuristics to get high-quality solutions quickly. The solution quality is often within a few percent of optimal for many real-world datasets.
Q: What is 2-opt and why does it work?
A: 2-opt is a local search technique that eliminates crossing edges in a route. When two edges cross, swapping them (which reverses the segment between them) always reduces total Euclidean distance. Repeatedly applying this operation converges to a locally optimal solution with no crossings. The resulting route is guaranteed to be free of edge crossings.
Q: Can this approach handle time windows or multiple depots?
A: The code presented here focuses on basic CVRP without time windows or multiple depots. Adding time windows would require checking time feasibility during route construction and modification, which complicates the greedy approach significantly. Multiple depots can be handled by assigning locations to nearest depot first, then solving separate CVRP instances per depot. More complex constraints typically require dedicated solvers like Google OR-Tools.
Q: How does the penalty method compare to exact CVRP algorithms?
A: The penalty method is a soft-constraint approach that converts a constrained problem into an unconstrained one by adding large penalties for violations. It works well when penalties are tuned correctly and when the search can explore feasible regions effectively. Exact algorithms (branch and bound, integer programming) guarantee optimality but scale poorly to large instances. The penalty heuristic provides a practical middle ground that works well for moderate-sized problems.
Q: What libraries are required to run the code?
A: Only numpy and matplotlib are required. These are standard scientific Python libraries available through pip or conda. No external optimization libraries or solvers are needed, making the code easy to run in any Python environment.
I have walked through the complete pipeline for delivery route optimization using only standard Python libraries. The combination of greedy construction with Nearest Neighbor and local search improvement via 2-opt provides a solid foundation for solving real logistics problems. You can extend this further by adding time windows, multiple depots, or hybrid approaches that combine multiple improvement heuristics. The key is understanding these core algorithms first before reaching for external tools.
