多级网络优化的规划问题简化-Python预演

背景和目标

在物流网络中,经常存在需要优化的网络结构,比如从生产中心到一级仓库 ,到二级仓库再到配送中心,这样形成一个多级的分仓体系。在实际执行过程中会遇到DC层或TC层的选址问题,一般会遇到优化问题,优化的目标主要考虑多个方面的成本,如运输成本,仓库成本,转运成本等等。如果按照多级网络的模式进行考虑,一般规划问题会成为非线性的整数规划问题,在求解上是非常难且建模也比较难。

现在对于这样的其中选址的问题进行思考:假设我们只是考虑运输成本或距离上的成本,DC层的仓库可以向周边的仓库进行供货,而且保证TC层的一个仓库只能唯一的DC层仓库供货。从常规的建模一般都是在DC层设置一个变量X, TC层设置一个变量Y,来计算目标,并设置约束,最终来进行求解,那么这个问题能简化么?

如果能简化那么这个问题就能推广到多层的选址问题,不需要非线性整数规划的方式进行求解。能大大的简化整个求解,可能不是最优的解,但是能得到较优的解。经过仔细的实验和思考,是能进行简化的。将DC层和TC层的地址看为一个变量,这样就减少一个变量,转化为了线性规划的问题(LP)。DC层对TC层为1对N的方式,但是TC只能属于一个DC。而且可以控制DC层的地点或TC层的地点的个数。解决了选址中遇到的所有问题。
物流的多级分仓体系

数据的准备

这里我们准备了一些城市的数据,其中有DC,TC层和最终的地点。数据存储于mysql数据库中,下面定义一个数据抽取的class,来进行数据查询,并生成需要的距离矩阵。便于后续使用该矩阵来进行优化目标值的计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# import packages
import pymprog
import pymysql
import pandas as pd
import numpy as np
from collections import defaultdict

class MysqlClient(object):
"""
create mysql connect client
"""
def __init__(self, host, user, password, database="glc_lpp_dev", port=3306):
self.host = host or "127.0.0.1"
self.user = user
self.passwd = password
self.database = database
self.port = port
self.connection = self._get_connection()

def _get_connection(self):
"""get mysql connection client"""
try:
_connection = pymysql.connect(host=self.host, user=self.user, password=self.passwd, port=self.port,
database=self.database, charset="utf8")
except Exception as error:
print("Connect mysql server:%s has error, the error is: %s" % (self.host, error))
_connection = None
return _connection

def query(self, sql_scripts):
"""
:param sql_scripts: string, use this sql scripts get data.
:return: tuple
"""
if self.connection is None:
raise Exception("Get mysql connection failed. The connection is NoneType object.")
cursor = self.connection.cursor()
cursor.execute(sql_scripts)
fetch_data = cursor.fetchall()
cursor.close()
return fetch_data

def close(self):
if self.connection is not None:
self.connection.commit()
self.connection.close()

规划问题的简化方案

在本次的实验过程中使用pymprog来进行LP求解,并定义整个网络模型,通过距离矩阵来定义目标和约束,具体如下面代码中的说明,先定义决策变量(这里定义为了0-1整数变量),再定义目标函数(本示例中主要定义了一个距离相关的优化目标),再定义约束条件,最终求解,并格式化输出。其中约束条件定义非常灵活:

  1. 一个TC只能属于一个DC
  2. 一个DC可以有多个TC,这儿并定义了输入的DC都必须被选到

示例代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
def solve_link(distance_matrix_frame, flag=1):
"""Find the link matrix by linear programming slove
parameters
----------
distance_matrix_frame:
pandas.DataFrame, src positions to dst positions, index is src position.

return
------
DataFrame, the link dataframe, the index is src positions and the columns is dst positions.
"""
t_frame = distance_matrix_frame.T.to_dict()
src_pos_, dst_pos_ = distance_matrix_frame.index, distance_matrix_frame.columns
constant = []
for s in src_pos_:
s_list = []
for d_ in dst_pos_:
s_list.append(t_frame[s][d_])
constant.append(s_list)

pymprog.begin('link')

index, columns = range(len(src_pos_)), range(len(dst_pos_)) # the number of variable
x = pymprog.var('x', pymprog.iprod(index, columns), bool) # defined variable

min_value = sum([x[(i, j)] * constant[i][j] for i in index for j in columns])
pymprog.minimize(min_value, "min_distance") # optimizer target: minimize

# ------------ defined constraints -------------- #
# defined next layer map one city
for j in columns:
st_init = 0
for i in index:
st_init += x[(i, j)]
pymprog.st(1 <= st_init <= 2)
# defined current layer at least one
if flag:
for i in index:
ct_init = 0
for j in columns:
ct_init += x[(i, j)]
pymprog.st(1 <= ct_init)
# ------------ defined constraints -------------- #

