A problem with the solution printing and objective value, please help!
AnsweredHello, for my bachelors thesis that is due in a week, i am working on an MILP for a heterogenous CVRP and I am running into a slight problem and am not quite sure what I should do to fix it. The MILP runs and gets an objective value which is the minimum total distance, it is however a lot smaller than the actual solution is.
For example, the best objective solution = 3995. With the produced routes:
{'tractor_0': [], 'car_1': [8, 9, 7], 'tractor_2': [], 'car_3': [3, 1], 'tractor_4': [], 'tractor_5': [6, 5, 4, 2]}
However, in the case with my MILP it should start and end each route at the depot: 0.
So the actual routes should look like:
{'tractor_0': [], 'car_1': [0,8, 9, 7,0], 'tractor_2': [], 'car_3': [0,3, 1,0], 'tractor_4': [], 'tractor_5': [0,6, 5, 4, 2,0]}.
The objective value should therefore be higher as there is also a distance from and to each node, it seems to me that the MILP doesn't account for the distances of the depot to the nodes but I am unsure on what to do about it.
Could someone please help me? (edit: I removed some redundant constraints)
# Importing required libraries
import numpy as np
from gurobipy import Model, GRB, quicksum
import pandas as pd
import os
# Define a function to set up variables and constraints for the CVRP problem
def define_variables(distance_matrix_dict, num_vehicles, capacity_dict, demand_list, vehicle_types):
# Number of clients
n = len(demand_list)
# Set of clients
N = [i for i in range(1, n)]
# Set of clients plus the depot (depot is at index 0)
V = [i for i in range(n)]
# Set of arcs (i, j) where i != j
A = [(i, j) for i in V for j in V if i != j]
# Total number of vehicles needed
total_vehicles_needed = num_vehicles
# Cost (distance) dictionary for each arc and each vehicle type
c = {(i, j, k): distance_matrix_dict[vehicle_types[k]][i][j] for i, j in A for k in range(total_vehicles_needed)}
# Capacity dictionary for each vehicle type
Q = {k: capacity_dict[vehicle_types[k]] for k in range(total_vehicles_needed)}
# Demand dictionary for each client
q = {i: demand_list[i] for i in N}
# Initialize Gurobi model
mdl = Model("CVRP")
mdl.Params.Presolve = 2
mdl.Params.NoRelHeurTime = 2.0
# Decision variables
x = mdl.addVars(A, range(total_vehicles_needed), vtype=GRB.BINARY)
u = mdl.addVars(N, range(total_vehicles_needed), vtype=GRB.CONTINUOUS)
# Objective: Minimize the total distance traveled
mdl.modelSense = GRB.MINIMIZE
mdl.setObjective(quicksum(x[i, j, k] * c[i, j, k] for (i, j) in A for k in range(total_vehicles_needed)))
# Constraints
# Each client should be visited at least once
for i in N:
mdl.addConstr(quicksum(x[i, j, k] for j in N if j != i for k in range(total_vehicles_needed)) == 1, name="VisitOnceFrom_{}".format(i))
for j in N:
mdl.addConstr(quicksum(x[i, j, k] for i in N if i != j for k in range(total_vehicles_needed)) == 1, name="VisitOnceTo_{}".format(j))
for i in N:
for k in range(total_vehicles_needed):
big_M = 10000 # A sufficiently large constant
mdl.addConstr(q[i] <= Q[k] + big_M * (1 - quicksum(x[i, j, k] for j in V if j != i)), name="BigMConstraint_{}_{}".format(i, k))
# Ensure total demand serviced by each vehicle 'k' doesn't exceed its capacity.
for k in range(total_vehicles_needed):
mdl.addConstr(quicksum(q[i] * x[i, j, k] for i in N for j in V if i != j) <= Q[k], name="Capacity_{}".format(k))
# Modified to prevent intermittent depot visits.
for i in N:
for k in range(total_vehicles_needed):
mdl.addConstr(quicksum(x[i, j, k] for j in N if j != i) == quicksum(x[j, i, k] for j in N if j != i), name="SameVehicleInOut_{}_{}".format(i, k))
# Ensure the same vehicle 'k' enters and leaves the depot.
# Set MIP Gap and Time Limit
mdl.Params.MIPGap = 0.1
mdl.Params.TimeLimit = 600 # 600 seconds
# Write model to a file (useful for debugging)
mdl.write("myLP.lp")
# Optimize the model
mdl.optimize()
# Check the status of the solution
if mdl.SolCount > 0:
print("Best Objective Value Found:", mdl.ObjVal)
else:
print("No feasible solution found.")
# Check for infeasibility
if mdl.status == GRB.INFEASIBLE:
mdl.computeIIS()
print('\nThe following constraint(s) cannot be satisfied:')
for c in mdl.getConstrs():
if c.IISConstr:
print('%s' % c.constrName)
# Extract the routes
# Placeholder for returning results
total_distance = 0
used_vehicles_lin = []
df_route_order = {}
vehicle_loads = {}
visited_nodes = set()
if mdl.SolCount > 0:
for k in range(total_vehicles_needed):
route = [0] # Start at depot
load = 0 # Initialize load
for i, j in A:
if x[i, j, k].x > 0.5: # If arc is part of the solution
total_distance += distance_matrix_dict[vehicle_types[k]][i][j]
route.append(j)
load += q.get(j, 0)
visited_nodes.add(j)
if len(route) > 0:
total_distance += distance_matrix_dict[vehicle_types[k]][route[-1]][0]
route.append(0) # End at depot
# Skip routes that only consist of 0-0
if set(route) != {0}:
df_route_order[f"{vehicle_types[k]}_{k}"] = route
vehicle_loads[f"{vehicle_types[k]}_{k}"] = load
used_vehicles_lin.append(vehicle_types[k])
all_nodes = set(N) # N is your list of client nodes
if visited_nodes == all_nodes:
print("All nodes have been visited.")
else:
print("Not all nodes have been visited.")
print("Nodes not visited:", all_nodes - visited_nodes)
# Print the routes
print(df_route_order)
print(vehicle_loads)
# Placeholder for returning results
return total_distance, df_route_order, used_vehicles_lin
# Main function to call the define_variables function
def main(distance_matrix_dict, num_vehicles, capacity_dict, demand_list, vehicle_types):
total_distance, df_route_order = define_variables(distance_matrix_dict, num_vehicles, capacity_dict, demand_list, vehicle_types)
return total_distance, df_route_order
# You can call the function by passing the required arguments:
# distance_matrix_dict, num_vehicles, capacity_dict, demand_list, vehicle_types
def main(distance_matrix_dict, num_vehicles, capacity_dict, demand_list, vehicle_types):
total_distance, df_route_order, used_vehicles_lin = define_variables(distance_matrix_dict, num_vehicles, capacity_dict, demand_list, vehicle_types)
print(total_distance)
print(df_route_order)
return total_distance, df_route_order, used_vehicles_lin
if __name__ == "__main__":
distance_matrix_dict = {'car': [[0, 973, 382, 1342, 914, 1103, 298, 186, 357, 495]
, [988, 0, 729, 466, 231, 230, 795, 1050, 1061, 745]
, [382, 723, 0, 1093, 705, 811, 238, 414, 402, 285]
, [1348, 429, 1120, 0, 573, 464, 1144, 1410, 1071, 846]
, [924, 250, 668, 576, 0, 278, 749, 986, 972, 656], [1105, 197, 788, 464, 286, 0, 928, 1202, 934, 710]
, [294, 797, 238, 1158, 738, 933, 0, 419, 512, 452],
[191, 1045, 414, 1415, 986, 1176, 420, 0, 337, 475],
[364, 1056, 402, 1163, 1007, 1114, 517, 341, 0, 311], [499, 788, 284, 943, 701, 746, 452, 476, 311, 0]],
'tractor':
[[0, 1745, 1087, 2289, 1653, 1967, 872, 508, 952, 1480],
[1888, 0, 1259, 609, 412, 342, 1244, 2269, 1686, 1508],
[1073, 1118, 0, 1675, 1027, 1269, 595, 1330, 699, 522],
[2285, 706, 1671, 0, 854, 784, 1641, 2665, 2128, 1950],
[1703, 355, 1062, 861, 0, 382, 1059, 2077, 1446, 1269],
[2006, 319, 1253, 809, 411, 0, 1348, 2241, 1610, 1433],
[876, 1113, 588, 1658, 1021, 1318, 0, 1281, 807, 981],
[499, 2153, 1426, 2697, 2061, 2350, 1302, 0, 739, 1339],
[862, 1680, 699, 2171, 1490, 1623, 814, 655, 0, 613],
[1453, 1502, 521, 1992, 1311, 1445, 987, 1245, 615, 0]]}
capacity_dict = {'car': 1100, "tractor": 5000}
demand_list = [0, 249, 882, 434, 1271, 245, 786, 480, 272, 127]
used_vehicles = ['tractor', 'car', 'tractor', 'car', 'tractor', 'tractor']
num_vehicles = len(used_vehicles)
main(distance_matrix_dict, num_vehicles, capacity_dict, demand_list, used_vehicles)
I hope someone will be able to help me!
Thank you so much in advance!
-
Hi Jordi,
In the flow conservation constraints (last set of constraints above), you do not consider the arcs from and to the depot. You need to include them here. If this results in infeasible solutions, then there is an issue somewhere else.
Here are Python notebooks that show different VRP formulations and might help in your case.
Best regards,
Mario0
Please sign in to leave a comment.
Comments
1 comment