转运问题¶
现实生活中，物流公司常常将仓库作为中间节点，然后再转运给受众，这种问题被称为转运问题。
转运问题是运输问题的一种特殊情况，即在运输路径中有中间节点。例如，在A到B之间运输，通过C可能A直达B的运输更便宜。
案例分析-沙土运输¶
某沙土公司经理决定利用两个中间节点作为沙土临时储存的转运点。网络流程图如下图所示:
其中连线上的数字代表单位成本，图片左侧和右侧则显示了工厂的供给量以及项目对沙土的需求量
索引¶
- $F=\{A,B,C\}$,工厂的集合
- $W=\{P,Q\}$,仓库的集合
- $P=\{1,2,3\}$，项目的集合
决策变量¶
- $x_{fw}$:从工厂$f$至仓库$w$的的运输量
- $y_{wp}$:从仓库$w$至项目$p$的运输量
参数¶
- $c_{fw}$:从工厂$f$至仓库$w$的的单位运输费用
- $e_{wp}$:从仓库$w$至项目$p$的单位运输费用
- $s_{f}$:从工厂的最大供给量
- $d_{p}$:项目$p$的需求量
目标函数¶
$$\min \sum_{f\in F}\sum{w\in W}c_{fw}x_{fw}+\sum_{w\in w}\sum{p\in P}e_{wp}x_{wp}$$约束条件¶
工厂的供给量不能超过最大供给量 $$\sum_{w\in W}x_{fw}\le s_f, f\in F$$
项目的需求量等于从仓库的接受量 $$\sum_{w\in W}y_{wp}\le d_p, p\in P$$
仓库的接受量等于输出量 $$\sum_{f\in F}x_{fw}=\sum_{p\in P}y_{wp}, w\in W$$
同时 $$x_{fw},y_{wp}\ge 0$$
代码实现¶
# Import PuLP modeler functions
from pulp import *
# Creates a list of all the supply nodes
factories = ["A", "B", "C"]
# Creates a dictionary for the number of units of supply for each supply node
supply = {"A": 100, "B": 200, "C":200}
# Creates a list of all demand nodes
projects = ["1", "2", "3"]
# Creates a dictionary for the number of units of demand for each demand node
demand = {
"1": 50,
"2": 150,
"3": 300,
}
# Intermediate nodes
warehouses=["P","Q"]
# Creates a list of costs of each transportation path
costs_1 = [ # warehouses
[3,2], # A factories
[4,3], # B
[2.5,3.5] # C
]
costs_2 = [ # projects
[2,1,4], # P warehouses
[3,2,5], # Q
]
# The cost data is made into a dictionary
costs_1 = makeDict([factories, warehouses], costs_1, 0)
# The cost data is made into a dictionary
costs_2 = makeDict([warehouses, projects], costs_2, 0)
# Creates the 'prob' variable to contain the problem data
prob = LpProblem("Material_Supply_Problem", LpMinimize)
# Creates a list of tuples containing all the possible routes for transport
Routes_1 = [(f, w) for f in factories for w in warehouses]
# A dictionary called 'Vars' is created to contain the referenced variables(the routes)
vars_1 = LpVariable.dicts("Route1", (factories, warehouses), 0, None, LpInteger)
# Creates a list of tuples containing all the possible routes for transport
Routes_2 = [(w, b) for w in warehouses for b in projects]
# A dictionary called 'Vars_2' is created to contain the referenced variables(the routes)
vars_2 = LpVariable.dicts("Route2", (warehouses, projects), 0, None, LpInteger)
# The objective function is added to 'prob' first
prob += (
lpSum([vars_1[f][w] * costs_1[f][w] for (f, w) in Routes_1]) + lpSum([vars_2[w][b] * costs_2[w][b] for (w, b) in Routes_2]),
"Sum_of_Transporting_Costs",
)
# The supply maximum constraints are added to prob for each supply node (factories)
for f in factories:
prob += lpSum([vars_1[f][w] for w in warehouses]) <= supply[f],f"Sum_of_Products_out_of_factories_{f}"
# The demand minimum constraints are added to prob for each demand node (project)
for b in projects:
prob += (
lpSum([vars_2[w][b] for w in warehouses]) >= demand[b],
f"Sum_of_Products_into_projects_{b}" ,
)
# Transshipment constraints: What is shipped into a transshipment node must ne shipped out.
for w in warehouses:
prob += (
lpSum([vars_1[f][w] for f in factories]) - lpSum([vars_2[w][p] for p in projects])== 0,
f"Sum_of_Products_out_of_warehouse_{w}",
)
# The problem is solved using PuLP's choice of Solver
prob.solve()
# Print the variables optimized value
for v in prob.variables():
print(v.name, "=", v.varValue)
# The optimised objective function value is printed to the screen
print("Value of Objective Function = ", value(prob.objective))
输出结果¶
Route1_A_P = 100.0
Route1_A_Q = 0.0
Route1_B_P = 200.0
Route1_B_Q = 0.0
Route1_C_P = 200.0
Route1_C_Q = 0.0
Route2_P_1 = 50.0
Route2_P_2 = 150.0
Route2_P_3 = 300.0
Route2_Q_1 = 0.0
Route2_Q_2 = 0.0
Route2_Q_3 = 0.0
Value of Objective Function = 3050.0小结¶
在本文中，我们学习了使用python PuLp库的转运问题、问题公式和实现。我们使用Python中的一个线性编程问题解决了转运问题
参考资料