CVRP без посещения каждого узла

Question

У меня есть линейная модель для модели маршрутизации транспортных средств большой вместимости.Теперь я хочу ограничить максимальное количество активных ребер, что приведет к тому, что не каждый узел будет посещен.Однако каждый маршрут должен начинаться и заканчиваться в депо (узел 0).У меня есть следующая модель:

Ввод:

n = Number of Clients
N = List of Nodes
V = List of nodes plus depot
Q = Vehicle Capacity
q = Demands per Client Dictionary

A = All Possible Roads (eg. [(0,1),(1,2),(2,3),(3,0),(2,0)])
c = All Distances Dictionary (eg. {(0, 1): 90, (1,2): 50, …})

Модель:

mdl = Model('CVRP')

x = mdl.binary_var_dict(A, name='x')
u = mdl.continuous_var_dict(N, ub=Q, name='u')

# Objective: Maximize Profit (profit - cost)
mdl.maximize(mdl.sum(q[i]*x[i,j] - c[i,j]*x[i,j] for i,j in A))

# (1) Constraints: Make sure end once in each node
mdl.add_constraints(mdl.sum(x[i,j] for j in V if j!=i) == 1 for i in N)

# (2) Constraints: Make sure leave each node once
mdl.add_constraints(mdl.sum(x[i,j] for i in V if i!=j) == 1 for j in N)

# (3) Constraints: Fill of container is waste current contianer + past containers
mdl.add_indicator_constraints(mdl.indicator_constraint(x[i,j], u[i]+q[j]==u[j]) for i,j in A if i!=0 and j!=0)

# (4) Constraints: Have to take all waste from a container
mdl.add_constraints(u[i]>=q[i] for i in N)

solution = mdl.solve(log_output=True)

Чтобы реализовать ограничение максимума активных ребер, я добавил следующее ограничение:

# (5) Constraint: Set maximum of active edges
mdl.add_constraint(mdl.sum(x[i,j] for i,j in A) <= 6)

Таким образом, я должен настроить оператор '==' на '<=' в ограничениях (1) и (2).Однако в результате узел 0, депо, не является обязательным для посещения.Кто-нибудь может помочь мне немного дальше с этим?Заранее спасибо! </p>

Answer 1

Для того, чтобы заставить депо входить и выходить, вы не должны ослаблять == для депо.Таким образом, вы должны разделить ограничения (1) и (2) для узлов депо и не-депо:

# Depot
mdl.add_constraints(mdl.sum(x[0,j] for j in V if j!=i))
mdl.add_constraints(mdl.sum(x[i,0] for i in V if i!=j))
# Non-Depot
mdl.add_constraints(mdl.sum(x[i,j] for j in V if j!=i) <= 1 for i in N if N != 0)
mdl.add_constraints(mdl.sum(x[i,j] for i in V if i!=j) <= 1 for j in N if N != 0)

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