“一地多仓”型网上超市多品订单的拆分优化决策方法

doi:10.16381/j.cnki.issn1003-207x.2021.0799

摘要/Abstract

摘要：

近年来以京东为首的大型网上超市零售电商蓬勃发展，其“一地多仓”的仓储布局和大量“一单多品”的订单特性使得订单拆分履行成为普遍现象，进而引发了配送高扰动、履行高成本等一系列难题，该问题的复杂性在于随着订单规模及其所含品项数的增加，导致订单拆分方案数呈指数增长。本文针对订单拆分优化难题，综合运用组合优化和聚类分析理论，以最小化订单拆分履行成本为目标，从缩减求解空间的视角出发，设计了高效的基于商品相关性的PLBH-LNS（product link-based hybrid heuristic large neighborhood search algorithm）算法。通过对小规模的构造算例进行分析，与CPLEX结果比较，验证了算法的科学性和有效性；并采用国内某零售电商大规模实际数据进行实验分析，验证了算法的实用性。实验结果表明，与实际操作中运用简单规则的订单拆分策略相比，PLBH-LNS方法平均能缩减22.48%的订单拆分履行成本，为大型网上超市的订单拆分问题提供了新思路和有效的辅助决策支持。

关键词: 网上超市, 订单拆分, 一地多仓, 一单多品, 大规模邻域搜索算法

Abstract:

In recent years online supermarkets such as JD.com have developed greatly in the e-commerce environment. Order splitting has been a common phenomenon in practical operations due to two main features of the online supermarket： one is the multi-warehouse network in one big city， the other is the vast multi-item customer orders. Serious order splitting problem intrigues some challenges such as high delivery disturbance， high fulfillment cost. The complexity of this problem is that the solution space will be large because of the explosive increased number of splitting solutions with the increase in the number of orders and the number of items in each order. Synthetically applying the theories of combinatorial optimization and clustering analysis， the order splitting optimization problem is investigated to minimize the order splitting fulfillment cost. For the sake of decreasing the solution space， the product link-based hybrid heuristic large neighborhood search algorithm （PLBH-LNS） is proposed. The effectiveness and practicality of the PLBH-LNS algorithm are verified using a series of generated small-scale datasets and a real large-scale dataset from an online retailer in China. The results show that， compared with the myopic order splitting strategy in practical operations， the PLBH-LNS algorithm could decrease the average order fulfillment cost by 22.48%. A new method and idea for the online supermarket order splitting in e-commerce is provided， which also supports the order fulfillment decision for decreasing the order splitting.

Key words: online supermarket, order splitting, multi-warehouse system, multi-item orders, large neighborhood search

中图分类号:

朱姗,张博,胡祥培. “一地多仓”型网上超市多品订单的拆分优化决策方法[J]. 中国管理科学, 2024, 32(4): 250-260.

Shan Zhu,Bo Zhang,Xiangpei Hu. Order Splitting Optimization Method of Multi-item Order Fulfillment in Online Supermarkets with Multi-warehouses in a City[J]. Chinese Journal of Management Science, 2024, 32(4): 250-260.

图/表 13

图1

图2

表1

模型参数符号说明"

符号	参数说明
$K$	仓库编号， $k = 1,2, …, K$
$J$	顾客订单编号， $j = 1,2, …, J$
$I$	商品SKU编号， $i = 1,2, …, I$
$S k i$	表示仓库 $k$ 中商品 $i$ 的库存量
$D j i$	表示订单 $j$ 中商品 $i$ 的需求量
$d i s k j$	表示仓库 $k$ 到顾客(订单) $j$ 的距离
$C 1 p a c k$	表示仓库中单个包裹的打包成本
$C 2 f i x e d$	表示从仓库出发进行一次运输的固定启动成本
$C 2 v a r i a b l e$	表示从仓库出发进行一次运输的每公里的单位可变成本
决策变量
$x i j k$	正整数，表示从仓库 $k$ 运送去满足订单 $j$ 中的商品 $i$ 的数量
$y j k$	0/1变量，表示是否从仓库 $k$ 到订单 $j$ 进行了一次运输

表1

图3

图4

图5

图6

图7

表2

实验基本参数设置"

参数	取值	参数	取值
$C 1 p a c k$	0.5	$τ m i n$	0.1
$C 2 f i x e d$	6	$τ m a x$	0.3
$C 2 v a r i a b l e$	0.3	$M a x I t e r$	50

