I would like to use gurobi to implement such a cvrp problem:
1）There are n customer nodes, which are 1... n: The fixed depot node is 0.
2）The demand of each customer node is q_i
3）There is only one vehicle with a capacity limit Q, but every time the capacity of the vehicle is used up, it will be returned to the depot and refilled.
def solve_cvrp_bigM(V, N, E, d, Q, q, time_limit=None):
# V：include depot node 0 N：all customer node E：all edges
# d: cost q:demand Q:capacity limitation for the vehicle
model = gp.Model("CVRP")
# edge x 0-1 variable
x = {e: model.addVar(vtype=GRB.BINARY, name="x[{}]".format(e) ) for e in E}
# Vehicle's serviced capacity variable for customer node i
u = model.addVars(V,vtype=GRB.CONTINUOUS)
u[0] = 0 # for depot 0
model.update()
### objective
model.setObjective(gp.quicksum(d[e] * x[e] for e in E), GRB.MINIMIZE)
###
# in and out once and only once
model.addConstrs(gp.quicksum(x[i,j] for j in V if j != i) == 1 for i in N)
model.addConstrs(gp.quicksum(x[i,j] for i in V if i != j) == 1 for j in N)
# bigM model
model.addConstrs( ( (u[i] + q[j]) <= (u[j] + Q*(1-x[i,j])) ) for i in V for j in N if i!=j)
model.addConstrs( ( (u[i] + q[j])
>= ( u[j] - (Q - q[i] - q[j])*(1-x[i,j]) ) ) for i in V for j in N if i!=j)
# model.Params.outputFlag = False
# model.Params.threads = 1
model.Params.MIPGap = 0.1
if time_limit is not None:
model.Params.timeLimit = time_limit
model.optimize()
if model.SolCount <= 0:
return None, None
x_sol = {e: round(x[e].x) for e in x}
return (model.ObjVal), x_sol
The CVRP of only one vehicle that has been implemented so far is as above, but I don’t know how to make this vehicle refill every time it returns to the depot to continue serving customer nodes. could someone help me? Thanks very much!
Give an example:
**n** = 5
**d**:#(i,j,d_ij) (i=0..n)(j=0..n)
0 1 0.54
0 2 0.72
0 3 0.52
0 4 0.68
0 5 0.7
1 2 0.18
1 3 0.56
1 4 0.56
1 5 0.52
2 3 0.38
2 4 0.58
2 5 0.42
3 4 0.67
3 5 0.7
4 5 0.72
**q**: # q_i (i=1..n) q_0=0
0.6
0.9
0.6
0.5
0.3
**Q** = 1.0
The ideal solution should be：
[0, 5, 1, 0, 4, 0, 2, 0, 3,0]
In the CVRP, you want to ensure that the vehicle returns to the depot to refill its capacity and continue serving customers. To achieve this, you need to introduce a sub-tour elimination constraint to force the vehicle to return to the depot. Here's how you can modify your existing Gurobi model to include this constraint:
from gurobipy import *
def solve_cvrp_refill(V, N, E, d, Q, q, time_limit=None):
model = Model("CVRP with Refill")
x = {(i, j): model.addVar(vtype=GRB.BINARY) for i in V for j in V if i != j}
u = model.addVars(V, vtype=GRB.CONTINUOUS)
u[0] = 0
model.setObjective(quicksum(d[i, j] * x[i, j] for i, j in E), GRB.MINIMIZE)
model.addConstrs(quicksum(x[i, j] for j in V if j != i) == 1 for i in N)
model.addConstrs(quicksum(x[i, j] for i in V if i != j) == 1 for j in N)
model.addConstrs(u[i] + q[j] <= u[j] + Q * (1 - x[i, j]) for i in V for j in N if i != j)
model.addConstrs(u[i] >= u[j] + q[j] * x[i, j] for i in V for j in N if i != j)
model.addConstr(quicksum(x[j, 0] for j in N) >= 1)
model.Params.MIPGap = 0.1
if time_limit is not None:
model.Params.timeLimit = time_limit
model.optimize()
if model.SolCount <= 0:
return None, None
x_sol = {(i, j): round(x[i, j].x) for i, j in E}
return model.ObjVal, x_sol
In this modified model, I added a constraint model.addConstr(quicksum(x[j, 0] for j in N) >= 1) to ensure that the depot is visited at least once. This constraint forces the vehicle to return to the depot to refill its capacity.
Make sure that your input data, such as edge costs d and demand values q, are correctly defined for your problem instance. Also, ensure that you have imported the necessary Gurobi functions and libraries. This modified model should now handle the refill behavior you described.