无人仓系统订单分批问题及Kmax聚类算法.pdf

第 27 卷第 5 期 计算机集成制造系统
2 0 2 1 年 5 月 Computer Integrated Manufacturing Systems May 2 0 2 1
DOI：／j . .05 .026
无人仓系统订单分批问题及 K-max 聚类算法
李珍萍1 ，田宇璇1 ，卜晓奇1 ，吴凌云2 ，3
（1 .北京物资学院 信息学院，北京 101149 ；
2 .中国科学院 数学与系统科学研究院，北京 100190；
3 .中国科学院大学 数学科学学院，北京 100049）
摘 要：为了提高订单拣选效率、降低拣选成本，研究了以自动引导小车（AGV）为搬运工具的无人仓库系统订
单分批问题。分析了影响订单拣选成本和效率的两种主要因素，建立了以订单分批拣选总成本极小化为目标的整
数规划模型。根据 K-means 聚类算法思想，结合订单分批问题的优化目标，基于每批订单中包含的商品种类和拣
选每批订单需要搬运的货架信息，利用取大（max）运算符分别定义了能够反映订单拣选成本的两种类中心，以及订
单到两种类中心的距离。进一步以工作人员拣选每种商品的单位成本和 AGV 搬运一个货架的成本为权重，构造
了订单到批次（类中心）的加权距离。在此基础上设计了 K-max 聚类算法求解订单分批问题。采用具体算例验证
了 K-max 聚类算法的有效性。
关键词：无人仓；货到人；订单分批；分类型数据；取大运算；K-max 聚类算法；加权距离
中图分类号：O221 .4；F253 .4 文献标识码：A
Order batching problem of unmanned warehouse system and K-max clustering algorithm
，
LI Zhenping 1 ，TIAN Yuxuan 1 ，BU Xiaoqi 1 ，WU Lingyun 2 3
（1 .School of Information，Beijing Wuzi University，Beijing 101149 ，China；
of Mathematics and Systems Science，Chinese Academy of Sciences，Beijing 100190，China；
3 .School of Mathematical Sciences，University of Chinese Academy of Sciences，Beijing 100049 ，China）
Abstract：To improve the efficiency and reduce the cost of order picking，the order batching probl