The Capacitated Vehicle Routing Problem


It appears that we are on to something!

The mTSP model gave us some promising results, so we decided to go ahead with the multiple delivery campaigns that will run in parallel. But it turns out that the sleighs have limited capacity.

Can you help?

We knew that the mTSP model is not the ideal solution. Not only are the tours uneven, but we have no way to take into account the capacity of the vehicle, or the possibility that the nodes have different levels of demand.

If we would like to incorporate these aspects in our analysis, then we would need to follow a VRP-based approach.

We combine all nodes into a single list.

We are using the above parameter variable to set the number of facilities to be opened.

Note that in the 2nd constraint we use n to define the number of facilities to be opened.

In the above code we are iterating through our sets of facilities and customers.

Wherever we find a pair that is connected, we will append the origin and destination coordinates of a link between them to vect_orig and vect_dest, respectively.


from pulp import *
from scipy.spatial import distance

# Calculate distance matrix 
dist_matrix = distance.cdist(cust_coord, facil_coord, 'euclidean')

# Initialise problem
prob = LpProblem('prob', LpMinimize)

# Define sets of customers and facilities
S = [('S'+str(i+1)) for i in range(num_facility)]
D = [('D'+str(i+1)) for i in range(num_customer)]
H = [('H'+str(i+1)) for i in range(num_vehicles)]
N = S + D

# Prepare distance matrix parameters
d = {customer:{facility:dist_matrix[i][j] for j,facility in enumerate(N)} for i,customer in enumerate(N)}
p = {vehicle:payload[i] for i,vehicle in enumerate(H)}
c = {vehicle:cost_h[i] for i,vehicle in enumerate(H)}

# Define decision variables
x = LpVariable.dicts('x', (N,N), lowBound = 0, upBound = 1, cat = LpInteger)
f = LpVariable.dicts('f', (N,N), lowBound = 0, cat = LpInteger)

# Objective function
prob += lpSum([lpSum([x[i][j]*d[i][j]]) for j in N for i in N]) + lpSum([cost * x[i][j] for i in S for j in D])

# Constraint 1: Vehicle Equilibrium
for i in D:
    prob += lpSum([x[j][i] for j in N]) - lpSum([x[i][j] for j in N]) == 0

# Constraint 2: Flow Equilibrium (assuming demand of one unit of cargo at each demand point)
for i in D:
    prob += lpSum([f[j][i] for j in N]) - lpSum([f[i][j] for j in N]) == 1

# Constraint 3: Cargo flow must not exceed vehicle payload
for i in N:
    for j in N:
        prob += f[i][j] <= payload * x[i][j]

# Constraint 4: Return to the supply depot with no cargo
for i in N:
    for j in S:
        prob += f[i][j] == 0

# Constraint 5: Ensure no vehicle waits at any node
for i in N:
    prob += x[i][i] == 0

# Constraint 6: Ensure that at least one vehicle leaves the depot
for i in S:
    prob += lpSum([x[i][j] for j in D]) >= 1

# Constraint 7: All nodes must be visited
for i in D:
    prob += lpSum([x[i][j] for j in N]) == 1

# Constraint 8: Sub-tour elimination
for i in D:
    for j in D:
        prob += x[i][j] + x[j][i] <= 1 

# Constraint 9: Budget constraint
prob += lpSum([cost * x[i][j] for i in S for j in D]) <= budget

# Solve the model
status = prob.solve()