基于关联网络的“人—机”双拣选系统仓储商品选择方法

      1 引言

      随着电子商务的快速发展，网络零售商物流配送中心需要处理的多种类、小批量和高时效性的订单日益增多[1，2]。订单拣选是配送中心的关键业务环节，传统“人到货”拣选模式下的拣选成本占据仓库运营成本55%以上[3]。为了缓解订单量的爆炸式增长以及高比例的一单多品订单给仓库运营带来的压力，网络零售商引入采用“货到人”拣选模式的机器人移动货架系统（robotic mobile fulfillment system，RMFS）[4，5]。AGV（automatic guided vehicle，自动导引小车）载着货架前往拣货站，拣货员在拣选站即可完成货物拣选操作。该系统在提升一单多品订单的拣选效率以及降低企业运营成本方面具有明显优势，已广泛应用于京东商城、天猫超市、亚马逊等网上超市[6，7]。

      机器人移动货架系统的多AGV拣选协同效率高、部署成本高、货架容量有限（例如某机器人移动货架系统的货架平均存储42个SKU（stock keeping unit，库存量单位）[8]，适用于拣选一单多品订单，而传统拣选模式存储空间大、空间利用率高、仓储成本低，适合批量拣选一单一品订单。大型网上超市企业在实际应用中发现，两种拣选系统正好优势互补。为了高效履行复杂多样的个性化订单，逐渐采用融合两种拣选模式的“人—机”双拣选系统，该系统可以最大程度发挥两个拣选系统的优势，进一步降低拣选成本，实现整体拣选效率的提升。然而，大型网上超市应用“人—机”双拣选系统却面临着两个拣选区域分别存储哪些商品（选品）的决策难题。尽管电商已经采取订单分批[9，10]、路径规划[11]、货位分配[12，13]等方式提高各拣选系统的拣货效率，但是，由于选品分配是双拣选系统首要关键性决策，如果仓储商品未进行合理划分，后续再多的优化调度也是徒劳。通过分析发现，由于大型网上超市具有的一单多品订单特点使得SKU间具有盘根错节的关联关系，仓库管理人员在规划双拣选系统仓储商品时，并没有充分挖掘SKU的关联性进行选品分配，导致合流订单量（由于订单被拆分到两个拣选区域分拣导致的）居高不下，这大大降低了系统的运行效率。与此同时，大型网上超市通常拥有数量庞大的SKU种类，使得选品问题的解空间巨大，大大提升了该问题的求解难度。因此，如何结合各拣选模式的优势、一单多品的订单特点，以最小化总的订单拣选成本为目标，研究“人—机”双拣选系统的选品问题，已经成为应用“人—机”双拣选系统亟需解决的关键难题。

      电商选品问题的相关研究主要集中于“人到货”“货到人”和“人—机”三种拣选模式。“人到货”和“货到人”拣选模式已经取得了丰富的研究成果，代表性的研究有：和Fisher[14]、李建斌等[15]、Zhu Shan等[16]。“人—机”双拣选系统是“人到货”和“货到人”两种不同拣选模式的协同合作。各仓库在拣选模式、订单偏好方面具有显著差异，因此，已有关于“人到货”或“货到人”拣选模式的选品方法相关研究无法直接应用于“人—机”双拣选系统。“人—机”双拣选系统的选品问题作为新兴研究方向，是目前研究的热点难题。现有研究主要围绕人工与A字机的双分拣系统，代表性研究有：李明等[17]从人工成本的角度对人工与A字机双分拣系统的品项分配优化问题进行了研究，并设计了启发式算法求解该问题。张贻弓和吴耀华[18]对双A字机拣货区的自动分拣系统品项分配优化问题进行研究，以最大化各订单提前拣选时间为目标建立数学模型，并应用最大最小蚂蚁系统算法求解。然而，A字机与机器人移动货架系统是两种自动化拣选系统，具有不同的拣选模式和系统特点。在融合人工拣选和机器人移动货架系统的双拣选系统选品研究方面，相关研究才刚刚起步。Wang Zheng等[19]以最小化订单合流成本和补货成本为目标，建立了“人—机”双拣选系统的整数规划模型，然而，却忽视了如何充分利用各系统拣选优势（人工拣选适合—单—品，机器人移动货架系统适合—单多品），以及SKU对存储空间的需求，而这正是大型网上超市实际选品运营中迫切需要解决的关键难题。

      本文针对“人—机”双拣选系统选品问题，考虑一单多品订单带来的商品关联复杂性以及数万种商品规模带来的解空间巨大等挑战性，基于缩减解空间的思想，提出一种基于关联网络的三阶段迭代搜索选品方法。该方法有两大突出特点：1）将商品关联网络划分成两个集合L（机器人移动货架区域存储商品的集合）、NL（人工拣选区域存储商品的集合），以最小化L和NL集合间连边关联，最大化机器人移动货架区域存储SKU的关联性为目标，通过提升机器人移动货架系统存储SKU间的关联并减少合流订单，使得双系统分别履行各自擅长的订单，可以有效解决有限存储空间下SKU关联强的选品难题，从而实现“人—机”双拣选系统的高效、低成本运行。2）该方法基于历史订单数据，按照“关联网络构建→关联网络转化（搜索树）→关联网络搜索（蒙特卡洛树搜索）”三阶段，可以巧妙地将海量关联商品的“人—机”双拣选系统选品难题转化为状态空间搜索问题，并且通过在关联网络搜索中，设计新的评估节点期望回报函数，可以高效地将商品网络划分为对应双拣选区域的商品集合方案。最后，利用企业的实际数据，验证本文方法的高效性和实用性，对仓库容量和迭代搜索次数进行灵敏度分析。本文方法可为“人—机”双拣选系统选品方案的生成提供科学、实用的决策支持，对企业提升双拣选系统的运行效率提供切实可行的指导意见。