表2

表3

小规模算例PLBH-LNS和CPLEX结果比较"

算例	仓库数 $K$	订单数 $J$	总的订单拆分履行成本(元)			CPU时间(秒)
算例	仓库数 $K$	订单数 $J$	CPLEX	PLBH-LNS	Gap (%)	CPLEX	PLBH-LNS
1	3	40	676.06	676.06	0	48.45	5.70
2	3	50	864.76	864.76	0	68.57	11.06
3	3	80	1352.90	1352.90	0	120.00	15.41
4	3	100	1713.50	1713.50	0	169.05	35.53
5	3	200	3305.10	3305.10	0	572.86	68.56
6	3	300	5172.20	5295.80	2.39	1506.52	75.58
7	4	40	678.16	678.16	0	83.71	8.09
8	4	50	812.29	812.29	0	99.11	12.92
9	4	80	1312.30	1331.72	1.48	222.48	27.02
10	4	100	1663.60	1710.35	2.81	273.44	31.96
11	4	200	3115.00	3115.00	0	845.34	74.72
12	4	300	─	4882.5	─	─	89.22
13	5	40	628.99	628.99	0	107.35	8.12
14	5	50	663.69	663.69	0	147.67	11.76
15	5	80	1142.90	1184.95	3.68	287.17	35.93
16	5	100	1469.00	1469.00	0	401.90	57.34
17	5	200	2780.10	2786.50	0.23	1653.90	91.82
18	5	300	─	4613.10	─	─	92.61

表3

图8

图9

表4

大规模算例PLBH-LNS结果和实际结果比较"

算例	订单数 $J$	总的订单履行成本(元) $m i n ? F C$			CPU时间(秒)
算例	订单数 $J$	Real	PLBH-LNS	Saving（%）	PLBH-LNS
1	937	16700	12820	23.23	240.813
2	770	13920	11340	18.53	304.021
3	820	16113	12027	25.36	248.104
4	769	13067	10204	21.91	174.136
5	774	13885	11273	18.81	270.245
6	853	13155	9598	27.04%	211.876

表4

参考文献 28

1	Ardjmand E， SaneiBajgiran O， Rahman S， et al.A multi-objective model for order cartonization and fulfillment center assignment in the e-tail/retail industry［J］.Transportation Research Part E： Logistics and Transportation Review，2018， 115： 16-34.
2	商务部公共服务信息网.2020年上半年网络零售市场发展情况［EB/OL］.［2020-08-20］..
	Ministry of Commerce Public Service Information Network. Development of Online Retail Market in the First Half of 2020.［EB/OL］.［2020-08-20］..
3	熊浩，鄢慧丽.考虑多种安全库存策略的选址-库存问题研究［J］.中国管理科学，2021， 29（1）： 72-81.
	Xiong H， Yan H L. Six Location-inventory modles with risk pooling in two-echelon logistics systems［J］. Chinese Journal of Mangement Science， 2021， 29（1）： 72-81.
4	张源凯，胡祥培，黄敏芳，等.网上超市拆分订单合并打包策略经济决策模型［J］.管理科学学报，2019， 22 （10）： 24-36+100.
	Zhang Y K， Hu X P， Huang M F， et al. Economic decision model for package consolidation in fulfilling split orders of online supermarkets［J］. Journal of Management Science in China， 2019， 22（10）： 24-36+100.
5	Difrancesco R M， Van Schilt I M， Winkenbach M.Optimal in-store fulfillment policies for online orders in an omni-channel retail environment［J］.European Journal of Operational Research，2021， 293（3）：1058-1076.
6	黄敏芳，张源凯，王颜新，等.基于JIT装配模式的网上超市订单分拣优化模型［J］.中国管理科学，2020， 28（5）： 159-166.
	Huang M F， Zhang Y K， Wang Y X， et al. JIT assembly line-based order picking process optimization method for online supermarkets［J］. Chinese Journal of Mangement Science， 2020， 28（5）： 159-166.
