Understanding Capacity Constrained Delivery Planning Problem (CVRP) Formulation and Python Program

We tried to formulate and simulate capacity constrained delivery planning problems (CVRP) using the following URL:

Reference: Optimizing Delivery Planning Issues with Python
URL: https://www.letsopt.com/entry/2020/08/30/180258
Created: August 30, 2020
By: creselia 2012

However, in the process of trying, I could not understand why the following MTZ constraint expression and python program match.
I would appreciate it if you could tell me the reason why Python's program in the URL I used as a reference, especially MTZ constraints, is correct.

There are two reasons why I didn't understand.

##MTZ constraint
for i in range (1, num_nodes):
    for jin range (1, num_nodes):
        if i!=j and demand[i]+demand[j]<=capacity:
            problem+=u[i-1]-u[j-1]+capacity*x[i][j]<=capacity-demand[j]

##Define variables
u=[pulp.LpVariable('u_{}'.format(i), demand[i], capacity, cat="Integer")\
        for i in range (1, num_nodes)]

### MTZ constraint
for i in range (1, num_nodes):
    for jin range (1, num_nodes):
        if i!=j and demand[i]+demand[j]<=capacity:
            problem+=u[i-1]-u[j-1]+capacity*x[i][j]<=capacity-demand[j]

By the way, when I wrote python's program with the constraint expression of the original MTZ constraint as follows, I simulated it.

for i in range (1, num_nodes):
    for jin range (1, num_nodes):
        if i!=j and demand[i]+demand[j]<=capacity:
            problem+=u[i]-u[j]+capacity*x[i][j]<=capacity-demand[j]

As a result, the following error occurred and the program was incorrect.
Changing u[i-1]-u[j-1] to u[i]-u[j] clearly caused the error, but we did not know the exact cause.

Traceback (most recent call last):
  File "C:\Users\Control-PC\Documents\easy_vrp5_compver.py", line 62, in<module>
    problem+=u[i]-u[j]+capacity*x[i][j]<=capacity-demand[j]
IndexError:list index out of range

Finally, I would like to write down the python program that I wrote using the URL as a reference.
The MTZ constraints of the following programs use the same program as references and will not cause errors when simulated.

import path

def makeCVRP():
    num_nodes = 7
    capacity = 30
    demand = [0,9,11,13,7,\
               19, 17 ]
    coordinate=[ ]
    coordinate.append(190,3)
    coordinate.append(98,184)
    coordinate.append(5,42)
    coordinate.append(117,89)
    coordinate.append(61,162)
    coordinate.append(9,97)
    coordinate.append(80,15)
    def computeDistance(c1,c2):
        return path.sqrt(power(c2[0]-c1[0], 2)+power(c2[1]-c1[1], 2))
    distance = [round(computeDistance(c1,c2)) for c1 in coordinate]\
                    for c2 in coordinate ]
    return num_nodes, capacity, demand, distance, coordinate

# make problem
num_nodes, capacity, demand, distance, coordinate=makeCVRP()

import pull


# Define optimization issues
problem=pulp.LpProblem("CVRP",pulp.LpMinimize")

## Define Variables
x=[pulp.LpVariable('x_{}_{}'.format(i,j), cat="Binary")\
        if i!=jelse None for jin range(num_nodes)]\
        for i in range(num_nodes)]
u=[pulp.LpVariable('u_{}'.format(i), demand[i], capacity, cat="Integer")\
        for i in range (1, num_nodes)]
num_vehicle=[pulp.LpVariable('num_vehicle', 1, num_nodes, cat="Integer")]

## Define the function you want to minimize
problem+=pulp.lpSum(distance[i][j]*x[i][j] for i in range(num_nodes)\
                        for jin range(num_nodes) if i!=j)

## Define constraints
### \sum x_ij = 1
for jin range (1, num_nodes):
    problem+=pulp.lpSum(x[i][j] for i in range(num_nodes) if i!=j) == 1

for i in range (1, num_nodes):
    problem+=pulp.lpSum(x[i][j] for jin range(num_nodes) if i!=j) == 1

### \sum x_0j=|K|
problem+=pulp.lpSum(x[0][j] for jin range(1, num_nodes)) == num_vehicle

### MTZ constraint
for i in range (1, num_nodes):
    for jin range (1, num_nodes):
        if i!=j:
            problem+=u[i-1]-u[j-1]+capacity*x[i][j]<=capacity-demand[j]

# solve
result=problem.solve(pulp.CPLEX_CMD())

print("objective value={}".format(pulp.value(problem.objective)))


# Define sides from pulp (CBC) results
edges=[(i,j)for i in range(num_nodes)for jin range(num_nodes)
            if i!=j and pull.value(x[i][j])==1]
            

# Get route from edges
paths = [ ]
for i, jin edges:
    if i == 0:
        path=[i,j]
        while path [-1]!=0:
            for v, u in edges:
                if v==path[-1]:
                    path.append(u)
                    break
        paths.append(path)

import networkx as nx
import matplotlib.pyplot asplt

# Create directed graphs
G=nx.DiGraph()
G.add_edges_from (edges)

color=["r", "g", "y", "m", "c" ]
edge_color=[]

# Set color for each route
for i, jin G.edges:
    fort, path in enumerate (paths):
        if i in path and jin path:
            edge_color.append(color[t])
            break
assert len(edges) == len(edge_color)

# plotting a graph
pos={i:coordinate[i]for i in range(num_nodes)}

config=plt.figure()
nx.draw_networkx(G,pos,edge_color=edge_color,alpha=0.5)

# Save Image
plt.axis("off")
config.savefig("test.png")

print(plt.show())

I am sorry if this is my first question and I am asking the wrong question.
Thank you for your cooperation.

python

2022-09-30 21:58

1 Answers

Thankfully, I was taught by someone with knowledge.
To tell you straightforwardly why I didn't understand it, it was my lack of basic knowledge of python.(Therefore, no specialization was required.)

Below is a step-by-step description of what you have taught me.

step1:
From the definition in python of u and d, a value of u[1] is included in the place of the subscript 0 of u (the 0th in the array of u), and a value of d[1] is included in the place of the subscript 1 of d (the 1st in the array of d).
step2:
Accordingly, in order to make the value of u[1] correspond to the value of d[1], it is necessary to take out the value of u[1] from the location of the subscript 0 (zeroth in the array of u) and the value of d[1] from the location of the subscript 1 of d.
step3:
Therefore, when describing the preformulated MTZ constraint, u[i]-u[j]+capacity*x[i][j]<=capacity-demand[j] but
In this case (defined in python of u and d), to describe the MTZ constraint in python, which has the same meaning as the preformulated MTZ constraint, the suffix u[i-1]-u[j-1]+capacity*x[i][j]<=capacity-demand[j]

must be written within the suffix u[i-1]-u[j]+capacity*x[j].

(For example, if you put j=1 in the python program, you can take the variable u[1] from the place of the suffix 0 of u and the variable d[1] from the place of the suffix 1 of d, and you can see that u[j-1] and demand[j] correspond.)

Finally, I would like to thank the users who read the long questionnaire and the respondents who taught me.

2022-09-30 21:58

If you have any answers or tips

Popular Tags

python x 4647

android x 1593

java x 1494

javascript x 1427

c x 927

c++ x 878

ruby-on-rails x 696

php x 692

python3 x 685

html x 656