[PYTHON] Solving the shortest path problem (VRP) Mixed integer programming
After studying famous logistics-related problems, I decided to solve them with python. So, for the first time, I will try to solve the transportation route problem by the integer programming method.
What is the transportation route problem?
English name Vehicle Routing Problem (VRP). [ORWiki transportation route problem](http://www.orsj.or.jp/~wiki/wiki/index.php/%E9%81%8B%E6%90%AC%E7%B5%8C%E8%B7 % AF% E5% 95% 8F% E9% A1% 8C) for a detailed explanation. Simply put, it is a problem of finding the minimum cost to meet the demands of multiple customers by using a carrier belonging to a base called a depot. If it is difficult to understand, you can think of making a plan to minimize the total mileage of Yamato Takkyubin trucks. (Sorry, in their case, there is a redelivery due to their absence, so it is extremely difficult to put it into a mathematical problem, or it is impossible.) Every company that does delivery aims to introduce a system aiming at automation, but full automation is quite difficult. This is because there are sudden order changes and products whose size is unknown. The impression that most companies are created by craftsmen in Excel.
Problem type
- In VRP, problems are classified according to the presence or absence of the following conditions. The software on the market meets most of the constraints. This time, only the track capacity is considered as a constraint.
- PickUP and Delivery（VRPPD) --Multiple loading areas. Not one depot.
- LIFO
- Post-in / first-out restrictions. It is troublesome to remove the luggage loaded in the back of the truck and remove the luggage in front. Important in the actual transportation plan.
- Time frame (VRPTW)
- Desired delivery time constraint for each customer.
- Track capacity (CVRP)
- Truck has capacity constraints
Formulation
Since VRP is NP-hard, commercial software uses a heuristic solution. After studying this time, I will solve it with MIP (Mixed Integer Programming). The explanation is in the source. I'm sorry for being unfriendly. I use a library called pulp, but if you are not familiar with it, I will link the following article for those who are not familiar with how to use pulp. Introduction to solving linear programming problems with PuLP By the way, this time I implemented the extended version of DFJ introduced in English Wiki of VRP.
Source
CVRPwithMIP.py
import pulp
import pandas as pd
import numpy as np
import networkx as nx
import itertools
import matplotlib.pyplot as plt
num_client = 15 #Number of customers (id=0,1,2,...I think it is numbered 14. id=0 is the depot. )
capacity = 50 #Truck capacity
randint = np.random.randint
seed = 10
#X for each customer,Create y coordinates and demand (how many products you want) as a DataFrame
df = pd.DataFrame({"x":randint(0,100,num_client),
"y":randint(0,100,num_client),
"d":randint(5,40,num_client)})
#The 0th customer is considered as a depot (base). So demand=0,To come to the center at the time of visualization
#x,y to 50.
df.ix[0].x = 50
df.ix[0].y = 50
df.ix[0].d = 0
#cost is the number of customers ✖️ Distance table of the number of customers. np.Hold in array.
cost = create_cost()
#subtours is a depot (id=0)A complete set of customers except. I'll see what this helps later.
subtours = []
for length in range(2,num_client):
subtours += itertools.combinations(range(1,num_client),length)
#x is the number of customers ✖️ binary variable Array of the number of customers. Corresponds to the Cost table. If it is 1, the truck will run between them.
# num_v is the required number of trucks variable.
x = np.array([[pulp.LpVariable("{0}_{1}".format(i,j),0,1,"Binary")
for j in range(num_client)]
for i in range(num_client)])
num_v = pulp.LpVariable("num_v",0,100,"Integer")
#Problem declaration and objective function setting. The objective function is to minimize the total distance.
problem = pulp.LpProblem('vrp_simple_problem', pulp.LpMinimize)
problem += pulp.lpSum([x[i][j]*cost[i][j]
for i in range(num_client)
for j in range(num_client)])
#Excluded because there is no possibility of moving from customer 1 to customer 1
for t in range(num_client):
problem += x[t][t] == 0
#There is always one arc (truck) going out and one arc (truck) coming in from the customer.
for t in range(1,num_client):
problem += pulp.lpSum(x[:,t]) == 1
problem += pulp.lpSum(x[t,:]) == 1
#Depot (here id=0)The number of incoming arcs (tracks) and outgoing arcs (trucks) is always the same.
problem += pulp.lpSum(x[:,0]) == num_v
problem += pulp.lpSum(x[0,:]) == num_v
#This is the liver. With the above restrictions, an isolated cycle that does not return to the depot is created. What we are doing here
#subtour eliminate constraint. We also look at demand and add a Capacity constraint here. be interested
#If you are interested, please search for subtour eliminate.
for st in subtours:
arcs = []
demand = 0
for s in st:
demand += df_dpsts["d"][s]
for i,j in itertools.permutations(st,2):
arcs.append(x[i][j])
print(len(st) - np.max([0,np.ceil(demand/capacity)]))
problem += pulp.lpSum(arcs) <= np.max([0,len(st) - np.ceil(demand/capacity)])
#Calculation and confirmation of results
status = problem.solve()
print("Status", pulp.LpStatus[status])
for i in range(num_client):
for j in range(num_client):
print(i,j,x[i][j].value())
output_image(G,x)
Visualization
Visualization of the solution. The blue dot is the depot and the red dot is the customer (numbers are demand)
It turns out that five trucks are needed. Note that the total demand for each cycle does not exceed the truck capacity (= 50).
Conclusion
Solved! The above formulation cannot be solved if the number of customers increases a little, especially because the number of restrictions on Subtour elimination increases explosively with the number of customers. There are some ideas here, but I will not introduce them this time. Next time, I'll write a heuristic (not an exact solution, but a good solution) method.
Recommended Posts