Solving Vehicle Routing Problems with Python & Heuristics Algorithm
A step-by-step guide to solving Capacitated VRP
In the modern world, efficient transportation is a crucial aspect of numerous industries, from logistics and distribution to public services and waste management. With the advancement of technology, the challenge of optimizing transportation routes has given rise to the fascinating field of the Vehicle Routing Problem (VRP). This complex computational puzzle lies at the heart of countless real-world scenarios, and finding optimal solutions can lead to substantial cost savings, reduced environmental impact, and enhanced service quality.
1. What is the Vehicle Routing Problem (VRP)?
The Vehicle Routing Problem (VRP) is a classical combinatorial optimization problem that involves determining the optimal set of routes for a fleet of vehicles to serve a given set of customers, with the objective of minimizing the total cost or distance traveled while satisfying certain constraints.
The key components of the VRP include:
- Depot: A central location where all vehicles start and return after completing their routes. The depot serves as the home base for the entire fleet.
- Customers: A set of locations that require goods or services to be rendered. Each customer has specific demands that need to be satisfied, such as a quantity of goods or the duration of service.
- Vehicles: The fleet of vehicles is responsible for delivering deliveries or services to the customers. Each vehicle has a limited capacity regarding the goods it can carry or the duration it can be on the road.
- Costs: Various cost factors play a role in the VRP, including travel distances, vehicle capacities, time constraints, fuel costs, and other operational expenses.
2. Formulating Mathematical Model for VRP
Formulating a mathematical model for the Vehicle Routing Problem (VRP) involves defining the decision variables, objective function, and constraints that represent the problem in a mathematical notation. Let’s consider the classic Capacitated Vehicle Routing Problem (CVRP) with a single depot, a fleet of vehicles, and a set of customers with demands. We’ll use the following notations:
- (1) The objective is to minimize the total cost or distance traveled by all vehicles.
- (2) Ensure that all vehicles visit each destination location exactly once.
- (3) Each route ends at depot n + 1.
- (4) Each route starts from the depot (0).
- (5) Each vehicle must visit a point and then move to visit another point.
- (6) The total load of the vehicle in one route does not exceed the vehicle’s capacity.
- (8) Non-negative constraint.
3. Solving VRP with Heuristic Methods
Solving the VRP to optimality for large instances is often computationally infeasible due to its high complexity. However, heuristic methods come to the rescue, offering efficient and practical solutions that approximate near-optimal routes for real-world applications. This article explores two popular heuristic methods for solving the VRP: the Nearest Neighbor and Two-Opt algorithms.
- Nearest Neighbor Algorithm:
The Nearest Neighbor algorithm is a simple and intuitive heuristic that constructs routes by iteratively choosing the nearest customer to the current customer. The algorithm starts with an empty route for each vehicle and an unvisited customer list. It then selects a starting customer (usually the depot) and iteratively adds the nearest unvisited customer to the current route until all customers are visited. The Nearest Neighbor algorithm is known for its efficiency and ease of implementation. However, it may not always produce optimal solutions as it can lead to suboptimal routes in certain scenarios.
- Two-Opt Algorithm:
The Two-Opt algorithm is a local search heuristic that seeks to optimize existing routes by iteratively removing two edges from the routes and reconnecting them differently, thereby reducing the total distance or cost. The algorithm starts with an initial solution, such as those generated by Nearest Neighbor or the Swap Method. It repeatedly applies the two-opt move until no further improvement is possible. The Two-Opt algorithm is relatively simple and can yield significant improvements over initial solutions.
4. Preparing the Data Input with Excel
Preparing the Excel input for the VRP solver requires organizing the data in a specific format that the code can read and process correctly. In this case, the code assumes that the Excel file contains three columns labeled ‘X,’ ‘Y’, and ‘Demand,’ representing each customer's coordinates and demand values.
Here’s a step-by-step guide on how to prepare the Excel input for the VRP solver:
- Open Microsoft Excel or any spreadsheet software.
2. Create a new sheet or use an existing sheet to input the VRP data.
3. Label the first row of the sheet with the following headers & input the data for each customer in the corresponding columns:
- ‘X’ for the x-coordinate of the customer location (a numeric value)
- ‘Y’ for the y-coordinate of the customer location (a numeric value)
- ‘Demand’ for the demand value of each customer (the quantity that needs to be delivered)
Repeat this process for each customer, entering their location and demand values in the respective rows.
5. Coding the CVRP Model with Python
Here is the Vehicle Routing Problem implementation using the Nearest Neighbor heuristic. I have utilized the Spyder IDE and an academic license for Gurobi to develop and execute the code in Python 3.10.
#import libraries
import numpy as np
import pandas as pd
def read_excel_file(filename, sheet_name):
"""
Read coordinates and demand values from a specific sheet in an Excel file.
Assumes the data is in columns labeled 'X', 'Y', and 'Demand'.
"""
df = pd.read_excel(filename, sheet_name=sheet_name)
coordinates = df[['X', 'Y']].values
demands = df['Demand'].values
return coordinates, demands
def calculate_distance_matrix(coordinates):
"""
Calculate the distance matrix between coordinates.
"""
num_points = len(coordinates)
dist_matrix = np.zeros((num_points, num_points))
for i in range(num_points):
for j in range(num_points):
dist_matrix[i, j] = calculate_distance(coordinates, i, j)
return dist_matrix
def calculate_distance(coordinates, i, j):
"""
Calculate the Euclidean distance between two points.
"""
x1, y1 = coordinates[i]
x2, y2 = coordinates[j]
return np.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
def calculate_total_distance(route, dist_matrix):
"""
Calculate the total distance of a given route using the distance matrix.
"""
total_distance = 0
num_points = len(route)
for i in range(num_points - 1):
current_node = route[i]
next_node = route[i + 1]
total_distance += dist_matrix[current_node, next_node]
return total_distance
def nearest_neighbor(dist_matrix, demands, capacity):
"""
Apply the Nearest Neighbor heuristic to find initial routes for VRP.
"""
num_points = dist_matrix.shape[0]
visited = np.zeros(num_points, dtype=bool)
routes = []
while np.sum(visited) < num_points:
current_node = 0 # Start at node 0
current_capacity = 0
route = [current_node]
visited[current_node] = True
while current_capacity + demands[current_node] <= capacity:
current = route[-1]
nearest = None
min_dist = float('inf')
for neighbor in np.where(~visited)[0]:
if demands[neighbor] + current_capacity <= capacity and dist_matrix[current, neighbor] < min_dist:
nearest = neighbor
min_dist = dist_matrix[current, neighbor]
if nearest is None:
break
route.append(nearest)
visited[nearest] = True
current_capacity += demands[nearest]
routes.append(route)
return routes
def format_output(routes):
"""
Format the final routes as required.
In this example, it returns a list of routes.
"""
return routes
def vrp_solver(filename, sheet_name, capacity):
"""
Solve the VRP using the provided filename for coordinates and vehicle capacity.
"""
coordinates, demands = read_excel_file(filename, sheet_name)
dist_matrix = calculate_distance_matrix(coordinates)
routes = nearest_neighbor(dist_matrix, demands, capacity)
formatted_routes = format_output(routes)
return formatted_routes
#Use nearest neighbor
filename = r"C:\Users\Firdaus\Documents\DATA VRP ASSIGNMENT.xlsx" #Copy file path
sheet_name = "vrp 45" # Specify the name of the sheet or its index
capacity = 2010 # Specify the capacity of the vehicle
solution = vrp_solver(filename, sheet_name, capacity)
for route in solution:
print(route)Below is the Vehicle Routing Problem implementation using the Two-Opt optimization technique. The two-opt optimization will further improve the initial routes obtained using the Nearest Neighbor heuristic by iteratively swapping segments of the routes to minimize the total distance traveled. The number of iterations for two-opt is determined by the num_iterations parameter. The more iterations you use, the better the optimization and the longer the execution time. Adjust it according to your requirements.
#Add these following code from the previous nearest neighbor code
#Use two opt
def two_opt(routes, dist_matrix, num_iterations):
best_routes = routes.copy()
for _ in range(num_iterations):
selected_route_idx = np.random.randint(0, len(routes))
selected_route = routes[selected_route_idx]
i, j = np.random.randint(1, len(selected_route) - 1, size=2)
if j < i:
i, j = j, i
new_route = selected_route.copy()
new_route[i:j] = selected_route[j - 1: i - 1: -1] # Reverse the path between i and j
new_routes = routes.copy()
new_routes[selected_route_idx] = new_route
if calculate_total_distance(new_routes[selected_route_idx], dist_matrix) < calculate_total_distance(
best_routes[selected_route_idx], dist_matrix
):
best_routes = new_routes
return best_routes
def vrp_solver2(filename, sheet_name, capacity, num_iterations):
"""
Solve the VRP using the provided filename for coordinates, vehicle capacity,
and number of iterations for the two-opt optimization.
"""
coordinates, demands = read_excel_file(filename, sheet_name)
dist_matrix = calculate_distance_matrix(coordinates)
routes = nearest_neighbor(dist_matrix, demands, capacity)
for i in range(len(routes)):
route = routes[i]
optimized_route = two_opt([route], dist_matrix, num_iterations)[0]
routes[i] = optimized_route
formatted_routes = format_output(routes)
return formatted_routes
filename = r"C:\Users\Firdaus\Documents\DATA VRP ASSIGNMENT.xlsx"
sheet_name = "vrp 421" # Specify the name of the sheet or its index
capacity = 200 # Specify the capacity of the vehicle
num_iterations = 100000
solution=vrp_solver2(filename, sheet_name, capacity, num_iterations)
print(solution)
for route in solution:
print(route)