1 引言 随着电子商务的迅速发展，电商仓库中的商品种类越来越多、储位分布情况越来越复杂。为了提高订单拣选效率，降低拣选成本，国内外电商企业如京东和亚马逊等开始使用自动化无人仓库系统[1]。无人仓系统依靠自动化智能设备（如自动引导小车_AGV）搬运货架到工作人员面前（货到人）代替传统仓库中由工作人员在货架中穿梭行走（人到货）的作业模式，降低了人工作业成本，提高了仓储拣选效率。 无论是在传统的人到货拣选仓库，还是货到人的自动化无人仓中，储位分配策略都是影响订单处理时间和仓储作业效率的关键因素。针对传统的人到货拣选模式下储位分配问题的研究成果已经很多[2-11]，这些研究主要集中在储位分配策略[2-5]和储位分配算法[6-11]等方面。 近年来部分学者开始研究货到人拣选模式下的无人仓系统储位分配问题。早期研究大多针对基于堆垛机和传送带的自动化立体仓库，陈璐等[12]以提高AS/RS中堆垛机的使用效率和仓库的空间利用率为目标，建立了储位再分配问题的整数规划模型，并设计两阶段的启发式算法。陈璐和陆志强[13]研究了自动化立体仓库中储位分配和存取作业路径联合优化问题，建立了混合整数规划模型，并设计了基于禁忌搜索的两阶段优化算法。 针对基于自动引导小车（AGV）搬运货架场景的无人仓系统储位分配问题，周方圆和李珍萍[14]以总拣选成本最小化为目标建立了储位分配问题的数学模型，基于复杂二分网络社团结构划分的思想，设计了求解模型的启发式算法。李珍萍和李文玉[15]以降低总拣选成本为目标，建立了网上书店智能仓库系统储位优化模型，设计了启发式算法。Xiang Xi等[16]建立了以同一货架上存储的产品相似度之和最大为目标的储位分配问题混合整数线性规划模型，并使用Cplex软件进行求解。 由于储位分配问题属于NP难问题，现有研究主要集中在快速有效的算法设计方面。如对于传统人工拣选仓库的储位分配问题，主要从降低物料搬运成本[2]、减少人员行走距离或根据产品性质分类存储[4]等角度出发设计求解问题的启发式算法。对于货到人拣选模式的无人仓系统储位分配问题，主要从减少货架搬运次数的角度出发设计启发式算法[12，14-15]、禁忌搜索算法[13]等进行求解。 借鉴经典NP难问题的求解思路，为了改善解的质量，可以将启发式算法与智能优化算法相结合，设计两阶段算法[17-18]。两阶段算法的基本思想是首先利用某种较简单的方法（如贪婪算法）求出一个初始可行解，然后运用智能优化算法（如邻域搜索[19-20]、启发式算法、遗传算法等）对初始可行解逐步进行改进，得到近似最优解。 现有的针对无人仓系统储位分配问题的研究，通常假设物品入库之前，仓库中所有储位均为空储位[14-16]。实际中，无人仓系统工作一段时间以后，仓库中可能出现一部分储位上的商品剩余数量不足或已经消耗完，而另一部分储位上的商品剩余数量充足。此时需要对存量不足或缺货的商品进行补货，且补货商品只能存放到空余储位上，对于储量充足的商品不需要补充或调整储位。为了提高无人仓系统的拣选工作效率，需求量较大的商品往往被同时存放在多个货架的不同储位上[16]。在无人仓系统的补货阶段，初始储位状态非空、允许一种补货商品存放在到多个货架上的储位分配问题是对文献[14-16]研究场景的一般推广，具有更加现实的实际意义，目前的文献中尚未查阅到相关研究成果。 本文拟对无人仓系统补货阶段的储位分配问题开展研究，考虑部分商品需要补货、并且货架上只有一部分储位空闲，每种补货商品需要存放在一个或多个空余储位上的情况，建立储位分配问题的混合整数规划模型，并设计求解模型的两阶段启发式算法，进一步通过模拟计算分析算法的求解效果。 本文主要创新点在于：考虑到无人仓系统补货阶段各个货架上可能同时存在非空储位（存放着不需要补货商品）和空余储位（可用于存放补货商品）的实际情况，将文献[16]中货架初始储位全部为空的假设条件去掉，建立了补货商品储位分配优化模型并设计求解模型的快速有效算法，使之既可以用于解决货架初始储位全部为空情况下的储位分配问题，也可以用于解决货架上包含一部分非空储位情况下的一般储位分配问题。由于本文研究的场景更加符合实际情况，因此研究结果可以作为无人仓管理信息系统的核心模型和算法。 2 问题描述与分析 假设某电商企业销售n种商品，所有商品存放在无人仓中的s个货架上，每个货架有k个储位，每个储位仅存放一种商品，每种商品可以存放在多个储位上。已知每种商品需要占用的储位数，且仓库中的总储位数与所有商品需要的总储位数相等。在某个补货阶段，已知待补货的商品种类，每种待补货商品所需的储位数，各个货架上存放的不需要补货商品种类，以及货架上的空余储位情况。假设未来一段时间内可能接到m个订单需要拣选，已知每个订单中包含的商品种类，问如何为待补货商品分配储位，才能尽可能降低未来的订单拣选成本、提高拣选效率？ 在无人仓系统中，关联度大的商品经常出现在同一订单上。如果把经常出现在同一订单中的商品存放在相同的货架上，可以有效减少拣选过程中搬运货架的总次数，从而降低拣选成本、提高拣选效率[16]。根据以上分析，可以把同一货架上商品之间的关联度之和最大化作为无人仓系统储位分配问题的目标函数。
