线性规划——物流配送问题的R实现

标签：Tesla 线性规划物流配送实现 SGM SVW data row

物流配送是电商物流的主要方式，基于电子商务的特点，对整个物流配送体系实行统一的信息管理和调度；按照用户订货要求，在物流中心进行理货工作，并将配好的货物送交收货人。物流仓储配送服务已然成为中国电子商务最为核心的作业环节，能够提供一个全面完善的物流仓储配送解决方案也成为了很多中小卖家、电子商务供应商品牌商必须关注的问题。物流配送的许多环节都需要巨大的成本、人力、时间，物流配送必须重视物流配送系统的信息化管理，来降低物流成本。

一、物流配送服务

物流配送问题描述的是在一个物流网络之中，如何从工厂出发经由不同路径，将满足经销商需求的货物以最小代价配送到各经销商处。数据见下面表格所示：

工厂	SVW	SGM	NIO	Tesla	GTMC
产量	300	250	175	190	223

经销商	Walmart	CP Lotus	Century Lianhua	Carrefour	Rt-mart	Auchan	Tesco
需求量	87	66	85	120	81	143	146

起点	SVW	SVW	SVW	SVW	SVW	SVW	SVW	SGM	SGM	SGM	SGM	SGM
终点	Walmart	CP Lotus	Century Lianhua	Carrefour	Rt-mart	Auchan	Tesco	Walmart	CP Lotus	Century Lianhua	Carrefour	Rt-mart
运输费用	1.77	2.06	1.52	1.64	1.26	1.25	1.88	2.05	1.32	1.5	1.95	2.04
运力	76	35	60	105	122	76	27	106	36	90	74	61
起点	SGM	SGM	NIO	NIO	NIO	NIO	NIO	NIO	NIO	Tesla	Tesla	Tesla
终点	Auchan	Tesco	Walmart	CP Lotus	Century Lianhua	Carrefour	Rt-mart	Auchan	Tesco	Walmart	CP Lotus	Century Lianhua
运输费用	1.79	1.88	1.96	1.46	2.21	2.09	1.8	1.31	1.66	1.75	2.1	1.82
运力	72	78	102	86	116	29	78	66	77	91	58	35
起点	Tesla	Tesla	Tesla	Tesla	GTMC	GTMC	GTMC	GTMC	GTMC	GTMC	GTMC
终点	Carrefour	Rt-mart	Auchan	Tesco	Walmart	CP Lotus	Century Lianhua	Carrefour	Rt-mart	Auchan	Tesco
运输费用	1.81	1.58	1.93	1.61	2.1	1.41	2.04	2.25	1.88	1.71	2.09
运力	136	72	73	56	119	35	88	51	66	57	88

【解析】该问题是运力有限的运输问题。
决策变量：在这个问题中，可以取从节点到节点之间的流量作为决策变量
目标函数：目标函数就是所有路径上的物流成本之和。
约束条件：此问题中的约束主要有三方面：路径流量不能超过运力限制；必须满足每个经销商的需求；每个工厂发出的货物必须小于其产量限制。
对于图问题的建模可以用networkx包来操作，这里只是做了简单的图建模和可视化，还有很多功能都没有用到。在复杂网络中，它附带的图分析网络和一些算法都非常有用。此问题的网络可视化如下：

from pulp import *
import pandas as pd
import networkx as nx
import os
import time
import matplotlib.pyplot as plt
 
# 导入数据
fpath = os.path.join("data", "物流配送模型数据.xlsx")
factories = pd.read_excel(fpath, sheet_name="工厂")
vendors = pd.read_excel(fpath, sheet_name="经销商")
routes = pd.read_excel(fpath, sheet_name="路线")
 
import networkx as nx
# 创建有向图
G = nx.DiGraph()
# 添加节点
for i, row in factories.iterrows():
    G.add_node(row.工厂, supply=row.产量, node_type = '工厂')
    
for i, row in vendors.iterrows():
    G.add_node(row.经销商, demand=row.需求量, node_type = '经销商')
# 添加边
for i, row in routes.iterrows():
    G.add_edge(row.起点, row.终点, cost=row.运输费用, capacity=row.运力)
 
# 网络可视化
top = nx.bipartite.sets(G)[0]
layout = nx.layout.bipartite_layout(G, top)
nx.draw(G,layout,node_shape='s',node_size=1200, node_color='#5C7EFF', arrow_size=50)
nx.draw_networkx_labels(G,layout)
plt.show()
# 建立模型
model = LpProblem("物流配送模型", LpMinimize)
 
# 建立变量
shipping_amount = LpVariable.dicts("配送量", G.edges(), lowBound=0)
 
# 目标函数
model += lpSum([data['cost']*shipping_amount[(origin, destination)] for(origin, destination, data) in G.edges(data=True)])
 
# 约束条件
# 满足经销商的需求
for name, data in G.nodes(data=True):
    if data["node_type"] == "经销商":
        model += lpSum([shipping_amount[(origin, name)] for origin,_ in G.in_edges(name)]) == data['demand']
            
# 满足工厂产量约束
for name, data in G.nodes(data=True):
    if data["node_type"] == "工厂":
        model += lpSum([shipping_amount[(name, destination)] for _,destination in G.out_edges(name)]) <= data['supply']
        
