无人仓系统订单分批问题及K-max聚类算法  

Order batching problem of unmanned warehouse system and K-max clustering algorithm

作　　者：李珍萍[1] 田宇璇 卜晓奇 吴凌云[2,3] LI Zhenping;TIAN Yuxuan;BU Xiaoqi;WU Lingyun(School of Information,Beijing Wuzi University,Beijing 101149,China;Academy of Mathematics and Systems Science,Chinese Academy of Sciences,Beijing 100190,China;School of Mathematical Sciences,University of Chinese Academy of Sciences,Beijing 100049,China)

机构地区：[1]北京物资学院信息学院,北京101149 [2]中国科学院数学与系统科学研究院,北京100190 [3]中国科学院大学数学科学学院,北京100049

出　　处：《计算机集成制造系统》2021年第5期1506-1517,共12页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(71771028);北京市自然科学基金资助项目(Z180005,9212004);北京市属高校高水平科研创新团队建设资助项目(IDHT20180510);北京市高校高水平人才交叉培养项目“实培项目”;北京市智能物流协同创新中心开放课题资助项目(BILSCIC-2019KF-18);北京物资学院校级重大资助项目(2019XJZD09);北京市科技创新服务能力建设—高精尖学科建设资助项目。

摘　　要：为了提高订单拣选效率、降低拣选成本,研究了以自动引导小车(AGV)为搬运工具的无人仓库系统订单分批问题。分析了影响订单拣选成本和效率的两种主要因素,建立了以订单分批拣选总成本极小化为目标的整数规划模型。根据K-means聚类算法思想,结合订单分批问题的优化目标,基于每批订单中包含的商品种类和拣选每批订单需要搬运的货架信息,利用取大(max)运算符分别定义了能够反映订单拣选成本的两种类中心,以及订单到两种类中心的距离。进一步以工作人员拣选每种商品的单位成本和AGV搬运一个货架的成本为权重,构造了订单到批次(类中心)的加权距离。在此基础上设计了K-max聚类算法求解订单分批问题。采用具体算例验证了K-max聚类算法的有效性。To improve the efficiency and reduce the cost of order picking,the order batching problem of unmanned warehouse system based on Automatic Guided Vehicle(AGV)was investigated.Two main factors affecting the cost and efficiency of order picking under“parts-to-picker”mode were considered:the number of item categories being picked up from the shelves,and the number of shelves being transported to working station.An integer programming model to minimize the total cost of order picking was established.Based on the items category in a batch of orders and the shelves to be transported when picking the batch of orders,two types of clustering centers related to the cost of order picking were defined using“max”operator respectively,the first clustering center was based on item categories to be picked and the second clustering center was based on the shelves to be transported.Two types of distances from an order to two clustering centers were defined respectively.Furthermore,the weighted distance from an order to a batch(clustering center)was formulated,and the weight coefficients were the unit cost of worker picking up one type of items and the unit cost of AGV moving one shelf.Based on the idea of K-means clustering algorithm,a new clustering algorithm named K-max clustering was designed to solve the order batching problem based on the categorical data.A numerical example was used to analyze the effective of K-max clustering algorithm.The sensitivity analysis of the weighted coefficients was given,and the effectiveness of K-max clustering algorithm for solving the order batching problem was verified.

关 键 词：无人仓 货到人 订单分批 分类型数据 取大运算 K-max聚类算法 加权距离 

分 类 号：O221.4[理学—运筹学与控制论] F253.4[理学—数学]