基于超图嵌入表示的商品分仓模型

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

摘要/Abstract

摘要：

电子商务的高速发展要求电商企业能快速地响应消费者的需求。当前，越来越多的电商企业通过构建分布式的配送中心，使库存尽可能地靠近消费者，从而实现分区域的就近发货和就近配送。然而，在多仓分布的设置下，不合理的商品分仓将导致大量的订单被拆分配送，这不仅会给消费者带来不便，还将使电商企业付出额外的运营成本。本文提出了一个以最小化被拆分订单的总量为目标的商品分仓优化模型。首先，基于已有的历史订单数据，构造超图G，使G中不同的顶点对应不同的商品，G中的超边则反映了商品在订单中的共现关系，通过对G做谱图分解，获得了对各商品的嵌入表示。然后，基于上述表示，提出了带上、下限簇数限制的约束聚类算法，并通过该算法生成商品分仓的结果。使用主题模型LDA（latent dirichlet allocation）生成的模拟订单数据作为实验分析的对象，在不同的参数设置下，生成了大量模拟订单数据，把本文提出的模型与当前流行的模型分别应用于这些数据以生成商品分仓的结果，实验结果显示，与现有的模型相比，本文提出的模型有明显的优势。

关键词: 商品分仓, 超图, 嵌入表示, 聚类, 运作优化

Abstract:

The rapid development of e-business（EB for short） requires EB companies to respond to consumer requirements quickly， in order to improve their efficiency of customer services， more and more EB companies have deployed distributeddistribution center systems. A main problem with using this system is that improper commodity warehouse allocation may result in a large number of orders being divided into multiple sub-orders， which not only causes inconvenience to customers， but also increases more operating costs to companies. Addressing to this problem， a commodity warehouse allocation model aimed at minimizing the total number of split orders is proposed. The model is based on a hypergraph representation of historic orders， where each vertex corresponds to a distinct goods appearing in the orders， and each hyperedge describes a co-occurrence relation of goods in a same orders. The spectrum decomposition on the Laplace matrix of the hypergraph is performed to obtain the embedding representations of the goods， then a constrained clustering algorithm is proposed and is applied to the above embeddings to generate the allocation results. The comprehensive simulations is conducted to evaluate the proposed model， where LDA （Latent Dirichlet Allocation） with variant parameter settings is used to simulate different ordering behaviors， and the proposed model as well as some other comparison models is applied to generate the allocation results from the data.All experimental results show the superior of our model.

Key words: commodity warehouse allocation, hypergraph, embedding representation, clustering, operations optimization

中图分类号:

TP181

刘顺,黄晓宇,鲜征征, 等. 基于超图嵌入表示的商品分仓模型[J]. 中国管理科学, 2024, 32(11): 270-278.

Shun Liu,Xiaoyu Huang,Zhengzheng Xian, et al. A Commodity Warehouse Allocation Model Based on Hypergraph Embedding[J]. Chinese Journal of Management Science, 2024, 32(11): 270-278.

图/表 11

图1

表1

图2

表2

各数据集使用的参数设置"

参数	DS-1	DS-2	DS-3	DS-4
浓度参数 $τ α$	0.0001	0.0001	0.0001	0.0001
浓度参数 $τ β$	0.001	0.003	0.001	0.001
主题个数t	200	200	500	200
泊松强度 $λ$	3.5	3.5	3.5	6
订单总数 $N$	100000	100000	100000	100000
最大长度h	12	12	12	12

表2

图3

表3

表4

不同泊松强度下品项组的分布情况"

品项组	泊松强度 $λ = 3.5$	泊松强度 $λ = 6$
2项组	21348	4531
3项组	25099	9234
4项组	21647	13546
5项组	15367	16428
6项组	8903	16740
7项组	4487	14007
8项组	2007	10480
≥9项组	1142	15034
总数	100000	100000

表4

表5

表6

表7

表8

参考文献 17

1	Seidscher A， Minner S. A Semi-Markov decision problem for proactive and reactive transshipments between multiple warehouses［J］. European Journal of Operational Research， 2013， 230（1）： 42-52.
2	Jasin S， Sinha A. An LP-based correlated rounding scheme for multi-item ecommerce order fulfillment［J］. Operations Research， 2015， 63（6）： 1336-1351.
3	Wang J Z， Huang P P， Zhao H， et al. Billion-scale commodity embedding for e-commerce recommendation in Alibaba［C］//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining， New York， USA， August 19-23 ， Association for Computing Machinery， 2018：839-848.
4	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.
5	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.
6	Andrés C， Marshall F. Assortment allocation to distribution centers to minimize split customer orders［R］. Working Paper， SSRN， 2012..
7	李建斌，李乐乐，黄日环.最小化拆单率的在线零售商多仓商品摆放优化策略研究［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］. Jornal of Industrial Engineering/Engineering Management， 2017，31（3）：167-173.
8	李建斌，孙哲，陈威帆，等.面向最小化拆单率的基于订单分配顺序的库存优化研究［J］.工业工程与管理，2017，22（6）：78-84.
	Li J B， Sun Z， Chen W F， et al. Research on inventory optimization for minimizing the rate of separating bills based on the sequence of order distribution［J］. Industrial Engineering and Management，2017，22（6）：78-84.
