Proper way to use big-M method
Awaiting user input
Hello, I am a student working on a pickup-delivery problem using drones and vehicles.
Currently, I am working with an initial depot at node 0, a final depot at node 2*num_orders + 1, pickup nodes from 1 to num_orders, and delivery nodes from num_orders + 1 to 2*num_orderes. For example, if there are 5 orders, the pickup nodes would be 1-5, and the corresponding delivery nodes would be 6-10.
The main problem I am trying to solve is when the drone’s battery becomes insufficient during delivery. In such cases, the drone synchronizes with an active vehicle, climbs aboard, charges while traveling along the vehicle’s route, and then resumes flight to the intended delivery node.
For instance, if the drone lacks sufficient battery after reaching pickup node 1, it would fly to a currently active vehicle at node i, travel along with the vehicle from i to j while charging, and then proceed to the delivery node (j → 6).
I’ve written the battery update constraint for the drone as follows:
for d in range(drone):
for i in range(1, num_orders + 1):
model.addConstrs(battery_level[i+num_orders, d] >= battery_level[i, d] - e*time_drone[i, f] + charging_rate*time_vehicle[f, l]
- e*time_drone[l, i+num_orders] - M*(5 - battery_need[i, d] - D[i, f, d] - D[f, l, d] - D[l, i+num_orders, d] - X[f, l, v])
for f in range(1, 2*num_orders+1) for l in range(1, 2*num_orders+2) for v in range(vehicle))
I’m encountering issues, and it seems like this constraint is not functioning as expected. I’m wondering if there could be a problem with the Big-M method I’m using. Below is my full code for reference.
import folium
import requests
import gurobipy as gp
from gurobipy import GRB
import pandas as pd
import numpy as np
import random
import distance_matrix_creation as dmc
orders_df = pd.read_csv('data/stage1_1_1.csv')
def generate_random_colors(num_colors):
folium_colors = ['green', 'pink', 'lightblue', 'blue', 'gray', 'darkred', 'darkgreen', 'darkblue', 'black',
'lightgreen', 'red', 'purple', 'white', 'lightgray', 'orange', 'lightred', 'cadetblue', 'beige', 'darkpurple']
colors = [random.choice(folium_colors) for _ in range(num_colors)]
return colors
v_speed = 60 * (5 / 18)
num_orders = 7
data = orders_df[0:num_orders]
vehicle = 2
drone = 2
M = 10000
battery_capacity = 150
e = 1
charging_rate = e * 2
flight_time_per_km = 60 # 초
food_ready_time = data['food_ready_time']
# 저장된 time_distance_matrix 불러오기
time_drone = np.load(f'time_distance_matrix_drone_{num_orders}.npy')
time_vehicle = np.load(f'time_distance_matrix_vehicle_{num_orders}.npy')
model = gp.Model('Vehicle_Drone_PD')
X = model.addVars(2*num_orders + 2, 2*num_orders + 2, vehicle, vtype=GRB.BINARY, name='X')
D = model.addVars(2*num_orders + 2, 2*num_orders + 2, drone, vtype=GRB.BINARY, name='D')
tw_vehicle = model.addVars(2*num_orders + 2, vehicle, vtype=GRB.CONTINUOUS, name="tw_vehicle")
tw_drone = model.addVars(2*num_orders + 2, drone, vtype=GRB.CONTINUOUS, name='tw_drone')
battery_level = model.addVars(2*num_orders + 2, drone, vtype=GRB.CONTINUOUS, name='battery_level')
battery_need = model.addVars(2*num_orders + 2, drone, vtype=GRB.BINARY, name='battery_need')
bin_charging = model.addVars(2*num_orders + 2, 2*num_orders + 2, drone, vtype=GRB.BINARY, name='bin_charging')
model.setObjective(
gp.quicksum(100.035 * time_vehicle[i, j] * X[i, j, v] for v in range(vehicle)
for i in range(2*num_orders + 2)
for j in range(2*num_orders + 2)) +
gp.quicksum(0.0138 * time_drone[i, j]*D[i, j, d] for d in range(drone)
for i in range(2*num_orders + 2)
for j in range(2*num_orders + 2)) +
gp.quicksum(tw_vehicle[2*num_orders + 1, v] for v in range(vehicle)),
GRB.MINIMIZE
)
for v in range(vehicle):
X[0, 0, v].ub = 0
for i in range(2*num_orders + 2):
for d in range(drone):
D[i, 0, d].ub = 0
for i in range(2*num_orders + 2):
for j in range(2*num_orders + 2):
model.addConstrs((D[i, j, d] + X[i, j, v] >= 2 - 2*(1 - bin_charging[i, j, d])
for d in range(drone) for v in range(vehicle)))
model.addConstrs((D[i, j, d] + X[i, j, v] <= 2 + 2*bin_charging[i, j, d]
for d in range(drone) for v in range(vehicle)))
for i in range(1, num_orders + 1):
model.addConstr(gp.quicksum(X[i, i + num_orders, v] for v in range(vehicle)) +
gp.quicksum(D[i, i + num_orders, d]*(1 - bin_charging[i, i + num_orders, d]) for d in range(drone)) == 1)
for v in range(vehicle):
model.addConstr(gp.quicksum(X[i, 2*num_orders + 1, v] for i in range(num_orders + 1, 2*num_orders + 1)) == 1)
for d in range(drone):
model.addConstr(gp.quicksum(D[i, 2*num_orders + 1, d]*(1 - bin_charging[i, 2*num_orders + 1, d]) for i in range(num_orders + 1, 2*num_orders + 1)) == 1)
for v in range(vehicle):
model.addConstr(gp.quicksum(X[0, i, v] for i in range(1, num_orders + 1)) == 1)
for d in range(drone):
model.addConstr(gp.quicksum(D[0, i, d] for i in range(1, num_orders+1)) == 1)
for v in range(vehicle):
for i in range(1, 2*num_orders + 1):
model.addConstr(gp.quicksum(X[i, j, v] for j in range(2*num_orders + 2))
- gp.quicksum(X[j, i, v] for j in range(2*num_orders + 2)) == 0)
for d in range(drone):
for i in range(1, 2*num_orders + 1):
model.addConstr(gp.quicksum(D[i, j, d] for j in range(2*num_orders + 2))
- gp.quicksum(D[j, i, d] for j in range(2*num_orders + 2)) == 0)
for d in range(drone):
for v in range(vehicle):
for f in range(1, 2*num_orders + 1):
model.addConstrs((battery_level[l, d] >= battery_level[f, d] + 2 * e * time_vehicle[f, l]
- M * (2 - X[f, l, v] - D[f, l, d]) for l in range(1, 2 * num_orders + 2)))
for i in range(1, 2*num_orders + 1):
model.addConstrs((battery_level[f, d] <= battery_level[i, d] - e*time_drone[i, f]
+ M*(3 - battery_need[i, d] - D[i, f, d] - X[f, l, v]) for l in range(1, 2*num_orders + 2)))
for d in range(drone):
for i in range(2*num_orders + 2):
for j in range(2*num_orders + 2):
model.addConstr((battery_level[j, d] <= battery_level[i, d] - e*time_drone[i, j]
+ M*(1 - D[i, j, d])))
for d in range(drone):
for v in range(vehicle):
for f in range(1, 2*num_orders + 1):
for l in range(1, 2*num_orders + 2):
model.addConstrs((tw_drone[f, d] >= tw_drone[i, d] + time_drone[i, f]
- M*(3 - battery_need[i, d] - X[f, l, v] - D[i, f, d]) for i in range(1, 2*num_orders + 1)))
model.addConstrs((tw_drone[f, d] >= tw_vehicle[f, v]
- M*(3 - battery_need[i, d] - X[f, l, v] - D[i, f, d]) for i in range(1, 2*num_orders + 1)))
model.addConstrs((tw_vehicle[f, v] >= tw_drone[i, d] + time_drone[i, f]
- M*(3 - battery_need[i, d] - X[f, l, v] - D[i, f, d]) for i in range(1, 2*num_orders + 1)))
model.addConstr(tw_drone[l, d] >= tw_drone[f, d] + time_vehicle[f, l]
- M*(2 - X[f, l, v] - D[f, l, d]))
for d in range(drone):
for i in range(2*num_orders + 2):
for j in range(2*num_orders + 2):
model.addConstrs((tw_drone[j, d] >= tw_drone[i, d] + time_drone[i, j]
- M*(1 - X[i, j, v] - D[i, j, d]) for v in range(vehicle)))
for i in range(2*num_orders + 2):
for j in range(2*num_orders + 2):
model.addConstrs((tw_vehicle[j, v] >= tw_vehicle[i, v] + time_vehicle[i, j] - M*(1 - X[i, j, v])
for v in range(vehicle)))
for d in range(drone):
model.addConstr(battery_level[0, d] == battery_capacity)
for d in range(drone):
for i in range(2*num_orders + 1):
model.addConstr(battery_level[i, d] >= 0)
for d in range(drone):
for i in range(2*num_orders + 2):
model.addConstr(battery_level[i, d] <= 0.5*battery_capacity - 0.0001 + 200*(1 - battery_need[i, d]))
model.addConstr(battery_level[i, d] >= 0.5*battery_capacity - 200*battery_need[i, d])
model.optimize()
-
Hi Dong Hyun Kim,
I’m encountering issues, and it seems like this constraint is not functioning as expected.
Can you give details of what you expect vs what you are observing?
- Riley
0 -
for d in range(drone): for i in range(1, num_orders + 1): model.addConstrs(battery_level[i+num_orders, d] >= battery_level[i, d] - e*time_drone[i, f] + charging_rate*time_vehicle[f, l] - e*time_drone[l, i+num_orders] - M*(5 - battery_need[i, d] - D[i, f, d] - D[f, l, d] - D[l, i+num_orders, d] - X[f, l, v]) for f in range(1, 2*num_orders+1) for l in range(1, 2*num_orders+2) for v in range(vehicle))
In my optimization model, when a drone reaches a pickup node (let’s denote it as a node
i) but does not have enough battery to proceed directly to the corresponding delivery node (i + num_orders), it needs to locate an active vehicle to follow. The idea is that the drone can travel with the vehicle, using its route temporarily to recharge along the way. Once the drone’s battery is sufficiently recharged, it can leave the vehicle and continue on to the delivery node (i + num_orders).The above constraint aims to update the drone's battery level as it moves along this coordinated route with the vehicle. In particular, the Big-M method is used here to capture different scenarios:
- If the drone has enough battery to go from the pickup node to the delivery node, it does so directly.
- If the drone lacks sufficient battery, then
battery_need[i, d] = 1becomes active, causing the drone to divert temporarily to follow the active vehicle’s path (X[f, l, v]), recharge, and then return to complete the original delivery.
However, the current model isn’t producing the intended results. In some cases, the drone flies directly to the final depot after visiting the pickup node
i, or the model returns as infeasible. My goal is for the drone to follow an optimized path, such as:-
if battery_need[2, 0] = 1 & D[j, 2, 0] = 1 then D[2, 5, 0] -> D[5, 10, 0] (where it recharges on the route segment
X[5, 10, 1]with the vehicle) -> D[10, 7, 0].
0 -
Ok, so if I understand correctly, it's not that the "constraint isn't functioning as expected", it's that your model just isn't correct yet?
0 -
I think that’s likely the case. I’ve been working on refining the model continuously, but it hasn’t been going well, which is why I wanted to ask for some guidance. I’ll give it some more try and reach out again if I have further questions.
0 -
I'd suggest starting with a tiny version of your problem, so that you can write the LP file out and inspect it - is it what you would expect? Then try fixing variables to the solution you'd expect and see if it's valid. If not there is a constraint which is wrong. If it is valid then you're missing a constraint (or a constraint is not strong enough).
You may find some useful tips here:
How do I diagnose a wrong result?1 -
Hello Riley,
Currently can we use generative-AI for complicated constraints and big-M parameters?
Thanks.
0 -
Hi L Yan,
Gen AI can be useful to a degree. Can you give us a bit more detail? Is your idea to use Gen AI for complicated constraints motivated by saving time, or where it is difficult to create the constraints yourself? By big-M parameters are you referring to PreSOS1BigM and PreSOS2BigM, or something else?
- Riley
0
Please sign in to leave a comment.
Comments
7 comments