# soleve linear programing
pymprog.solve()
# build up result by dataframe
output_dict = defaultdict(dict)
for i in index:
for j in columns:
output_dict[dst_pos_[j]][src_pos_[i]] = x[(i, j)].primal
# pymprog.sensitivity()
pymprog.end()
return pd.DataFrame(data=output_dict)

应用

通过一些数据进行试验上面的思路,下面生产中心选取了两个:天津和重庆,DC层有4个点,TC层 有7个点,配送中心有很多个城市,如下设置所示。通过sql查询得到数据库中的距离矩阵。后面将所有的中文地址转换为英文,主要便于后面的可视化。

1
2
3
4
5
6
7
8
9
10
# built the network struct, src position, depot and dst position
dst_position = ["宜昌", "长沙", "岳阳", "无锡", "合肥", "徐州", "常州","哈尔滨", "长春", "秦皇岛", "呼和浩特", "银川", "西宁",
"酒泉", "庆阳", "许昌", "吴忠", "鄂尔多斯", "广元", "巴中", "都江堰", "南充", "广安", "乐山", "宜宾", "南阳",
"衡阳", "大同", "丽江", "攀枝花", "玉林", "柳州", "桂林", "中山", "南平", "泉州", "雅安", "怀化", "荆州", "黄山"
]
src_position = ["重庆", "天津"]
depot_position = {
"level_1": ["北京", "成都", "西安", "武汉"],
"level_2": ["绵阳", "沈阳", "兰州", "南昌", "杭州", "南宁", "昆明"]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
middle_layer = []
for k, v in depot_position.items():
middle_layer.extend(v)

node_list = dst_position + src_position

import pickle

with open("/opt/notebook/distance.pkl", "rb") as picker:
data = pickle.load(picker)

with open("/opt/notebook/layer_distance.pkl", "rb") as layer:
layer_dist = pickle.load(layer)

layer_dist
绵阳 沈阳 兰州 南昌 杭州 南宁 昆明
北京 1691 685 1617 1470 1329 2426 2834
成都 120 2474 1039 1496 1857 1325 1068
西安 606 1775 647 1197 1417 1932 1561
武汉 921 1845 1368 370 859 1294 1815

通过线性规划求解得到了连接矩阵如下面结果所示,可以看出DC层下有多个TC层,但是TC只属于一个DC。本文中没有控制DC和TC的数量。实际是可以加入进去的。后续对得到结果通过networkx进行可视化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
nodes_res = solve_link(data, flag=0)
layer_res = solve_link(layer_dist)


def cn2pingyin(s: str)->str:
from pypinyin import lazy_pinyin
return "".join(lazy_pinyin(s))


nodes_res.index = nodes_res.index.map(cn2pingyin)
nodes_res.columns = nodes_res.columns.map(cn2pingyin)
layer_res.index = layer_res.index.map(cn2pingyin)
layer_res.columns = layer_res.columns.map(cn2pingyin)
layer_res
lanzhou nanning nanchang kunming hangzhou shenyang mianyang
beijing 0.0 0.0 0.0 0.0 0.0 1.0 0.0
chengdu 0.0 0.0 0.0 1.0 0.0 0.0 1.0
wuhan 0.0 1.0 1.0 0.0 1.0 0.0 0.0
xian 1.0 0.0 0.0 0.0 0.0 0.0 0.0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# !pip install matplotlib netowrkx
%matplotlib inline

import networkx as nx
from matplotlib import pyplot as plt
import matplotlib.font_manager as fm

fp1 = fm.FontProperties(fname="/usr/share/fonts/adobe-source-han-sans-cn/SourceHanSansCN-Medium.otf")
# nx.setitem(fp1)

plt.figure(figsize=(16, 9))
G = nx.Graph()

colors = ["blue", "gray"]
i = 0
for res in [layer_res, nodes_res]:
c = np.where(res==1)
index = res.index
columns = res.columns

pos1_list, pos2_list = [], []
for x, y in zip(c[0], c[1]):
G.add_edge(index[x], columns[y], weight=0.1)
pos1_list.append(index[x])
pos2_list.append(columns[y])

esmall = [(u, v) for (u, v, d) in G.edges(data=True) if d['weight'] >= 0.0]

if i >= 1:
pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, node_size=100)
nx.draw_networkx_edges(G, pos, edgelist=esmall, width=6, alpha=0.5, edge_color='b', style='solid')
nx.draw_networkx_nodes(G, pos,
nodelist=set(pos1_list),
node_color=colors[i],
node_size=500,
alpha=0.8)
nx.draw_networkx_labels(G, pos, font_size=12, font_family='DejaVu Sans')
if i >= 1:
nx.draw_networkx_nodes(G, pos,
nodelist2=set(pos1_list),
node_color=colors[i],
node_size=100,
alpha=0.8)
i += 1
plt.axis('off')
plt.show()

结果可视化