VRP with optional nodes
Hi all,
I am currently working on a VRP problem where the vehicles are electric. This means that I have range restricitons, and charging stations as nodes which are optional to visit.
In my model I have the following:
O = [0] # depot
N = [1,2,3,4,5,6,7] # deliveries
V = [0,1,2,3,4,5,6,7] # all nodes which must be visited
F = [8,9] # charging stations.
G = [0,1,2,3,4,5,6,7,8,9] # all the nodes
In addition I have a distance matrix with distances between all nodes. I also have demand in weight at every delivery point. My current model looks like this:
m = Model('E-VRP')
x = m.addVars(G, G, vtype=GRB.BINARY)
lw = m.addVars(G, vtype=GRB.CONTINUOUS) # for calculating load weight
d = m.addVars(G, vtype=GRB.CONTINUOUS) # for calculating distance driven
m.setObjective(quicksum(distance[i,j]*x[i,j] for i in G for j in G if i!=j), GRB.MINIMIZE)
# Restrictions
m.addConstrs(quicksum(x[i,j] for j in V if j!=i)== 1 for i in N) #1
m.addConstrs(quicksum(x[i,j] for i in V if i!=j)== 1 for j in N) #2
m.addConstrs ((x[i,j]==1) >> (lw[i] + Dw[i] == lw[j]) #3
for i in G for j in G if i!=0 if j!=0)
m.addConstrs (lw[i] >= Dw[i] for i in G); #4 (Dw being demand in weight at delivery)
m.addConstrs (lw[i] <= Qw for i in G); #5 (Qw being weight capacity of vehicle)
m.addConstrs ((x[i,j]==1) >> (d[i] + distance[i,j] == d[j])
for i in G for j in G if j>0); #6
m.addConstrs (d[i] <= Qr for i in G); #7 (Qr being range restriction of vehicle)
A combination of the first three restrictions make the model a working capacitated vehicle routing problem. It starts and ends at depot (0), and if Qw is less than lw, the model will make multiple routes.
The problem comes when I impose range restrictions. Where I have two problems:
First, the model will not make charging stations part of the route. I understand that restriction #1 and #2 states that there must be a conection from list V to N, and vice versa, meaning that for node j, there must at be an i in list V (which does not include charging stations). However, whenever I try to "loose up" the two first restricitons, the model will suggest subtours that does not start nor end at depot. Does anyone have any suggestions to how I can solve this?
Second, my variable d, which keeps track of the distance travelled, will only add up distance to the last node prior to returning to depot. I realize that my code j>0 states that the depot cannot be a destination in my travel variable, however, this is the only way I have had it to work for all the other nodes.
Any help to these questions would be much appreciated.
Brgds,
Viktor
-
Official comment
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
Post is closed for comments.
Comments
1 comment