I have a linear model for a capacity vehicle routing model. Now I want to put in a constraint on the maximum number of active edges which will result in the fact that not each node can be visited. However each route should start and end at the depot (node 0). I have the following model:
Input:
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, …})
Model:
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)
To implement the constraint of a maximum of active edges I added the following constraint:
# (5) Constraint: Set maximum of active edges
mdl.add_constraint(mdl.sum(x[i,j] for i,j in A) <= 6)
Thereby I should adjust the '==' operator to '<=' in constraint (1) and (2). However, the result is that also node 0, the depot, is not mandatory to visit anymore. Can anyone help me a bit further with this? Thank you in advance!
In order to force the depot being entered and exited you must not relax the == for the depot. So you have to split constraints (1) and (2) for the depot and non-depot nodes:
# 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)
I did not think about this a lot but now you may also need a constraint that requires for all nodes the number of incoming selected arcs to be equal to the number of outgoing selected arcs. That is, if a route enters a node then it must also exit that node.