仓储物流中心的波次优化BatchOpt
1.问题描述
电商等仓储物流中心每天需要配送几万甚至十几万包裹，每个包裹需要包含来自于不同仓库，不同库区，不同数量的物品。如果规划不合理，可能会导致跨库、跨区域数量过多，订单配货时间过长，物流核心设备无效冗余运作距离过长,库存周转效率降低等问题。例如某电商有P个包裹（每个包裹包含多件商品，可能分布在多个仓库（暂时不考虑库存）），需要将其分到B个波次中，要求：
每个波次的商品件数载[G1, G2]之间
每个波次的包裹数量在[P1, P2]之间
目标是波次包含的不同仓库数量最少
输入数据格式如下：pakage_no包裹号，area仓库+库存，qty在仓库中的商品数
1
2
3
4
pakage_no area qty
0 354378981 5号仓-4 1
1 354531421 2号仓-12 1
2 354324781 2号仓-22 1
2.数学模型
2.1 modelV1（基本模型）
这是比较常规的建模思路，决策变量代表了包裹$i$是否属于波次$j$，假设包裹数为P，波次数为B，仓库数为K，modelV1的变量数为$PB+BK+B$，约束数为$1+P+4B+BK$。
测试案例的数据包裹数为57780，波次数为107，仓库数为4，这样变量数为6182995，约束数为58637，随着包裹数和波次数的增加，规模会快速增加，导致求解时间增加，电商场景中波次优化需要快速响应，因此需要对该模型进行改进。
2.2 modelV2（仓库模式）
直接以包裹数作为建模变量，规模非常大，而目标是波次包含的不同仓库数量最少，主要涉及波次和仓库，那么是否可以使用其它变量表示？测试案例涉及4个仓库：2号仓，4号仓，5号仓和佳明仓，如果使用模式(patter)统计对某个包裹涉及的仓库记为1，否则记为0，包裹号就可以转化为模式。
- pattern：{2号仓，4号仓，5号仓，佳明仓}
比如包裹302826075涉及2号和5号仓，模式为(1,0,1,0)。存在多个包裹的模式相同，因此可以用仓库模式来取代具体包裹，只决策某个波次用了某个模式几次。
1
2
3
4
pakage_no area qty
116324 302826075 2号仓-13 1
140678 302826075 2号仓-23 1
155819 302826075 5号仓-3 1
虽然不同包裹的模式相同，但是数量不同，因此在模式上需要加上商品数，这样会让模式数量增加，但是不会比modelV1按照具体包裹多
- pattern：{包裹的商品件数，2号仓，4号仓，5号仓，佳明仓}
和modelV1相比，modelV2的改进在于，决策变量改为波次$j$使用模式$p$的次数。测试案例的数据包裹数为57780，波次数为107，仓库数为4，计算出来的模式数为106，变量数为11877，约束数为963，和modelV1相比极大降低了问题规模
2.3 modelV3（仓库库区模式）
在2.1和2.2中的模型只考虑了仓库，没有考虑库区，现在进一步考虑问题，要求波次包含的不同的库区数量最少，比较简单的方法是基于modelV2，将模式从仓库变成仓库+库区。
测试案例的数据包裹数为57780，波次数为107，仓库数为4，计算出来的仓库+库区模式有24927，变量数为2669650，约束数为27710，和modelV1的问题一样，模型规模会随着包裹数和波次数的增加而快速增加，不太可取
2.4 modelV4（多阶段）
库区模式可以区分包裹，对两个包裹，首先要看是否在一个仓库，其次再看是否在一个库存，都相同才表示是属于相同的库区。因此问题可以分成两阶段来处理：
一阶段：基于modelV2按照仓库模式，求出每个波次使用的每个仓库模式的数量
二阶段：基于一阶段的结果，固定每个波次使用某个仓库模式的数量，但是优化该仓库模式下具体使用的包裹，从而进一步降低不同库区的数量
二阶段的决策变量表示包裹$i$是否属于波次$j$，包裹$i$来源一阶段固定的波次$j$使用的仓库模式包括的包裹，并且对数量进行约束。
2.5 modelV5（多阶段+仓库模式+库区模式）
modelV4可以解决要求波次所含不同的库区数量最小的问题，但是modelV4中，二阶段使用的是包裹$i$是否属于波次$j$这种建模思路，和modelV1相同，同样参考modelV2对modelV1的改进，modelV5也可以在二阶段使用引入库区模式
3.求解结果
3.1 modelV2
代码中涉及模型构建的部分如下，完整代码在github
- 变量
1
2
3
4
5
6
7
8
9
10
11
def add_variables(self):
x_list, y_list, z_list = [], [], []
for j in range(1, self.batch_nb[1] + 1):
for p in self.pattern_dict.keys():
x_list.append((j, p))
for k in self.ware_dict.values():
y_list.append((j, k))
z_list.append(j)
self.x = self.model.addVars(x_list, vtype=GRB.INTEGER, name='x')
self.y = self.model.addVars(y_list, vtype=GRB.BINARY, name='y')
self.z = self.model.addVars(z_list, vtype=GRB.BINARY, name='z')
- 约束条件
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
def add_constraints(self):
# 约束(1) 保证分配的波次数量
lhs_c1 = 0
for z_val in self.z.values():
lhs_c1 += z_val
if self.batch_nb[0] == self.batch_nb[1]:
self.model.addConstr(lhs_c1 == self.batch_nb[0], name='c1')
else:
self.model.addConstr(self.batch_nb[0] <= lhs_c1 <= self.batch_nb[1], name='c1')
# 约束(2) 保证模式使用次数和其包裹数量匹配
for p in self.pattern_dict.keys():
lhs_c2 = 0
for x_id, x_val in self.x.items():
if x_id[1] == p:
lhs_c2 += x_val
self.model.addConstr(lhs_c2 == self.pattern_dict[p].package_nb, name='c2')
# 约束(3) 保证单一波次商品件数在区间[G1,G2]中
# 约束(4) 保证单一波次包裹数量在区间[P1,P2]中
for j in range(1, self.batch_nb[1] + 1):
lhs_c3 = 0
lhs_c4 = 0
for x_id, x_val in self.x.items():
if x_id[0] == j:
lhs_c3 += x_val * self.pattern_dict[x_id[1]].goods_nb
lhs_c4 += x_val
self.model.addConstr(lhs_c3 >= self.z[j] * self.goods_limit[0], name='c3')
self.model.addConstr(lhs_c3 <= self.z[j] * self.goods_limit[1], name='c3')
self.model.addConstr(lhs_c4 >= self.z[j] * self.package_limit[0], name='c4')
self.model.addConstr(lhs_c4 <= self.z[j] * self.package_limit[1], name='c4')
# 约束(5) 确认波次j是否用到仓库k
for j in range(1, self.batch_nb[1] + 1):
for k in self.ware_dict.values():
lhs_c5 = 0
for p in self.pattern_dict.keys():
if k in p[1:]:
lhs_c5 += 1 * self.x[(j, p)]
lhs_c5 -= self.big_M * self.y[(j, k)]
self.model.addConstr(lhs_c5 <= 0, name='c5')
- 目标函数
1
2
def add_objective(self):
self.model.setObjective(gp.quicksum(self.y.values()), sense=GRB.MINIMIZE)
- 求解结果：100s内，gap为9.127%，最优解为252
1
2
3
4
5
6
7
Explored 8045 nodes (1974431 simplex iterations) in 100.00 seconds (140.96 work units)
Thread count was 8 (of 8 available processors)
Solution count 10: 252 253 254 ... 284
Time limit reached
Best objective 2.520000000000e+02, best bound 2.290000000000e+02, gap 9.1270%