基于英式拍卖的RMFS货位指派研究

李秀，程广华，王雪菲，何茵楠

基于英式拍卖的RMFS货位指派研究

李秀，程广华*，王雪菲，何茵楠

（淮南师范学院 经济与管理学院，安徽 淮南 232038）

构建英式拍卖模型，以待指派商品品项（SKU）群的最低周转率为媒介，通过逐步提升最低周转率来实现待指派SKU与待指派区域货位数量的匹配。针对移动机器人拣货系统（RMFS）中的货位指派，提出基于英式拍卖机制的货位指派方法，提升仓库拣货效率。与随机指派相比，在不同仓库规模、订单规模、订单偏度的RMFS中采用英式拍卖货位指派机制，机器人行走路程下降比率在大型仓库中达30.17%，中型仓库的下降比率为27.31%，小型仓库的下降比率为24.13%。采用英式拍卖机制在RFMS中进行货位指派可大幅度提高工作效率。

RFMS；货位指派；英式拍卖；订单拣选

电子商务的迅猛发展、物流技术的提升使得人们获取商品的渠道更加宽广、方式更加多样。人们的需求也从大批量、小批次到小批量、大批次转变，这也要求物流必须从方法与技术双管齐下，双向提升。因此，催生一种新型的移动机器人拣货系统（Robotic Mobile Fulfillment System，RMFS），即“物至人”拣货系统。RMFS为一种智能仓储系统，主要由拣货机器人承担仓库入库、拣货、分拣等工作，极大地降低仓库中作业强度，还可降低失误率和提升工作效率。货位指派是货物进入仓库内的首要问题，研究合适的货位指派方法可以极大地缩短拣货时间、减少拣货路程，提升工作效率[1]，并能减少机器人小车的工作时间，降低仓库能耗。亚马逊、GAP等典型大型企业的RMFS都是采用随机货位指派机制。随机指派具有指派迅速、方法简单等优点，但也可能使得搜索目标商品（Stock Keeping Unit，SKU）的时间过长、延长拣货路径等缺点[2-3]。

拣货机器人拣货的速度、拣货时间以及总体作业成本通过采用合理的货位指派方法可有效解决[4]。Huang等[5]证明了货位指派方法的有效性，货位指派方法可有效提升RMFS对订单需求变化的应对能力，从而降低仓库成本。Weidinger等[6]为提升仓库中的拣货速率，提出了自适应编程的货位指派方法，并验证了其有效性。Roy等[7]采用两阶段随机模型，并使用拣货机器人存储分配制度，可有效应对不同订单需求条件下的货位指派方法。Xiang等[8]基于SKU相似模型提出一种启发式算法来解决订单处理问题。以上研究采用了多种分配制度提升拣货机器人的拣货速率，但拣货机器人在不同规模的仓库、不同的订单规模以及不同SKU订单偏度对拣货效率的影响没有纳入模型并进行求解。

经济学领域典型的资源分配制度之一为拍卖机制，常见的拍卖机制有英式拍卖、荷兰式拍卖和双向拍卖等。拍卖机制也逐渐引起了非经济学领域一些学者的关注，并证明了拍卖机制在其他领域的有效性。翁楚良等[9]基于计算机网络资源特点提出基于双向拍卖机制的网络资源分配方法，有效提升了分配效率。马俊等[10]研究了在不完全信息环境下采用合理拍卖机制来分析供应链的协调问题，证明了在拥有信息中介的二部合同拍卖机制下系统可以达到渠道协调。胡志刚等[11-12]提出了一种基于云环境下的组合双向拍卖定价模型，可有效提升供应商利润。邵嫄等[13]提出了基于双向拍卖的运输服务市场成交概率模型，实现运输服务市场双方（承运人和托运人）的收益最大化。赖明辉等[14]提出了基于迭代拍卖机制的多运输商整车运输合作模式，解决了在信息不完全的条件下，运输效率提升的问题。以上研究表明，拍卖机制在物流资源方面可取得有效成果。货位指派的本质是为将即将入库的SKU指派至合适的货位以方便订单SKU的拣选，徐翔斌等[15]采用荷兰式拍卖机制在RMFS中进行货位指派，但整个过程中只单独考虑待指派区域或待指派SKU的周转率，从而导致距拣货工作台较远的位置被指派到周转率较高的SKU，延长拣货时间，不利于拣货效率的提升。采用荷兰式拍卖与双向拍卖货位指派机制都能有效降低机器人小车拣货的行走距离，但是荷兰式拍卖与双向拍卖2种拍卖方式都有可能因为卖方减价策略不合理造成部分标的物流拍，从而导致在货位指派过程中有部分货位未被有效指派，增加机器小车的拣货距离。英式拍卖的拍卖过程属于买方逐步加价策略，无论竞拍人数与标的物数量是否对等，其拍卖结果都为有效结果，即所有标的物都会产生购买者。采用英式拍卖货位指派可解决拍卖过程中由于卖方减价策略不合理而造成部分货位不能得到有效指派的问题，降低机器人小车的拣货过程中的距离。

