Validity of a VRP formulation and code

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:

𝐶𝑜𝑠𝑡 = (𝛽 × 𝑇) + (𝛾 × 𝐷)
𝛽: the fixed cost per each used truck per day.
𝑇: the number of used trucks per day.
𝛾: the cost per unit travel distance in km.
𝐷: the total travel distance from all trucks per day in km.

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).

Assumptions:
• All distances are assumed to be haversine distances.
• The average driving speed of the truck is 20 km/hr.
• 𝛽 = 300/truck/𝑡𝑟𝑢𝑐𝑘
• 𝛾 = 0.5/km/𝑘𝑚
• Trucks have infinite capacity.

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).

Here is my formulation:

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()

正式なコメント

Simranjit Kaur

Gurobi Staff

2026年11月13日 01:34

This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.

Mario Ruthmair

2023年11月20日 17:23

Hi Taposh Kumar,

Several model components are missing that model the trucks' routes in your VRP with time windows.

Here are Jupyter notebooks that discuss different ways to model the Capacitated VRP and the VRP with time windows. It might give you some hints on the missing parts.

Best regards,
Mario

Taposh Kumar Kapuria

2023年11月20日 19:24

Thanks for your comments. Could you please suggest any resources to solve vrp with heuristics /metaheuristics in python?

2023年11月21日 08:23

Solving VRPs with (meta)heuristics is outside the scope of this forum since this is not Gurobi-related.

I do not know of any public Python implementations of VRP heuristics, but I usually recommend the book "Vehicle Routing" by Toth and Vigo.

Validity of a VRP formulation and code

コメント

お探しのものを見つけられませんでしたか？