I am currently working on a VRP problem where the vehicles are electric. This means that I have range restrictions, and charging stations as nodes which are optional to visit.
In my model I have the following:
O =  # 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 the 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 restrictions #1 and #2 state that there must be a connection from list
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 restrictions, the model will suggest subtours that do not start nor end at the depot. Does anyone have any suggestions as to how I can solve this?
Second, my variable
d, which keeps track of the distance travelled, will only add up the distance to the last node prior to returning to the 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.