Abstract: 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.

Key words: unmanned warehouse, parts to picker, order batching, categorical data, max operator, K-max clustering algorithm, weighted distance

摘要： 为了提高订单拣选效率、降低拣选成本,研究了以自动引导小车(AGV)为搬运工具的无人仓库系统订单分批问题。分析了影响订单拣选成本和效率的两种主要因素,建立了以订单分批拣选总成本极小化为目标的整数规划模型。根据K-means聚类算法思想,结合订单分批问题的优化目标,基于每批订单中包含的商品种类和拣选每批订单需要搬运的货架信息,利用取大(max)运算符分别定义了能够反映订单拣选成本的两种类中心,以及订单到两种类中心的距离。进一步以工作人员拣选每种商品的单位成本和AGV搬运一个货架的成本为权重,构造了订单到批次(类中心)的加权距离。在此基础上设计了K-max聚类算法求解订单分批问题。采用具体算例验证了K-max聚类算法的有效性。

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