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

У меня есть линейная модель для модели маршрутизации транспортных средств. Теперь я хочу ввести ограничение на максимальное количество активных ребер, что приведет к тому, что не каждый узел можно будет посетить. Однако каждый маршрут должен начинаться и заканчиваться в депо (узел 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, депо, больше не является обязательным для посещения. Может ли кто-нибудь помочь мне немного дальше с этим? Заранее спасибо!


vehicle-routing linear-programming cplex docplex simplex
person Marty    schedule 08.05.2019    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Чтобы заставить депо входить и выходить, вы не должны ослаблять == для депо. Таким образом, вам нужно разделить ограничения (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)

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

person Daniel Junglas    schedule 08.05.2019
comment
Спасибо за комментарий! Я думаю, что применять отдельные ограничения для депо не нужно, так как в «V» депо не включено, поэтому ограничение не применяется к депо. (Поправьте меня, если я ошибаюсь). Вторая проблема, которую вы упомянули, и есть та, с которой я сейчас имею дело. Ограничение каждого узла с «активным» входящим ребром должно иметь «активное» исходящее ребро и наоборот. Таким образом, должна быть проверка, если узел посещен или покинут, тогда узел также должен быть оставлен и посещен. Я пытался это реализовать, но возник вопрос, возможно ли это на самом деле в LO? - person Marty; 08.05.2019
comment
Ограничение должно быть довольно простым: сумма всех переменных, соответствующих входящим дугам, должна быть равна сумме всех переменных, соответствующих исходящим дугам. Я упустил разницу между V и N. Так что, если вы хотите принудительно отправить что-то из депо или в него, вам просто нужно добавить ограничение: сумма переменных, соответствующих дугам, выходящим/входящим в депо, равна ›= 1. - person Daniel Junglas; 08.05.2019
comment
Спасибо еще раз. Простое сравнение суммы входящих и исходящих в целом также может привести к входу в один узел и выходу из другого, который не ведет к связанным маршрутам. Таким образом, его следует проверять для каждого узла отдельно. Таким образом, если x[2,5] равно 1, то в множестве x[5,*] должна быть одна дуга, где * может быть любой другой вершиной или депо. Я новичок в Docplex, поэтому мне трудно реализовать это ограничение. Знаете, как я мог это реализовать? - person Marty; 09.05.2019
comment
Кроме того: я создал дополнительную переменную решения, чтобы отслеживать посещенные узлы с помощью g = mdl.binary_var_dict(N, name='g'). Во-вторых, я добавил ограничения индикатора для посещенных узлов с помощью mdl.add_indicator_constraints(mdl.indicator_constraint(g[i], mdl.sum(x[i,j] for j in V if j!= i) == 1) for i in N if i!=0 and j!=0). Более конкретный вопрос: как я могу установить g[i] равным 1, если узел посещен и, таким образом, x[i,node] равен 1? - person Marty; 09.05.2019
comment
Да, конечно, количество входящих дуг равно количеству исходящих дуг. Ограничения должны быть на узел. Я думал, что это то, что я сказал (по крайней мере, я пытался). Для этого ограничения должно работать что-то простое: mdl.add_constraints(mdl.sum(x[j, i] for j in N if j != i) == mdl.sum(x[i, j] for j in N if j != i) for i in N). Что касается остальных, я думаю, вы хотите найти что-то, называемое ограничениями исключения подтура. Также я думаю, что вам не нужны эти дополнительные переменные. Узел i посещается, если sum(x[i,j] for j in N j != i) равно 1 (т. е. если есть дуга, выходящая из узла). - person Daniel Junglas; 09.05.2019
comment
Спасибо, это сработало для меня! Я добавил ограничение, как вы предложили, но изменил N на V, так как это также относится к депо, потому что каждый маршрут должен начинаться и заканчиваться в депо: mdl.add_constraints(mdl.sum(x[j, i] for j in V if j != i) == mdl.sum(x[i, j] for j in V if j != i) for i in V). Для меня нормально найти несколько маршрутов, которые можно проехать друг за другом, так что основная проблема теперь решена! Это было проще, чем я думал на первый взгляд. Еще раз спасибо @Daniel! - person Marty; 12.05.2019