因此，在本研究中基于拍卖机制提出一种RFMS货物指派方法，并模拟不同仓库规模、不同订单规模、不同订单偏度3种不同因素的影响，验证英式拍卖机制在RFMS中货位指派的适用性。

1 英式拍卖货位指派机制的模型构建

1.1 问题描述

在RMFS中，从SKU进入到商品开始，大部分工作都由机器人小车完成。RMFS中的工作流程为：SKU进入至仓库中暂存区域，拣货工作人员扫描SKU与货架，再将SKU放置于货架之上，再由机器人小车运送至目标货位；当仓库接收到订单时，工作人员扫描订单后，由电脑发出指令；机器人小车接收到指令之后，依次将目标货架运送至拣货台，由工作人员扫描货物与相应的SKU，再放至储物篮；最后由拣货机器人将货架送回相应位置。作业中，机器人一次只运输一个货架。由此可知，货位指派可直接影响到后续拣货的过程，而货位指派方法则直接影响拣货的速率。

本文对单区仓库进行研究，每2排货架间有一条东西双向巷道，每10列货架之间有一每条南北双向巷道，具体排列方式如图1所示。

由图1可知，待入库SKU从东边进入仓库中，由工作人员放置于货架上，再由拣货机器人按相应指派方法将货架运送至目标货位。拣货工作台放置于仓库西侧，每20个货架为一个货架群，再由若干个货架群组成一个货架区，由西向东分为A、B、C、D等区域。按照位置的优劣性（即离出库区域的路程）可知，位置最优为A区，最差为D区。1台机器人小车每一次只能运送一个货架，而每一个货架只能由一台机器人小车运送。在运送货架时，机器人小车只能由巷道行驶，而没有运送货架时，则可从货架底部穿行。

本文在小（560货位）、中（900货位）、大（1 320货位）3种不同规模的仓库进行实验，采用英式拍卖机制在不同规模的仓库中货位指派之后，再进行订单拣选。

图1 仓库货架排列布置平面

1.2 模型建立

模型假设：仓库为单层平面仓库，机器人小车可以在行走时按照东、西、南、北随时转变方向，且在仓库中，每一排和每一列的货架数量都相同，且在运输过程中不会发生拥塞；拣货机器人一次只运送一个货架，一个货架由一个机器人运送。每一个货架中只存放一种SKU，且每一种SKU只存放于一个货架中。机器人的承重相同，且每一满载货架的重量不会超过拣货机器人承重；拣货机器载重时运行速度不变；实验中，忽略机器人抬起货架、工作人员拿放SKU以及货位指派的时间。

货位指派为将待指派的SKU指派至合适的货位来缩短拣选订单货物所需要行走的路程。机器人小车拣货过程中路程的目标函数为：

约束条件：

式中：T为机器人拣选完订单中所有SKU所需行走的总路程；为完成订单中所有SKU拣选需经过的巷道的数量；x为编号为号待拣选SKU在第号巷道内的第个货位，若该货位存在，则等于1，若不存在，则等于0；G为机器人拣选第号订单是否经需要过号巷道，如需要经过，则等于1，如不需要，则等于0；t、t为机器人扫描货架底部的条码和抬起货架所需要的时间。式（1）为实验总目标函数，表示为拣选完订单中所有SKU机器人所需行走的最短距离；式（2）为单一货架只存放一种SKU；式（3）为每一种SKU只存放于一个货架；式（4）为拣选订单中的SKU时，至少需要通过一条巷道；式（5）中为机器人行走的速度，L和N为经过号和号巷道的次数。

1.3 英式拍卖货位指派机制

英式拍卖为“升价”拍卖，即购买者依照加价幅度依次对标的物进行递增加价，当到达截拍时间时，标价最高的购买者将购得标的物。在英式拍卖过程中，卖家有设定保留价或不设定保留价2种选择，属于竞价拍卖，其具体流程如图2所示。

