Блог

Я пытаюсь решить проблему CVRP, используя приведенную ниже формулировку.

Состав CVRP, который я использовал

Я написал математическую модель, как показано ниже, но я получаю невыполнимые решения. Я не могу найти, где я ошибся. Я был бы очень рад, если бы вы могли помочь.

 m=2
Q=1500
V = [i for i in range(1, n 1)]
N = [0]   V
K = [k for k in range(1,m 1)]
A = [(i, j) for i in N for j in N if i != j]
c = {(i, j): np.hypot(x_c[i]-x_c[j], y_c[i]-y_c[j]) for i, j in A}
d = {i: rnd.randint(1,5) for i in N}

from gurobipy import Model, GRB, quicksum

mdl = Model('CVRP')

x = mdl.addVars(A,K, vtype=GRB.BINARY)
Y = mdl.addVars(N,K, vtype=GRB.CONTINUOUS)
L = mdl.addVar()

mdl.modelSense = GRB.MINIMIZE
mdl.setObjective(L)

mdl.addConstrs(quicksum(x[i, j,k] for j in N if i!=j ) <= 1 for i in N if i == 0  for k in K )

mdl.addConstrs(quicksum(x[i, j,k] for j in N for k in K if j!=i ) == 1 for i in V  )

mdl.addConstrs(quicksum(x[i, j,k] for j in N if j!=i) == quicksum(x[j, i,k] for j in N if j!=i ) for i in V for k in K )

mdl.addConstrs(quicksum(x[i, j,k]*d[i] for i,j in A) == Y[0,k] for k in K)

mdl.addConstrs( Y[j,k] <= Y[i,k]- d[j]   Q*(1 - x[i,j,k]) for i in N for j in N for k in K if j!=i)

mdl.addConstrs(Y[0,k]<= Q for k in K)

mdl.addConstrs(quicksum(x[i, j,k]*c[i,j] for i,j in A) == L for k in K)

mdl.Params.MIPGap = 0.05
mdl.Params.TimeLimit = 300000
mdl.optimize()