9	钟丽文，姜同强. 基于改进贪婪关联算法的在线零售商优化拆单问题［J］. 工业工程，2021，24（2）：134-140.
	Zhong L W， Jiang T Q. Online retailer optimal splitting problem based on improved greedy association algorithm［J］. Industrial Engineering Journal，2021，24（2）：134-140.
10	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.
11	朱姗，张博，胡祥培.“一地多仓”型网上超市多品订单的拆分优化决策方法［J］.中国管理科学，2024， 32（4）： 250-260.
	Zhu S， Zhang B， Hu X P. Order splitting optimization method of multi-item order fulfillment in online supermarkets with multi-warehouses in a city［J］. Chinese Journal of Mangement Science，2024，32（4）： 250-260.
12	胡秉德，王新根，王新宇，等.超图学习综述：算法分类与应用分析［J］.软件学报，2022，33（2）：498-523.
	Hu B D， Wang X G， Wang X Y， et al. Survey on hypergraph learning： Algorithm classification and application analysis［J］. Journal of Software， 2022， 33（2）： 498-523.
13	Zhou D， Huang J， Schölkopf B. Learning with hypergraphs： Clustering， classification， and embedding［C］//Proceedings of the 19th International Conference on Neural Information Processing Systems，Vancouver， British Columbia， Canada， December 4-7， The MIT Press， 2006：1601-1608.
14	Bradley P S， Bennett K P， Demiriz A. Constrained k-means clustering［R］.Working Paper，Microsoft Research，2000.
15	Orlin J B. A polynomial time primal network simplex algorithm for minimum cost flows［J］. Mathematical Programming， 1997， 78（2）： 109-129.
16	Blei D M， Ng A Y， Jordan M I. Latent dirichlet allocation［J］. Journal of Machine Learning Research， 2003， 3（Jan）： 993-1022.
17	Hastie D I， Liverani S， Richardson S. Sampling from Dirichlet process mixture models with unknown concentration parameter： Mixing issues in large data implementations［J］. Statistics and Computing， 2015， 25（5）： 1023-1037.

订单编号	订购商品
D₁	V₂，V₄，V₈
D₂	V₁，V₆，V₇
D₃	V₃，V₅，V₆

数据集	待分仓商品数	0.0005	0.001	0.003	0.005
DS-1	4794	7168	2032	46	0
DS-2	7819	1506	147	0	0
DS-3	7566	3586	376	0	0
DS-4	5234	48439	14077	652	6

算法训练集比例	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
EMCLS（K=10）	16.13	16.94	16.28	16.72	14.42	14.26	15.15	13.26	13.23
EMCLS（K=30）	12.55	11.07	11.38	11.72	11.16	11.25	11.26	11.41	10.98
EMCLS（K=50）	11.79	11.56	12.12	11.89	12.01	11.59	11.74	11.54	11.57
EMCLS（K=100）	13.68	14.15	14.28	14.54	15.43	13.91	14.04	14.65	13.75
LOOP（HR=0.02）	42.72	42.76	45.18	46.95	46.69	46.78	46.93	46.85	46.93
LOOP（HR=0.05）	39.80	43.15	44.82	44.65	44.37	44.55	44.62	44.46	44.84
LOOP（HR=0.1）	36.83	40.12	40.23	40.30	40.27	40.02	39.92	39.57	39.67
RC	77.29	82.51	83.88	85.31	86.56	87.06	87.47	89.05	88.60

算法训练集比例	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
EMCLS（K=10）	43.06	39.61	39.85	40.09	39.68	38.25	40.58	39.61	38.76
EMCLS（K=30）	37.79	36.03	35.31	35.98	34.79	35.62	35.46	35.16	34.68
EMCLS（K=50）	36.96	36.18	35.34	35.47	34.72	34.09	34.71	35.01	34.63
EMCLS（K=100）	38.08	37.88	37.73	36.70	36.99	36.19	36.78	37.39	36.44
LOOP（HR=0.02）	75.71	76.08	76.15	76.20	76.15	75.72	75.38	76.05	75.99
LOOP（HR=0.05）	72.09	72.07	71.92	71.91	71.79	71.43	70.72	71.41	71.25
LOOP（HR=0.1）	67.17	66.88	66.78	66.38	66.75	65.87	65.50	66.43	66.02
RC	92.85	92.67	92.73	92.64	92.83	92.56	92.60	92.58	92.93

算法训练集比例	0.1	0.2	0.3	0.4	0.5	0.6	0.7	0.8	0.9
EMCLS（K=10）	40.61	36.41	37.83	37.16	38.44	38.13	37.92	38.41	35.96
EMCLS（K=30）	35.05	32.47	34.09	34.56	33.43	33.38	33.18	33.66	33.43
EMCLS（K=50）	34.34	31.56	32.96	31.39	31.95	31.48	30.83	30.66	31.78
EMCLS（K=100）	34.21	31.80	30.89	31.34	30.36	31.02	30.50	30.12	31.09
LOOP（HR=0.02）	77.52	78.22	78.53	78.42	78.62	78.62	78.47	78.81	79.01
LOOP（HR=0.05）	74.48	75.22	75.12	74.92	74.70	74.83	74.56	74.91	75.41
LOOP（HR=0.1）	69.61	70.17	69.81	69.49	69.71	69.85	69.18	69.47	69.85
RC	92.24	92.94	92.94	92.09	92.90	92.94	92.93	92.76	92.55