货位指派指将进入仓库的待指派SKU存放于待指派货位的过程，其过程可视为仓库中的资源分配问题。采用合理的货位指派机制可有效地降低对目标订单的拣选时间与行走距离[16]，有效提升拣货机器人在RFMS中的工作效率。拍卖机制是典型的资源分配方式，其中英式拍卖是拍卖机制中最简单的拍卖方式之一，因其操作简单有效被广泛使用。本文所采用的英式拍卖机制是一个离散型的拍卖过程。

英式拍卖的基本思想：首先计算RFMS中的周转率，各待指派区域相互独立（待指派区域、待指派SKU相互不受影响）。在整个过程中，英式拍卖中的卖方（ST）和买方（BT）分别为待指派区域和待指派SKU，而价格TR则用待指派SKU的周转率替代。实验先采用随机指派机制，再生成拣选订单，并使用机器人进行拣货，然后再采用英式拍卖货位指派机制进行货位指派，采用卖方（待指派区域）未保留价格（最低周转率）模式。随着卖方逐步加价，TR（SKU群中SKU最低周转率）升高至TR1，直至买方的价格与卖方价格相等（待指派SKU与待指派区域的数量相匹配），则将该SKU群指派至该区域，由拣货机器人完成指派工作。待指派SKU群的TR符合函数：

1）计算RMFS中待指派SKU的周转率。

2）将仓库中的个货位按S形进行排序，列货，分为个待指派区域。

3）将待指派SKU随机指派至相应货位。

4）按需求偏度（高、中、低）随机生成大、中、小（15SKU、10SKU、5SKU）不同规模的订单。

5）使用机器人拣选订单SKU，并计算行走的总路程长度。

6）再根据周转率对SKU进行重新指派。重新指派的具体过程如下：

①将待指派SKU按周转率分为个SKU群，其最低周转率为从小到大为1,2,…,n。

②编号M—M号为待指派货位，若高于n的SKU数量正好为待指派区域货位的数量，则将SKU指派至目标货位。

③如果高于n的SKU数量与待指派区域货位的数量不匹配，则以为价格增加幅度，将n提升至n1，提升n2直至n，此时高于n的SKU的数量正好与待指派区域货位数量相匹配，则将待指派货位指派至该区域。

④按步骤③对剩余待指派区域进行货位指派，直到指派完成。

7）等货位指派完成后，再采用机器人对步骤4）中的订单进行拣选，拣选完成后计算机器人行走路程，计为S。具体流程图如图3所示。

图3 英式拍卖货位指派机制流程

2 仿真实验

2.1 因子及参数

本文所设计的实验分析了在小型、中型、大型仓库中，采用英式拍卖机制进行货位指派，计算拣货机器人拣货小、中、大3种不同订单规模在高、中、低3种不同订单偏度的情况下，所需行走的路程，共产生27（3×3×3）种不同情况。在此实验参数下使用英式拍卖货位指派机制进行仿真实验，实验因素及水平如表1所示。

表1 实验因子及水平

Tab.1 Experimental factors and levels

2.2 结果对比

RFMS系统中在不同仓库规模、订单规模以及订单的需求偏度下，模拟英式拍卖机制和随机拍卖机制的货位指派方法的拣选效果。得到用随机货位指派机制与使用英式拍卖货位指派机制指派之后，拣选相同订单机器人行走路程的下降比率，如图4所示。

图4 货位指派之后距离下降比率

由图4可以看出英式拍卖货位指派机制在RMFS中的有效性。效果随着仓库规模的增大，呈现出递增的趋势，因而在大规模（1 320货位）的仓库中取得的效果最好，机器人行走的路程下降比率达到30.17%。在小型仓库（560货位）中，机器人行走的距离下降比率也超过了24%。采用英式拍卖机制进行货位指派之后，在不同订单需求偏度情况下，机器人拣选所需订单SKU行走的路程与随机指派机制条件下，行走路程下降比率如图5所示。从图5中可得出，若不考虑订单规模，采用英式拍卖机制指派后，相较随机指派机制，在大型仓库且订单偏度高的情况下，拣选相同订单时机器人行走路程下降了43.16%；当订单偏度较小时，指派后得到的效果适中，其行走路程下降比率为15.3%～19.30%；当订单需求偏度较大时，指派效果则是随着仓库规模的增大而增强。

图6为不同订单规模的情况下，使用英式拍卖货位指派机制与随机指派机制后，机器人拣选相同订单行走路程的下降比率。可以看出，在大型仓库中且订单规模大的情况下，指派效果最好，工作行走路程下降了32.16%；订单规模为中等的情况下，在中型仓库中的指派效果最好；订单规模较小的情况下，指派效果较弱，工作行走路程下降比率为21.54。

