主管：中国科学院
主办：中国优选法统筹法与经济数学研究会
　　　中国科学院科技战略咨询研究院
中国管理科学

中国管理科学 ›› 2022, Vol. 30 ›› Issue (1): 124-135.doi: 10.16381/j.cnki.issn1003-207x.2019.1266

• 论文 • 上一篇    下一篇

无人仓系统储位分配问题的优化模型与算法

李珍萍1, 贾顺顺1,2, 卜晓奇1, 吴凌云3,4, 张国维3,4,5   

  1. 1.北京物资学院信息学院，北京101149； 2.首都经济贸易大学国际经济管理学院，北京100070；3. 中国科学院数学与系统科学研究院应用数学研究所管理决策与信息系统重点实验室，北京100190；4.中国科学院大学数学科学学院，北京100049； 5.华北电力大学经济与管理学院，北京102206
  • 收稿日期:2019-08-25 修回日期:2020-01-21 出版日期:2022-01-20 发布日期:2022-01-29
  • 通讯作者: 吴凌云(1975-)，男(汉族)，福建屏南人，中国科学院数学与系统科学研究院，研究员，博士，研究方向：组合优化、智能算法，Email:lywu@amss.ac.cn. E-mail:lywu@amss.ac.cn
  • 基金资助:
    国家自然科学基金资助项目(71771028)；北京市自然科学基金资助项目(9212004，Z180005)；2018年北京市属高校高水平创新团队支持计划项目(IDHT20180510)；北京市科技创新服务能力建设-高精尖学科建设计划资助项目(2019);北京市智能物流系统协同创新中心开放课题(BILSCIC-2019KF-18)

The Optimization Model and Algorithm for Storage Location Assignment Problem in Unmanned Warehouse System

LI Zhen-ping1, JIA Shun-shun1,2, BU Xiao-qi1, WU Ling-yun3,4, ZHANG Guo-wei3,4,5   

  1. 1. School of Information, Beijing Wuzi University, Beijing 101149, China; 2. International School of Economics and Management,Capital University of Economics and Business Beijing, 100070, China;3. Key Laboratory of Management Decision and Information Systems, Institute of Applied Mathematics, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China;4. School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China;5. School of Economics and Management, North China Electric Power University, Beijing 102206, China
  • Received:2019-08-25 Revised:2020-01-21 Online:2022-01-20 Published:2022-01-29
  • Contact: 吴凌云 E-mail:lywu@amss.ac.cn

PDF (PC)

482

摘要： 考虑到无人仓系统补货阶段货架上只有部分空余储位的特点，研究了补货商品储位分配问题的优化模型与算法。以同一货架上存放的商品之间关联度之和最大化为目标建立了混合整数规划模型；结合贪婪算法和邻域搜索算法设计了求解模型的两阶段方法。第一阶段利用贪婪算法求初始可行解；第二阶段利用邻域搜索算法对初始可行解进行优化。利用一个具体算例验证了邻域搜索算法的优化效果，结果显示，通过邻域搜索算法对初始可行解的优化，可以使目标函数值至少提升27%。进一步利用多个小规模算例分析了两阶段算法的近似比和求解速度，验证了算法的快速有效性。本文的研究结果不仅解决了货架初始状态非空情况下的储位分配问题，同样适合解决货架初始状态为空的情况，因此更加符合实际场景，可以作为无人仓管理信息系统的核心模型和算法。

关键词: 无人仓；储位分配；混合整数规划；贪婪算法；邻域搜索

Abstract: Unmanned warehouse is an automatic storage system appeared in recent years. The storage allocation strategy is one of the main factors affecting the efficiency of unmanned warehouse system. Based on the scene that there might be only part of the storage locations empty in the replenishment stage of the unmanned warehouse system, the optimization model and algorithm for storage location assignment problem of unmanned warehouse system is studied. A mixed integer programming model of the storage location assignment problem is formulated to maximize the sum of the correlation degrees among items stored on the same shelves. Based on the greedy algorithm and neighborhood search algorithm, a two-stage algorithm is designed for solving the model. In the first stage, a greedy algorithm is used to obtain an initial feasible solution, in the second stage, the neighborhood search heuristic algorithm is designed to optimize the initial feasible solution. An computer generated example is used to verify the optimization effect of neighborhood search algorithm, the results show that the objective value of solution being optimized by neighborhood search algorithm is increase by at least 27%. Several small-scale examples are used to analyze the approximation ratio and running speed of the two stage heuristic algorithm, which verifies the fast and effective of the algorithm. The model and algorithm of this paper not only solve the storage allocation problem with parts of the storage locations being empty on the shelves, but also can be used to solve the problem with all the storage locations being empty on the shelves. So the application of this method is broader, which can be used as the core model and algorithm for designing the unmanned warehouse management information system.

Key words: unmanned warehouse; storage location assignment; mixed integer programming; greedy algorithm; neighborhood search

中图分类号: