VRP problem with time constraints
OngoingDear community,
I'm trying to model a very basic VRP problem with time constraints. In the code below, please check the time constraint I wrote in two different ways. The constraint in the comment (quadratic) works, but the same constraint (without comment) returns an infeasible result. Could you please help me to understand where the problem is?
depot_indices = [8]
trip_indices = [0, 1, 2, 3, 4, 5, 6, 7]
bus_indices = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
time = [[100 58 58 58 12 12 12 12 12]
[ 58 100 58 58 12 12 12 12 12]
[ 58 58 100 58 12 12 12 12 12]
[ 58 58 58 100 12 12 12 12 12]
[ 10 10 10 10 100 49 49 49 11]
[ 10 10 10 10 49 100 49 49 11]
[ 10 10 10 10 49 49 100 49 11]
[ 10 10 10 10 49 49 49 100 11]
[ 13 13 13 13 11 11 11 11 0]]model = Model("vrp")
""" Trip scheduling related variables"""
# If the arc(i, j) is traversed by bus k.
x = model.addVars(trip_indices + depot_indices, trip_indices + depot_indices, vtype=GRB.BINARY, name="x")
# Num buses
n = model.addVar(name="n")
# Service start time at node k
T = model.addVars(trip_indices, name="T")
# Waiting time after trip i until trip j.
W = model.addVars(trip_indices + depot_indices, trip_indices + depot_indices, name="W")
# Objective function.
obj = model.addVar(name="objective")"""=============== CONSTRAINTS ==============="""
model.addConstr(obj == quicksum(time[i, j] * x[i, j]
for i in trip_indices + depot_indices
for j in trip_indices + depot_indices))model.addConstrs(quicksum(x[i, j] for j in trip_indices) + x[i, 8] == 1 for i in trip_indices)
model.addConstrs(quicksum(x[i, j] for i in trip_indices) + x[8, j] == 1 for j in trip_indices)model.addConstr(quicksum(x[8, j] for j in trip_indices) <= 12)
model.addConstr(quicksum(x[i, 8] for i in trip_indices) <= 12)
model.addConstr(n == quicksum(x[8, i] for i in trip_indices))# Time constraint
# model.addConstrs(x[i, j] * (T[i] + time[i, j]) <= x[i, j] * T[j]
# for i in trip_indices
# for j in trip_indices)model.addConstrs(T[i] + time[i, j] - time[i, j] * (1 - x[i, j]) <= T[j]
for i in trip_indices
for j in trip_indices)model.addConstrs(T[i] == service_start[i] for i in trip_indices)
# Waiting time at each node.
model.addConstrs(W[i, j] == x[i, j] * (T[j] - T[i] - time[i, j])
for i in trip_indices
for j in trip_indices)
model.addConstrs(W[8, j] == x[8, j] * (T[j] - time[8, j]) for j in trip_indices)model.setObjective(obj, GRB.MINIMIZE)
model.optimize()
-
Did you have a look at the KB article How do I determine why my model is infeasible? This should help you find the source of your infeasibility.
0 -
Hi, thank you for the insight. I'm trying to use computeIIS, only including that particular constraint. From the documentation,
"To give an example of when these attributes might be useful, consider the case where an initial model is known to be feasible, but it becomes infeasible after adding constraints or tightening bounds. If you are only interested in knowing which of the changes caused the infeasibility, you can force the unmodified bounds and constraints into the IIS. That allows the IIS algorithm to focus exclusively on the new constraints, which will often be substantially faster."
Could you please give a small example of how I can force only a particular constraint to be checked? The information on IISConstrForce, unfortunately, is not very clear to me.
0 -
You can force a particular constraint via setting the corresponding ISSQConstrForce attribute to 1. In your case this would look similar to
Time constraint
cons = model.addConstrs(x[i, j] * (T[i] + time[i, j]) <= x[i, j] * T[j]
for i in trip_indices
for j in trip_indices)
for i in trip_indices:
for j in trip_indices:
cons[i,i].ISSQConstrForce = 1Best regards,
Jaromił0
Please sign in to leave a comment.
Comments
3 comments