图5 不同需求偏度调整后拣货工作行走距离下降比率

图6 不同订单规模指派后拣货行走距离下降比率

图7则是同时考虑了仓库规模、订单规模、订单需求偏度，采用英式拍卖货位指派机制与随机指派机制后拣选相同订单行走路程的下降比率。从图7中可以看出在RMFS中采用英式拍卖机制的有效性。在仓库规模不同的情况下，订单规模与需求偏度对机器人拣货行走路程长度有不同的影响。订单需求偏度较小时，各规模仓库与订单的指派效果较接近，路程比率一般为13.07%～21.97%；而订单SKU需求偏度较高时，指派效果波动较明显，在大型仓库中，路程下降比率达到36.72%以上。

图7 指派后路程下降比率

综合来看，英式拍卖货位指派机制在RFMS中具有有效性，采用该指派机制后，使用机器人对仓库进行拣货可有效提升拣货机器在RFMS中的工作效率。

3 结语

研究英式拍货位指派机制在不同规模RFMS中的应用。结果表明，英式拍卖货位指派机制在RFMS中是一种有效的货位指派方法。相较于随机货位指派，采用英式拍卖货位指派机制在大、中、小3种不同规模的仓库中，机器人的拣货路程长度下降的比率分别达到了30.17%、27.31%、24.13%。对于不同需求偏度，当需求偏度较高时，在大型仓库中指派后距离下降比率为43.16%；当需求度中等时，在中型仓库中指派后距离下降比率为30.17%；当需求偏度较低时，在小型仓库中指派后距离下降比率为19.30%。对于不同订单规模，当订单规模较大时，在大型仓库中指派后距离下降比率为32.16%；当订单规模中等时，在中型仓库中指派后距离下降比率为29.62%；当订单规模较小时，在大型规模仓库中指派后距离下降比率为30.79%。数值分析显示，对于不同仓库规模、订单规模、订单需求偏度，英式拍卖货位指派机制都展示出良好的指派效果，尤其对大型仓库、较大订单规模、较高需求偏度的指派效果最佳。英式拍卖货位指派机制可以缩短订单拣选路程、降低拣货时间、提升工作效率，对零售电子商务仓库的货位指派和订单拣选具有一定的参考价值和实际应用意义。

[1] 周丽, 朱杰, 郭键. 分类存储返回型与S型拣选路径随机模型的比较研究[J]. 系统科学与数学, 2011, 31(8): 921-931.

ZHOU Li, ZHU Jie, GUO Jian. Comparative Research on Stochastic Model of sorted-Storage return-Type and s-Type Order Picking Route[J]. Journal of Systems Science and Mathematical Sciences, 2011, 31(8): 921-931.

[2] LAMBALLAIS T, ROY D, DE KOSTER R. Estimating Performance in a Robotic Mobile Fulfillment System[J]. European Journal of Operational Research, 2016, 256(3): 976-990.

[3] 徐翔斌, 李秀. 固定路径下多阶段货位调整研究[J]. 工业工程与管理, 2017, 22(5): 24-31.

XU Xiang-bin, LI Xiu. Research on Route-Based Multi-Staged Storage Location Adjustment[J]. Industrial Engineering and Management, 2017, 22(5): 24-31.

[4] 徐翔斌, 马中强. RMFS订单拣选系统动态货位再指派研究[J]. 计算机集成制造系统, 2021, 27(4): 1146-1154.

XU Xiang-bin, MA Zhong-qiang. Dynamic Location Reassignment of RMFS Order Picking System[J]. Computer Integrated Manufacturing Systems, 2021, 27(4): 1146-1154.

[5] HUANG G Q, CHEN M, PAN J. Robotics in Ecommerce Logistics[J]. HKIE Transactions, 2015, 22(2): 1-10.

[6] WEIDINGER F, BOYSEN N, BRISKORN D. Storage Assignment with Rack-Moving Mobile Robots in KIVA Warehouses[J]. Transportation Science, 2018, 52(6): 1479-1495.

[7] ROY D, NIGAM S, KOSTER R, et al. Robot-Storage Zone Assignment Strategies in Mobile Fulfillment Systems[J]. Transportation Research Part E Logistics and Transportation Review, 2019, 122: 119-142.

[8] XIANG Xi, LIU Chang-chun, MIAO Li-xin. Storage Assignment and Order Batching Problem in Kiva Mobile Fulfilment System[J]. Engineering Optimization, 2018(4): 1-22.

[9] 翁楚良, 陆鑫达. 一种基于双向拍卖机制的计算网格资源分配方法[J]. 计算机学报, 2006, 29(6): 1004-1009.

