Optimal Transport Problem
Let’s say you are living in city A and has a small ride hailing company called AwesomeRides. Now after a lot of efforts you have created a small marketplace in this city where Riders use your app to book drivers. But now the question comes is given open requests and drivers at any time how well we are able to match riders with drivers to reduce transport cost of bringing driver to rider location as well as fulfilling as much rides as possible.
This is an interesting task and has many ways to deal with it. Here we will go with one of the methods described in Graph-Based Equilibrium Metrics for Dynamic Supply-Demand Systems with Applications to Ride-sourcing Platforms.
Though the paper talks a lot about many things but here we will focus on a simple problem. Given supply and demand at a given time for a given city, how efficiently we are able to match supply with demand.
Let’s say we have a city A which is further divided into smaller hexagonal regions. Each region r has it’s own demand d_r and supply s_r. For matching supply s to demand d has some cost(travel, time, toll etc.). Our task is to efficiently match demand to supply s.t.
Although the equation looks big but in essence it is trying to solve for an optimal plan gamma that tells us how much drivers we should send to each location to minimize the overall cost.
This is a standard Linear Problem and can be solved by solved by any linear programming solver packages(For example : XP Solver). In the above equation there is a L1-norm which many standard solvers doesn’t support. So it’d be better to simplify the above equation before feeding into the solver.
The above equation can be solved by any standard LP solver and we can get our optimal plan using that.
Example
We will use the equation defined in figure 2 to find the values marked as *.
Because of mode this is difficult to be directly solved and hence we will use the transformation described in figure 3.
from scipy.optimize import linprog
def generate_array(var_list):
base = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
index = {
"s1" : 0,
"s2" : 1,
"s3" : 2,
"s4" : 3,
"s5" : 4,
"y11" : 5,
"y12" : 6,
"y14" : 7,
"y22" : 8,
"y23" : 9,
"y25" : 10,
"y31" : 11,
"y32" : 12,
"y33" : 13,
"y34" : 14,
"y42" : 15,
"y44" : 16,
"y53" : 17,
"y54" : 18,
"y55" : 19,
}
for var, multiplier in var_list:
base[index[var]] = multiplier
return base
# Assume : lambda = 2
obj = [1,1,1,1,1,0,2,2,0,2,2,2,2,0,2,2,0,2,2,0]
lhs_ineq = [
generate_array([("y11",1), ("y31",1), ("s1", -1)]),
generate_array([("y22",1), ("y42",1), ("y12",1), ("y32",1), ("s2", -1)]),
generate_array([("y23",1), ("y33",1), ("y53",1), ("s3", -1)]),
generate_array([("y14",1), ("y34",1), ("y44",1), ("y54",1), ("s4", -1)]),
generate_array([("y25",1), ("y55",1), ("s5", -1)]),
generate_array([("y11",1), ("y31",-1), ("s1", -1)]),
generate_array([("y22",-1), ("y42",-1), ("y12",-1), ("y32",-1), ("s2", -1)]),
generate_array([("y23",-1), ("y33",-1), ("y53",-1), ("s3", -1)]),
generate_array([("y14",-1), ("y34",-1), ("y44",-1), ("y54",-1), ("s4", -1)]),
generate_array([("y25",-1), ("y55",-1), ("s5", -1)])
]
rhs_ineq = [
5,
2,
3,
10,
2,
-5,
-2,
-3,
-10,
-2
]
lhs_eq = [
generate_array([("y11",1), ("y12",1), ("y14", 1)]),
generate_array([("y22",1), ("y23",1), ("y25", 1)]),
generate_array([("y33",1), ("y32",1), ("y31", 1), ("y34", 1)]),
generate_array([("y44",1), ("y42",1)]),
generate_array([("y55",1), ("y53",1), ("y54", 1)])
]
rhs_eq = [
3,
8,
1,
20,
1
]
bnd = [(0, float("inf")) for i in range(len(obj))]
opt = linprog(c=obj, A_ub=lhs_ineq, b_ub=rhs_ineq,
A_eq=lhs_eq, b_eq=rhs_eq, bounds=bnd,
method="revised simplex")
print(opt.x)Upon solving the equation with above script it will return following solution.
Summary
Here we have seen how given the transport requirement, we can use Linear Program to create an optimal plan. In the Next part we will talk about given an optimal plan how we can say if the market is balanced.
