摘要：构造了拣货作业中订单分批问题的数学模型，在聚类分析的基础上，提出了三种相似系数计算公式，并建立了订单分批问题的聚类模型。然后采用启发式算法求解聚类模型得到分批结果，再根据分批模型求最短行走距离。最后以拣货行走的总距离为目标，用算例将算法与现有的分批方法进行比较，验证了模型和算法的有效性。

关键词：拣货作业；订单分批；聚类分析；模型；算法

配送中心拣货作业中的订单分批是为了提高拣货作业效率而把多张订单集合成一批，进行批次拣取作业，其目的是缩短拣取时平均行走搬运的距离和时间。若再将每批次订单中的同一商品品项汇总后拣取，然后再把货品分配给每一个顾客订单，则形成批量拣取，这样不仅缩短了拣取时平均行走搬运的距离，也减少了重复寻找储位的时间，而使拣货效率提高。批量拣取特别适合于品项数少而订单数量庞大的系统，越是少量多次的配送，批量拣取就越有效。

订单分批问题用数学语言来表达就是指将订单按照适当的方式进行分批并确定批量拣取路径以使目标函数达到最优^［1］。批量拣取的基础目标有两种：①减少拣货行走的总时间；②减少拣货行走的距离进而提升产能和改善交货期。Elsayed　and Stern^［2］, Hwang and Lee ^［3］, Pan and Liu ^［4］对单巷道仓库的订单分批问题作了研究。Gibson and Sharp^［5］，Rosenwein^［6］，De Koster et al.^［7］对多种启发式分批方法的效果进行了比较研究。Gademann et al.^［8］在一个人工分波次拣货（wave picking）系统中，以最小化任意批量的最大前置时间为目标，考虑了拣取位置临近分批问题。Rosenwein^［9］建立了订单分批问题的p－中值0－1规划整数模型。Chen et al.^［10］采用数据挖掘方法对订单分批问题进行了研究。Hwang and Kim^［11］对低层人至物拣货系统，针对不同的路径策略建立了统一的聚类分批模型，但相似系数的计算是以路径策略事先给定为前提的。本文以最小化拣货行走距离为目标构造了订单分批问题的数学模型，并将问题转化为聚类问题进行求解，提出了多种相似系数的计算方法，且相似系数的计算不需要事先知道路径策略，基于聚类分析的启发式算法能有效求得订单分批问题的近优解。