WENG Chu-liang, LU Xin-da. A Double Auction Method for Resource Allocation on Computational Grids[J]. Chinese Journal of Computers, 2006, 29(6): 1004-1009.

[10] 马俊, 张杰, 汪寿阳. 应用拍卖机制协调供应链[J]. 管理科学学报, 2009, 12(5): 1-9.

MA Jun, ZHANG Jie, WANG Shou-yang. Coordinate Supply Chain via Auction Mechanisms[J]. Journal of Management Sciences in China, 2009, 12(5): 1-9.

[11] 胡志刚, 刘艳. 云环境下基于组合双向拍卖的动态资源定价[J]. 计算机工程, 2012, 38(8): 19-21.

HU Zhi-gang, LIU Yan. Dynamic Resource Pricing Based on Combinatorial Double Auction in Cloud Environment[J]. Computer Engineering, 2012, 38(8): 19-21.

[12] 毛莺池, 郝帅, 平萍, 等. 基于组合双向拍卖的云资源调度方法[J]. 计算机应用, 2019, 39(1): 1-7.

MAO Ying-chi, HAO Shuai, PING Ping, et al. Cloud Resource Scheduling Method Based on Combinatorial Double Auction[J]. Journal of Computer Applications, 2019, 39(1): 1-7.

[13] 邵嫄, 索馨. 基于双向拍卖的运输服务市场成交概率模型研究[J]. 价值工程, 2020, 39(21): 89-91.

SHAO Yuan, SUO Xin. Transaction Probability Model Based on Double Auction in Transportation Service Market[J]. Value Engineering, 2020, 39(21): 89-91.

[14] 赖明辉, 薛巍立, 田歆, 等. 整车运输协作问题迭代拍卖机制设计[J]. 系统工程理论与实践, 2018, 38(12): 3174-3186.

LAI Ming-hui, XUE Wei-li, TIAN Xin, et al. Iterative Auction Design for Truckload Collaborative Transportation[J]. Systems Engineering—Theory & Practice, 2018, 38(12): 3174-3186.

[15] 徐翔斌, 何世奇, 李秀. 基于荷兰式拍卖机制的RMFS货位指派研究[J]. 包装工程, 2020, 41(1): 128-133.

XU Xiang-bin, HE Shi-qi, LI Xiu. RMFS Storage Location Assignment Based on Dutch Auction[J]. Packaging Engineering, 2020, 41(1): 128-133.

[16] 何茵楠, 王帮俊, 魏宇茜, 等. 碳减排下的汽车零部件循环取货路径优化研究[J]. 重庆工商大学学报(自然科学版), 2021, 38(3): 71-78.

HE Yin-nan, WANG Bang-jun, WEI Yu-xi, et al. Research on the Optimization of Milk-Run Route of Automobile Parts Based on Carbon-Emission Reduction[J]. Journal of Chongqing Technology and Business University (Natural Science Edition), 2021, 38(3): 71-78.

RFMS Storage Location Assignment Method Based on British Auction

LI Xiu, CHENG Guang-hua*, WANG Xue-fei, HE Yin-nan

(School of Economics and Management, Huainan Normal University, Anhui Huainan 232038, China)

The work aims to construct a British auction model to match the number of Stock Keeping Unit (SKU) to be assigned with the number of storage locations in the area to be assigned by gradually increasing the minimum turnover rate of the SKU group to be assigned as a medium. The storage location assignment method based on British auction was proposed to improve the picking efficiency in the warehouse for the storage location assignment in Robotic Mobile Fulfillment System (RMFS). Compared with the random assignment model, when the storage location assignment based on British auction was adopted in RMFS with different warehouse scales, order sizes, and order biases, the travel distance reduction rate of robot reached 30.17% in large warehouses, 27.31% in medium-sized warehouses, and 24.13% in small warehouses. The use of the British auction mechanism in RFMS for storage location assignment can significantly improve efficiency.

RFMS; storage location assignment; British auction; order picking

U291.5+5

A

1001-3563(2023)17-0160-07

10.19554/j.cnki.1001-3563.2023.17.019

2022-06-20

江西省自然科学基金资助项目（2018BAB201010）；安徽省高等学校省级质量工程（2020jyxm1736）；物流工程卓越物流师教育培养计划（2018zygc041）；淮南市指导性科技计划项目（2021136）；淮南师范学院校级科研项目（2021XJYB009，2020XJYB028）；淮南师范学院校级教研项目（2020hsjyxm34）

责任编辑：曾钰婵