# 满足路线运力约束
for (origin, destination, data) in  G.edges(data=True):
    model += shipping_amount[(origin, destination)] <= data['capacity']
 
# 求解
start_time = time.clock()
model.solve()
print("用时：", time.clock()-start_time," s")
print("求解状态：", LpStatus[model.status])
 
# 组织计算结果
rsl = []
for origin, destination in G.edges():
    val = value(shipping_amount[(origin, destination)])
    rsl.append({"起点": origin, "终点":destination, "运输量": val})
rsl_df = pd.DataFrame(rsl)
print(rsl_df[rsl_df.运输量>0])
print("最小运输代价为： ",value(model.objective))

用时： 0.009226999999999874  s
求解状态： Optimal
                 终点     起点    运输量
3         Carrefour    SVW  105.0
4           Rt-mart    SVW   81.0
5            Auchan    SVW   76.0
8          CP Lotus    SGM   36.0
9   Century Lianhua    SGM   85.0
13            Tesco    SGM   13.0
19           Auchan    NIO   66.0
20            Tesco    NIO   77.0
21          Walmart  Tesla   87.0
24        Carrefour  Tesla   15.0
27            Tesco  Tesla   56.0
29         CP Lotus   GTMC   30.0
33           Auchan   GTMC    1.0
最小运输代价为：  1096.57

二、配送网点设置

例2：一家快递公司准备在某个地区建立两个点部，向7个区的居民经营，每个区的居民数如下图，每个分公司只能向本区和相邻区的居民经营，这两个点部应建在何处，才能使得所能供应的居民的数量最大？请给出数学模型及求解程序。

【解析】

将居民区进行标号, 如图，记 \(r_i, i=1,2, \cdots, 7\) 为第 \(i\) 个居民区人数, 设 \(r_{i j}=r_i+r_j\) 为设在 \(i\) 区时服务的人数, 如 \(r_{12}=r_1+r_2=109\) 。
用 0-1 变量 \(x_{i j}=\left\{\begin{array}{lc}1 & \text {,公司设在居民区 } i 向j区服务 \\ 0 & \text {,其它 }\end{array} i<j\right.\), 且 \(i,j\) 相邻。则由题意建立整数线性规划模型：

\[\begin{aligned} & \max =\sum_{i, j \text { 相邻 }}\left(r_i+r_j\right) x_{i j} \\ & \text { s.t. } \\ &\quad \quad \sum_{i, j} x_{i j}=2 \\ &\quad \quad \sum_k x_{i k}+\sum_k x_{k i} \leq 1 \text { (服务居民区 } i \text { 最多有一个) } \\ & \end{aligned} \]

即:

\[\begin{gathered} \max =109 x_{12}+89 x_{13}+104 x_{14}+122 x_{23}+117 x_{34}+83 x_{35}+100 x_{36}+115 x_{46}+81 x_{56}+56 x_{57}+73 x_{67} \\ \text { s.t. } \\ x_{12}+x_{13}+x_{14}+x_{23}+x_{34}+x_{35}+x_{36}+x_{46}+x_{56}+x_{57}+x_{67}=2 \\ x_{12}+x_{13}+x_{14} \leq 1 \\ x_{23}+x_{12} \leq 1 \\ x_{34}+x_{35}+x_{36}+x_{13}+x_{23} \leq 1 \\ x_{46}+x_{14}+x_{34} \leq 1 \\ x_{56}+x_{57}+x_{35} \leq 1 \\ x_{67}+x_{36}+x_{46}+x_{56} \leq 1 \end{gathered} \]

library(lpSolve)
a1=c(1,1, 1,  1,  1 , 1,  1 , 1,  1,   1, 1)
a2=c(1 , 1 , 1,  0,  0,  0,  0 , 0 , 0, 0, 0)
a3=c(1,  0,  0,  1 , 0 , 0,  0,  0 , 0,   0 ,  0)
a4=c(0 , 1,  0 , 1 , 1 , 1,  1,  0,  0,   0,   0)
a5=c(0 , 0 , 1 , 0 , 1 , 0, 0 , 1 , 0,   0 ,  0)
a6=c(0 , 0 , 0,  0,  0 , 1 , 0 , 0 , 1,   1,   0)
a7=c(0,  0,  0 , 0 , 0 , 0 , 1,  1 , 1  , 0,   1)

f.obj <- c(109,89,104,122, 117, 83, 100, 115, 81, 56, 73)
f.con=rbind(a1,a2,a3,a4,a5,a6,a7)
f.dir <- c('=','<=','<=','<=','<=','<=', '<=')
f.rhs <- c(2,1,1,1,1,1,1)
jie=lp('max', f.obj, f.con,f.dir,f.rhs,all.bin=TRUE)
jie$solution
jie$objval
#最优值为237，两个分公司设在居民区2和4，提供配送服务

参考文献

标签：Tesla,线性规划,物流配送,实现,SGM,SVW,data,row
From： https://www.cnblogs.com/haohai9309/p/17334160.html

线性规划——物流配送问题的R实现

一、物流配送服务

二、配送网点设置

参考文献

相关文章

赞助商

阅读排行