7	Becerrilarreola R， Leng M， Parlar M.Online retailers’ promotional pricing， free-shipping threshold， and inventory decisions： a simulation-based analysis［J］.European Journal of Operational Research，2013， 230（2）： 272-283.
8	Catalan A F M.Assortment allocation to distribution centers to minimize split customer orders［J］.SSRN Electronic Journal，2012. .
9	Zhu S， Hu X， Huang K， et al.Optimization of product category allocation in multiple warehouses to minimize splitting of online supermarket customer orders［J］.European Journal of Operational Research，2021， 290（2）： 556-571.
10	李建斌，李乐乐，黄日环.最小化拆单率的在线零售商多仓商品摆放优化策略研究［J］.管理工程学报，2017， 31（3）： 167-173.
	Li J B， Li L L， Huang R H. Inventory allocation policy to distribution centers with minimum split orders in online retailing［J］. Journal of Industrial Engineering and Engineering Management， 2017，31（3）： 167-173.
11	Zhang Y， Huang M， Hu X， et al.Package consolidation approach to the split-order fulfillment problem of online supermarkets［J］.Journal of the Operational Research Society，2018， 69（1）： 127-141.
12	Zhang Y， Lin W H， Huang M， et al.Multi-warehouse package consolidation for split orders in online retailing［J］.European Journal of Operational Research，2021， 289 （3）： 1040-1055.
13	Xu P J， Allgor R， Graves S C.Benefits of reevaluating real-time order fulfillment decisions［J］.Manufacturing & Service Operations Management，2009， 11（2）： 340-355.
14	Jasin S， Sinha A.An LP-based correlated rounding scheme for multi-item ecommerce order fulfillment［J］.Operations Research，2015， 63 （6）： 1336-1351.
15	Acimovic J， Graves S C.Making better fulfillment decisions on the fly in an online retail environment［J］.Manufacturing & Service Operations Management，2015， 17（1）： 34-51.
16	Jason A. Lowering outbound shipping costs in an online retail environment by making better fulfillment and replenishment decisions［D］. Boston： Massachusetts Institute of Technology，2012.
17	Torabi S A， Hassini E， Jeihoonian M.Fulfillment source allocation， inventory transshipment， and customer order transfer in e-tailing［J］.Transportation Research Part E-logistics and Transportation Review，2015， 79： 128-144.
18	Mahar S， Wright P D.The value of postponing online fulfillment decisions in multi-channel retail/e-tail organizations［J］.Computers & Operations Research，2009， 36（11）： 3061-3072.
19	JD.com Company profile［EB/OL］.［2020-08-25］..
20	Chen L， Hsu F， Chen M， et al.Developing recommender systems with the consideration of product profitability for sellers［J］.Information Sciences，2008， 178 （4）： 1032-1048.
21	Xu P. order fulfillment in online retailing： what goes where［D］. Boston： Massachusetts Institute of Technology，2005.
22	Hwang H， Lee M.Order batching algorithms for a man-on-board automated storage and retrieval system［J］.Engineering Costs and Production Economics，1988， 13 （4）： 285-294.
23	Shaw P. Using constraint programming and local search methods to solve vehicle routing problems［C］//Proceeding of 4th International Conference on Principles and Practice of Constraint Programming， Pisa， Italy， October 26-30 ， Springer Berlin Heidelberg， 1998，417-431.
24	Mladenovic N， Hansen P.Variable neighborhood search［J］.Computers & Operations Research，1997， 24 （11）： 1097-1100.
25	Herrán A， Colmenar J M， Duarte A.A variable neighborhood search approach for the vertex bisection problem［J］.Information Sciences，2019， 476： 1-18.
26	Pisinger D， Ropke S. Handbook of metaheuristics ［M］. Boston： Springer US， 2010： 399-419.
27	Ropke S， Pisinger D.An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows［J］.Transportation Science，2006， 40 （4）： 455-472.
28	Ropke S， Pisinger D.A unified heuristic for a large class of Vehicle Routing Problems with Backhauls［J］.European Journal of Operational Research，2006， 171（3）： 750-775.

[1]	曹端阳, 张旭梅, 但斌. 考虑订单可拆分的第三方共享制造平台产能匹配策略[J]. 中国管理科学, 2025, 33(10): 225-235.
[2]	丁天蓉, 张源凯, 王玉英, 胡祥培. 基于关联网络的“人-机”双拣选系统仓储商品选择方法[J]. 中国管理科学, 2023, 31(3): 26-37.
[3]	黄敏芳, 张源凯, 王颜新, 胡祥培. 基于JIT装配模式的网上超市订单分拣优化模型[J]. 中国管理科学, 2020, 28(5): 159-166.
[4]	符卓, 刘文, 邱萌. 带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法[J]. 中国管理科学, 2017, 25(5): 78-86.