help with modeling
回答済みtrying to implement VRPSPD following the following formulation, but I can't.
Can someone help me?
I don't know what I'm doing wrong
my code looks like this
import gurobipy as gp
V = [[0, 300, 713, 890, 828, 978, 1202, 476, 974, 1253],
[300, 0, 825, 721, 990, 1031, 1048, 281, 1029, 1092],
[713, 825, 0, 746, 1468, 1681, 903, 689, 1676, 961],
[890, 721, 746, 0, 1696, 1749, 328, 441, 1747, 371],
[828, 990, 1467, 1696, 0, 385, 2018, 1257, 379, 2066],
[978, 1031, 1680, 1749, 385, 0, 2077, 1313, 6, 2118],
[1202, 1048, 903, 328, 2018, 2077, 0, 768, 2075, 59],
[476, 281, 689, 441, 1257, 1313, 768, 0, 1310, 812],
[974, 1029, 1676, 1747, 379, 6, 2075, 1310, 0, 2116],
[1253, 1092, 961, 371, 2066, 2118, 59, 812, 2116, 0]] # set of customers
n = len(V) # number of customers
Q = 500 # capacity
MD = 38999 # Maximum distance for all k
Klinha = 2 # number of vehicles available
demands = {}
demands['pickup'] = [8,62,17,50,6,49,9,9,15,51]
demands['delivery'] = [52,44,55,38,56,28,8,28,42,32]
origins = [i for i in range(n)]
destinations = [j for j in range(n)]
vehicles = [i + 1 for i in range(Klinha)]
custos = dict()
for i, origem in enumerate(origins):
for j, destino in enumerate(destinations):
custos[origem, destino] = V[i][j]
m = gp.Model()
# variables
x = m.addVars(origins,destinations, vehicles, vtype=gp.GRB.BINARY)
y = m.addVars(origins,destinations, vtype=gp.GRB.INTEGER) # pickup
z = m.addVars(origins,destinations, vtype=gp.GRB.INTEGER) # delivery
# objective function
m.setObjective(gp.quicksum(
V[i][j]*x[i,j,k]
for i in origins
for j in destinations
for k in vehicles
), sense=gp.GRB.MINIMIZE)
# constraints
r1 = m.addConstrs(
gp.quicksum(x[i,j,k] for i in origins for k in vehicles) == 1
for j in destinations
)
r2 = m.addConstrs(
gp.quicksum(x[i,j,k] for i in origins) - gp.quicksum(x[j,i,k] for i in origins) == 0
for j in destinations
for k in vehicles
)
r3 = m.addConstrs(
gp.quicksum(x[0,j,k] for j in destinations) <= 1
for k in vehicles
)
r4 = m.addConstrs(
gp.quicksum(
V[i][j]*x[i,j,k] for i in origins for j in destinations) <= MD
for k in vehicles
)
r5 = m.addConstrs(
gp.quicksum(y[j,i] for i in origins if j != 0) - gp.quicksum(y[i,j] for i in origins if j != 0) == demands['pickup'][j]
for j in destinations
)
r6 = m.addConstrs(
gp.quicksum(z[j,i] for i in origins if j != 0) - gp.quicksum(z[i,j] for i in origins if j != 0) == demands['delivery'][j]
for j in destinations
)
r7 = m.addConstrs(
gp.quicksum(x[i,j,k] for k in vehicles) * (y[i,j] + z[i,j]) <= Q
for i in origins
for j in destinations
)
#execute
m.optimize()
I get the following error
Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (win64)
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 54 rows, 400 columns and 1084 nonzeros
Model fingerprint: 0x762ea6aa
Variable types: 0 continuous, 400 integer (200 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+03]
Objective range [6e+00, 2e+03]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 4e+04]
Presolve time: 0.00s
Explored 0 nodes (0 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 1 (of 4 available processors)
Solution count 0
Model is infeasible
Best objective -, best bound -, gap -
0
-
正式なコメント
-
Gurobi Staff
This post is more than three 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. -
-
-
The Knowledge Base article How do I determine why my model is infeasible? explains how to proceed in such a case.
0 -
-
I did the tests, as a return I got this model.ilp file
containing the following
\ Model _copy
\ LP format - for model browsing. Use MPS format to capture full model detail.
Minimize
Subject To
R93: - C1157 + C1173 + C1175 + C1176 + C1177 + C1178 + C1179 + C1180
+ C1181 + C1182 + C1183 + C1184 + C1185 + C1186 + C1187 + C1188 + C1189
- C1191 - C1208 - C1225 - C1242 - C1259 - C1276 - C1293 - C1310 - C1327
- C1344 - C1361 - C1378 - C1395 - C1412 - C1429 = 1
R98: - C1157 + C1173 + C1175 + C1176 + C1177 + C1178 + C1179 + C1180
+ C1181 + C1182 + C1183 + C1184 + C1185 + C1186 + C1187 + C1188 + C1189
- C1191 - C1208 - C1225 - C1242 - C1259 - C1276 - C1293 - C1310 - C1327
- C1344 - C1361 - C1378 - C1395 - C1412 - C1429 = 24
Bounds
C1157 free
C1173 free
C1175 free
C1176 free
C1177 free
C1178 free
C1179 free
C1180 free
C1181 free
C1182 free
C1183 free
C1184 free
C1185 free
C1186 free
C1187 free
C1188 free
C1189 free
C1191 free
C1208 free
C1225 free
C1242 free
C1259 free
C1276 free
C1293 free
C1310 free
C1327 free
C1344 free
C1361 free
C1378 free
C1395 free
C1412 free
C1429 free
Generals
C1157 C1173 C1175 C1176 C1177 C1178 C1179 C1180 C1181 C1182 C1183 C1184
C1185 C1186 C1187 C1188 C1189 C1191 C1208 C1225 C1242 C1259 C1276 C1293
C1310 C1327 C1344 C1361 C1378 C1395 C1412 C1429
End0 -
-
-
If you look at the two constraints \(\texttt{R93}\) and \(\texttt{R98}\), you will see that both constraints have the exact same left-hand side and set the respective left-hand side to either 1 or 24, which is infeasible.
So now you have to find out how those two constraint made it into your model and try to fix it.
0 -
投稿コメントは受け付けていません。
コメント
4件のコメント