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

李珍萍，田宇璇,卜晓奇，吴凌云

(1.北京物资学院 信息学院，北京 101149；2.中国科学院 数学与系统科学研究院，北京 100190；3.中国科学院大学 数学科学学院，北京 100049)

0 引言

近年来，电子商务迅速发展，电商企业每天要处理的订单数量和订单类型越来越多。在大型配送中心内部，订单拣选作业时间约占总作业时间的30%～40%，拣选作业成本占到总作业成本的60%[1],对订单采取分批拣选策略可以有效减少作业时间、降低拣选成本[2-3]。因此，研究如何对订单进行分批是电商企业关注的重要问题之一。

传统的电商企业物流配送中心大多采用以人工作业为主的“人到货”拣选模式，该模式耗时长、效率低，容易出差错。近年出现的无人仓系统(如Kiva System[4-5])采用以自动导引小车(Automated Guided Vehicle, AGV)为主要运载工具的“货到人”拣选模式，这种模式具有拣选效率高且劳动强度低的优点，特别适合电商企业的多品种、小批量、多批次订单[4-5]。在基于AGV的无人仓系统中，对于每一组待处理订单列表(拣选单)，首先由计算机控制系统确定需要搬运的货架和搬运路线，然后指派AGV将货架搬运至工作台前，等待工作人员从货架上拣取商品，再将货架送回仓库适当的位置。无人仓系统用AGV搬运货架代替人工行走，大大降低了工作人员的劳动强度。

无论是基于人工拣选的传统仓库，还是基于AGV的无人仓系统，订单分批策略都是直接影响订单拣选效率和拣选成本的最主要因素之一[2,4-5]。订单分批问题就是将陆续到达的众多订单按照一定规则划分为若干批次，每个批次对应一个订单列表(称为一个拣选单),每一批次订单同时进行拣选[6]。……