基于“货到人”拣选模式的储位分配问题研究

研究了“货到人”拣选模式下的储位分配问题,以订单拣选过程中搬运货架总时间最短为目标建立了整数非线性规划模型,并证明其为NP-hard问题,分别设计了求解模型的贪婪算法和单亲进化遗传算法。首先根据订单和物品的关联关系对物品进行聚类,基于聚类结果设计了求解模型的贪婪算法。然后设计了直接求解模型的单亲进化遗传算法,遗传算法中采用了0-1矩阵编码、多点基因倒位算子、单点基因突变算子和精英保留等策略,通过合理选取参数,能够很快求解出问题的近似最优解。最后利用模拟算例和一个具体实例进行计算,并对贪婪算法和遗传算法的求解时间和求解效果进行了比较分析。结果显示,对于小规模问题,两种算法均能在较短的时间内以很高的概率得到问题的全局最优解,对于中等规模的实际问题,利用两种算法得到的储位分配方案均优于企业目前采取的基于出库频率的储位分配方案,遗传算法得到的储位分配方案对应的货架搬运次数、货架搬运总时间等均优于贪婪算法。本文设计的遗传算法可以作为智能仓库管理信息系统的核心算法。

Study on the Storage Allocation Problem Under Cargo to Person Picking Mode

The storage allocation problem under cargo to person picking mode is studied.An integer nonlinear programming model is established to minimize the total time of moving shelves in the process of orders picking,the problem is proved to be NP-hard,and then two different approaches are designed to solve the model.In the greedy approach,the items are first clustered based on the relationship of orders and items,and then a greedy algorithm is applied on the clustering results.In another approach,the partheno evolution genetic algorithm is designed to solve the model directly.By adopting 0-1 matrix encoding rule,multipoint gene inversion operator,single point gene mutation operator and elitism scheme,with reasonable selection of parameters,the approximate optimal solution of the problem can be quickly found.Simulation is done on several simulation examples and a real case.The running time and effect of the greedy algorithm and the genetic algorithm are compared and ana-lyzed.The results show that for small scale problems,both algorithms can get the global optimal solution with high probability in a relatively short time,and for the medium scale real case,the storage allocation schemes obtained by both algorithms are better than the enterprise’s current storage allocation scheme.The storage allocation scheme obtained by genetic algorithm is better than that of the greedy algorithm in terms of the number of shelf movements and the total moving time.The genetic algorithm designed in this paper can be used as the core algorithm of intelligent warehouse management information system.