Graphs | Navigating the Vehicle Routing Problem (VRP) using Python
Exploring Algorithmic Solutions for Simplified Vehicle Routing
The Vehicle Routing Problem (VRP) is a classic challenge in logistics and operations research, demanding efficient delivery routes to minimize costs and maximize efficiency. From navigating city streets for package deliveries to optimizing supply chain logistics, VRP’s applications are vast and impactful.
In this post, we’ll dissect a Python implementation that tackles a simplified version of the VRP using three fundamental algorithms: Nearest Neighbor, Brute Force, and Random Search. We’ll explore how these methods work, their strengths and limitations, and how they can approximate solutions for this complex optimization problem. Let’s dive in.
1. Graph Creation and Distance Calculation
We begin by creating a virtual city map using Python’s networkx library. The create_graph function generates a complete graph where nodes represent delivery locations and edges represent the roads connecting them. Each location is assigned random coordinates, and the edge weights correspond to the Euclidean distances between them. This serves as our problem space.
def create_graph(num_nodes, seed=42):
random.seed(seed)
G = nx.Graph()
cities = {i: (random.uniform(0, 10), random.uniform(0, 10)) for i in range(num_nodes)}
for city, pos in cities.items():
G.add_node(city, pos=pos)
for i in range(num_nodes):
for j in range(i + 1, num_nodes):
x1, y1 = cities[i]
x2, y2 = cities[j]
distance = np.sqrt((x2 - x1)**2 + (y2 - y1)**2)
G.add_edge(i, j, weight=distance)
return G, citiesOnce we have our graph, we need a way to calculate the total distance of a route. The route_distance function does precisely that, summing the weights of the edges along a given path, including the return trip to the starting point.
def route_distance(G, route):
total = sum(G[route[i]][route[i + 1]]['weight'] for i in range(len(route) - 1))
total += G[route[-1]][route[0]]['weight']
return total2. The Algorithms: Approaching the Problem
To tackle the VRP, we first address a core component: the Travelling Salesperson Problem (TSP). The TSP aims to find the shortest route that visits each node exactly once and returns to the starting node. Our code implements three distinct approaches:
- Nearest Neighbor (
solve_tsp_nearest_neighbor): This greedy algorithm starts at a node and repeatedly selects the nearest unvisited node. It's fast and simple but often yields suboptimal results.
def solve_tsp_nearest_neighbor(G):
route = [0]
unvisited = set(G.nodes()) - {0}
while unvisited:
current = route[-1]
next_city = min(unvisited, key=lambda x: G[current][x]['weight'])
route.append(next_city)
unvisited.remove(next_city)
return route, route_distance(G, route)- Brute Force (
solve_tsp_brute_force): This exhaustive search method generates all possible permutations of nodes and calculates the distance for each. While guaranteeing the optimal solution, its computational cost explodes with increasing node count.
def solve_tsp_brute_force(G):
nodes = list(G.nodes())[1:]
min_route, min_distance = None, float('inf')
for perm in itertools.permutations(nodes):
route = [0] + list(perm)
dist = route_distance(G, route)
if dist < min_distance:
min_distance, min_route = dist, route
return min_route, min_distance- Random Search (
solve_tsp_random): This approach generates a set number of random routes and selects the best one. It's simple but highly dependent on the number of iterations and offers no guarantee of optimality.
def solve_tsp_random(G, iterations=1000):
nodes = list(G.nodes())
min_route, min_distance = None, float('inf')
for _ in range(iterations):
route = [0] + random.sample(nodes[1:], len(nodes) - 1)
dist = route_distance(G, route)
if dist < min_distance:
min_distance, min_route = dist, route
return min_route, min_distance3. From TSP to Simplified VRP: Clustering and Subgraphs
Here’s where we move from TSP to a simplified VRP. The solve_vrp function divides the nodes into clusters, representing routes for different vehicles. It uses a straightforward round-robin clustering method. For each cluster, it creates a subgraph, relabels the nodes, and applies one of our TSP solvers.
def solve_vrp(G, num_vehicles, solver):
nodes = list(G.nodes())
nodes.remove(0)
clusters = [nodes[i::num_vehicles] for i in range(num_vehicles)]
routes, total_distance = [], 0
for cluster in clusters:
cluster_nodes = [0] + cluster
subgraph = G.subgraph(cluster_nodes).copy()
mapping = {old: new for new, old in enumerate(cluster_nodes)}
subgraph = nx.relabel_nodes(subgraph, mapping)
route, distance = solver(subgraph)
original_route = [cluster_nodes[i] for i in route]
routes.append(original_route)
total_distance += route_distance(G, original_route)
return routes, total_distanceThis example is a simplified VRP. We’re not considering factors like vehicle capacity, demand, or time windows. This implementation essentially breaks the VRP into multiple independent TSP instances.
4. Visualizing the Routes: Plotting with Matplotlib
To better understand our solutions, we use matplotlib to visualize the routes. The plot_vrp function draws the graph, highlights the routes for each vehicle with different colors, and displays the total distance.
def plot_vrp(G, routes, distance, title, time_taken):
plt.figure(figsize=(10, 8))
pos = nx.get_node_attributes(G, 'pos')
nx.draw_networkx_nodes(G, pos, node_color='lightblue', node_size=500)
nx.draw_networkx_edges(G, pos, edge_color='gray', alpha=0.3)
nx.draw_networkx_labels(G, pos, font_size=12, font_weight='bold')
colors = ['red', 'green', 'blue', 'orange', 'purple']
for i, route in enumerate(routes):
color = colors[i % len(colors)]
edges = [(route[j], route[j + 1]) for j in range(len(route) - 1)] + [(route[-1], route[0])]
nx.draw_networkx_edges(G, pos, edgelist=edges, edge_color=color, width=2)
edge_labels = {(i, j): f"{G[i][j]['weight']:.2f}" for i, j in G.edges()}
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=10)
plt.title(f"{title}\nDistance: {distance:.2f}, Time: {time_taken:.6f}s", fontsize=14)
plt.axis('off')
plt.show()5. Running the Analysis: Comparing the Algorithms
Finally, the run_vrp_analysis function ties everything together. It creates a graph, runs the VRP solver with each of our three algorithms, prints the results, and plots the solutions. This allows us to compare the performance and effectiveness of each method.
def run_vrp_analysis(num_nodes, num_vehicles):
G, _ = create_graph(num_nodes)
solvers = {
"Nearest Neighbor": solve_tsp_nearest_neighbor,
"Brute Force": solve_tsp_brute_force,
"Random Search": solve_tsp_random
}
for name, solver in solvers.items():
start_time = time.time()
routes, distance = solve_vrp(G, num_vehicles, solver)
elapsed_time = time.time() - start_time
print(f"{name} - Routes: {routes}, Distance: {distance:.2f}, Time: {elapsed_time:.6f}s")
plot_vrp(G, routes, distance, f"{name} Solution ({num_nodes} nodes, {num_vehicles} vehicles)", elapsed_time)You can run the function by defining the number of nodes and vehicles, in this case, for 8 nodes and 3 vehicles:
run_vrp_analysis(8, 3)
The three algorithms produce the same result, but as we increase the number of nodes, outputs tend to diverge (e.g., 15 nodes and 3 vehicles):
Final Thoughts
While this code provides a valuable introduction to VRP solving, it has some limitations. In this regard, improvements could include:
- Implementing more sophisticated clustering algorithms.
- Incorporating vehicle capacity and demand constraints.
- Exploring more advanced optimization algorithms (e.g., genetic algorithms, simulated annealing).
- Using dedicated VRP solvers like OR-Tools.
This implementation demonstrates the core concepts and the application of fundamental algorithms. By understanding these basics, we can move towards tackling more complex and realistic VRP scenarios.
