基于自适应交叉策略遗传算法的非空货位分配方案优化研究.docx

基于自适应交叉策略遗传算法的非空货位分配方案优化研究

摘要：针对“货到人”拣选系统的补货环节，考虑仓库起始状态非空条件下的货位分配问题，将货架现存商品种类及数量信息与订单包含的商品种类及数量信息进行比对，做出商品分配位置以及上架数量决策，以所有货架上的商品相似度总和最大化为目标，构建了整数非线性规划模型，并设计了自适应交叉策略的遗传算法进行求解，以问题实际约束对染色体生成、交叉和变异操作进行设计。通过随机算例来对算法进行测试，结果表明文章设计的算法能够有效解决其实状态非空的货位分配问题。

关键词：“货到人”拣选；货位分配；遗传算法

0??引??言

近年来，随着消费者需求的多样化转变，电子商务呈现出高频率、多品种、小批量的特点，对企业的仓储、分拣、订单处理等工作提出了更高的要求。作为一种新兴的拣选处理模式，“货到人”拣选系统（Roboticmobilefulfillmentsystems，RMFS）采用AGV（AutomatedGuidedVehicle）、AMR（AutonomousMobileRobot）、AGC（AutomatedGuidedCart）等设备[1]将储存货物的货架、托盘等载体搬运至人工拣选站实现“货到人”的拣选。这种“货到人”拣选模式最早于2012年由Amazon应用于仓储分拣系统中，目前国内的“货到人”拣选系统的实际运用已经有阿里菜鸟联盟智能仓、京东天狼货到人系统和快仓等。与传统的“人到货”拣选模式类似，“货到人”系统也需要解决货位分配、订单分批、任务指派和路径规划等[2]问题。其中，作为拣选流程中的先决步骤，仓储系统中的货位分配工作无疑影响着后续工作的组织和效率。目前已经有很多学者对“货到人”拣选系统的货位分配展开了大量研究，主要集中在问题模型的约束细化、优化目标的确定以及求解方法的改进等方面[3]。

在问题模型的约束细化方面，Mirzaei等[4]提出了规格相同的货位对于不同种商品的容量上限不同，更加贴合于现实问题中的标准化货位对应不同规格的商品。李英德[5]考虑了SKU相关性的装箱问题与货位分配的协同优化，设计了“SKUs对”相关性位置变换策略，并使用SAC算法和NFDP算法针对性地分别求解装箱问题和货位指派问题。杨雅婷等[6]在交叉存取拣选模式下考虑动态时间阈值和动态距离阈值，以拣选任务为主，在阈值约束下考虑是否执行存放任务并判断货物存放位置，同时优化了订单拣选顺序及货物上架位置的决策，实现了“货到人”拣选系统中的动态拣选与货位分配任务同时进行。张雪等[7]考虑了仓库非空状态下一品多位的货位分配问题，同时考虑滞销商品的下架操作和商品的上架位置指派优化，采用贪婪算法生成初始解，再采用粒子群优化算法求解该问题。

同时，由于不同行业对仓储运行的需求不尽相同，所以在进行货位分配决策时想要达到的目标也比较多元，常见的货位分配目标有单位时间的吞吐量最大、批次订单的拣选时间最短、单位货架的稳定性最高、货架上商品关联度最高等。Wang等[8]在考虑货架承重约束以及高度约束的同时以货架重心最低为目标，采用层次遗传算法求解货位分配问题。袁瑞萍等[9]以最小化货架搬运次数以及最小化机器人总拣选路程为目标，并结合商品分配到货架以及货架位置的两阶段决策思想，设计两阶段启发式算法进行求解。包菊芳等[10]以同一货架上SKU的总关联度最大为目标，采用FP-Growth算法以及聚类方法进行求解。周亚云等[11]综合考虑了商品需求关联度与周转率，通过计算商品关联性和相似性，采用基于拉普拉斯矩阵分解的SC算法中引入K-Means++算法对商品进行聚类完成货位分配决策。

在求解方法的改进方面，主要采用的方法有排队网络、启发式聚类、启发式算法以及一些仿真优化等。Keung等[12]以改进的A*算法计算拣选过程中所有货架的总移动距离，并以此衡量包括K-means聚类，高斯混合模型聚类，贝叶斯高斯混合模型聚类等在内的9种货位分配的聚类方法的优化效果。胡祥培等[13]通过对商品关联网络的构建、分析和聚类三个阶段来解决一品多位的商品货位分配问题。翟梦月等[14]同时考虑商品种类和数量的双重关联，以拣选批次订单货架移动次数最小为目标，设计了结合模拟退火思想的变邻域有哪些信誉好的足球投注网站算法进行求解。王征等[15]在已知未来订单信息以及货架上储存的商品种类信息的情况下建立货架热度和货架关联度模型，设计了双层邻域变换的禁忌有哪些信誉好的足球投注网站启发式算法来优化货架位置。

对于“货到人”系统中的商品分配到货架的货位分配问题，目前的研究大多都是针对仓库起始状态为空的归零优化，而在实际的仓储条件下，系统中的补货过程往往不是在仓库全部为空的状态下进行的。针对某一特定时刻的货位分配问题，本文考虑仓库起始状态非空，并根据订单信息来确定特定商品是否需要进行下架，以及某种