A delivery company is operating in Virginia and has a fleet of trucks that are used to deliver groceries from supermarkets to consumers. The company delivers orders and operates its fleet for one shift per day that is between 12 PM and 11:59 PM.
Each day by 12 PM, the company receives a list of all deliveries required from all supermarkets. Each order is defined by the supermarket location, delivery location, and delivery time window. The company should deliver all orders. The goal of the business is to minimize its costs which are defined as follows:
All trucks should start and end their operation at the depot. The location of the depot is at: [25.1371,55.25042]. The average service time per order is 5 minutes (i.e., the time needed to take the order to the front door of the customer after arriving at their location).
Hence, a truck can pick up multiple orders’ deliveries and then deliver them. You are given the data for 6 different days. Days 1, 2, and 3 had a low amount of demand, while days 4, 5, and 6 had a high amount of demand. You need to come up with the operational plan deciding how many trucks to use and the route of each truck. (i.e., deal with each day as a separate problem, so the optimal number of trucks per day can be two on day 1 and five on day 2, and so on).
I'm new in vrp. I need to solve the problem for a) the best possible solution (heuristics/metaheuristics) Using the nearest neighbor. b) formulation for the exact solution
what needs to be added or modified in the formulation to get the desired results for both.
Here is my code:
import numpy as np
import math
from gurobipy import Model, GRB
class GroceryDeliverySolver:
def __init__(self, orders):
self.orders = orders
self.depot_location = [25.1371, 55.25042]
self.truck_capacity = float('inf')
self.average_speed_kmh = 20
self.average_service_time_minutes = 5
self.fixed_cost_per_truck = 300
self.cost_per_km=0.5
self.model = Model()
self.model.setParam('OutputFlag', 0) # Suppress Gurobi output
self.num_orders = len(orders)
self.setup_variables()
self.setup_constraints()
def setup_variables(self):
self.x = {}
for i in range(self.num_orders):
self.x[i] = self.model.addVar(vtype=GRB.BINARY, name=f'x_{i}')
self.num_trucks = self.model.addVar(lb=1, ub=self.num_orders, vtype=GRB.INTEGER, name='num_trucks')
self.start_times = [self.model.addVar(lb=0, ub=1440, vtype=GRB.INTEGER, name=f'start_time_{i}') for i in range(self.num_orders)]
self.model.update()
def setup_constraints(self):
# Each pickup and delivery must be visited by exactly one truck
for i in range(self.num_orders):
pickup_order = self.get_pickup_order(i)
# Check if pickup_order is non-empty before accessing elements
if pickup_order:
self.model.addConstr(sum(self.x[j] for j in pickup_order) == 1)
self.model.addConstr(self.x[i] == self.x[pickup_order[0]])
# Time window constraints
for i in range(self.num_orders):
pickup_time_window = self.orders[i]['timewindow']
self.model.addConstr(self.start_times[i] >= pickup_time_window[0])
self.model.addConstr(self.start_times[i] <= pickup_time_window[1])
# Ensure that delivery starts after pickup service time
pickup_order = self.get_pickup_order(i)
if pickup_order:
self.model.addConstr(self.start_times[pickup_order[0]] + self.average_service_time_minutes <= self.start_times[i])
def solve(self):
objective_sum = self.model.addVar(lb=0, ub=int(1e9), vtype=GRB.INTEGER, name='objective_sum')
distances_as_int = [int(self.calculate_distance(i) * 1000) for i in range(self.num_orders)] # Scale by 1000 and convert to int
self.model.addConstr(objective_sum == sum(self.x[i] * distances_as_int[i] for i in range(self.num_orders)))
objective = self.model.addVar(lb=0, ub=int(1e9), vtype=GRB.INTEGER, name='objective')
self.model.addConstr(objective == objective_sum + self.num_trucks * self.fixed_cost_per_truck)
self.model.setObjective(objective, GRB.MINIMIZE)
self.model.optimize()
if self.model.status == GRB.OPTIMAL or self.model.status == GRB.TIME_LIMIT:
# Optimal or feasible solution found
self.print_solution()
if self.model.status == GRB.OPTIMAL:
print("Optimal solution found.")
else:
print("Feasible solution found, but not necessarily optimal.")
else:
# No feasible solution found
print("No feasible solution found.")
def calculate_distance(self, i):
pickup_loc = [self.orders[i]['pickup_lat'], self.orders[i]['pickup_lng']]
dropoff_loc = [self.orders[i]['dropoff_lat'], self.orders[i]['dropoff_lng']]
distance = (
self.haversine(self.depot_location, pickup_loc) +
self.haversine(pickup_loc, dropoff_loc) +
self.haversine(dropoff_loc, self.depot_location)
)
return distance
def haversine(self, loc1, loc2):
lat1, lon1 = loc1
lat2, lon2 = loc2
dlat = math.radians(lat2 - lat1)
dlon = math.radians(lon2 - lon1)
a = math.sin(dlat / 2) ** 2 + math.cos(math.radians(lat1)) * math.cos(math.radians(lat2)) * math.sin(dlon / 2) ** 2
c = 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))
radius_of_earth_km = 6371.0
distance = radius_of_earth_km * c
return distance
def get_pickup_order(self, i):
return [j for j in range(self.num_orders) if self.orders[j]['order_id'] == self.orders[i]['pickup_id']]
def print_solution(self):
print("\nTruck Routes:")
for i in range(self.num_orders):
if self.x[i].x > 0.5:
pickup_order = self.get_pickup_order(i)
route = pickup_order + [i]
print(f"Truck {int(self.x[i].x)}:", route)
print("\nStart Times:")
for i in range(self.num_orders):
print(f"Order {i + 1}: {self.start_times[i].x:.2f} minutes")
print("\nNumber of Trucks Used:")
print(f"{int(self.num_trucks.x)} trucks")
if __name__ == '__main__':
day6 = [
{"id": "order_0", "pickup_lat": 25.18024367, "pickup_lng": 55.34332202, "dropoff_lat": 25.13736182, "dropoff_lng": 55.38342594, "timewindow": [60, 120]},
{"id": "order_1", "pickup_lat": 25.2222181, "pickup_lng": 55.42110585, "dropoff_lat": 25.28360419, "dropoff_lng": 55.4365873, "timewindow": [60, 120]}
]
solver = GroceryDeliverySolver(day6)
solver.solve()
Comments
3 comments