# 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

Please sign in to leave a comment.

## Comments

0 comments