运筹与管理 ›› 2019, Vol. 28 ›› Issue (8): 86-92.DOI: 10.12005/orms.2019.0178

• 理论分析与方法探讨 • 上一篇    下一篇

基于聚类和动态规划的组合路径策略

冯爱兰1, 张小青1, 孔继利2   

  1. 1.北京科技大学 机械工程学院物流工程系,北京 100083;
    2.北京邮电大学 现代邮政学院,北京 100876
  • 收稿日期:2018-01-24 出版日期:2019-08-25
  • 作者简介:冯爱兰(1963-),副教授,研究方向:物流系统分析与优化、物流系统决策方法等;张小青(1992-),河北邢台人,硕士研究生,主要研究方向为拣货区拣货路径规划;孔继利(1982-),副教授,研究方向:复杂物流系统规划与设计、智能调度等。
  • 基金资助:
    国家自然科学基金资助项目(71772010):面向复杂产品研制联盟的云制造资源配置与调度研究

Combined Strategy Based on Clustering and Dynamic Programmingfor Picking Routing in warehouse

FENG Ai-lan1, ZHANG Xiao-qing1, KONG Ji-li2   

  1. 1.University of Science and Technology Beijing, Beijing 100083, China;
    2.School of Modern Post, Beijing University of Posts and Telecommunications, Beijing 100876, China
  • Received:2018-01-24 Online:2019-08-25

摘要: 为提高电商仓库的拣货作业效率,本文提出了基于聚类和动态规划的组合路径策略,实现了生成路径消耗时间和路径长度之间的平衡,并将这一策略成功地应用到多区型仓库。该策略分四步:首先,根据待拣储位分布特征,运用聚类分析法对其进行分类;然后,以各类的首末储位作为节点,运用动态规划法对已得分类进行排序,得到相应的类序;其次,得到各类内部路径;最后,依次拣取待拣商品,并返回出发点完成拣货作业。在提出新的路径策略后,通过仿真方法将新策略与三种传统路径策略(穿越策略、最大间隙策略和混合策略)和一种优质算法(蚁群算法)进行了对比分析,结果表明:该策略具备良好的适用性和实用性。

关键词: 拣货路径, 聚类分析, 动态规划

Abstract: In order to improve the efficiency of picking, this paper puts forward a new guidance strategy based on clustering and dynamic Programming for the picking routing in multi-block warehouse, which achieves the balance of the time for generating path and the length of path, and applies it to multi-block warehouse successfully. The strategy can be divided into four steps: Firstly, classify the picking bits by cluster analysis. Then, take the first and last points of each class as nodes, and use the dynamic programming method to sort the obtained classifications to get the corresponding class order. Next, determine the internal routing per class. Finally, pick the items in turn and get the picking routing length. After presenting the new routing strategy, this paper compares the new strategy with the previous heuristic strategies such as S-shape, Largest Gap, and Combined and ACO algorithm through simulation, getting the result: The newly proposed routing strategy has a good feasibility, applicability and practicability.

Key words: picking routing, cluster analysis, dynamic programming

中图分类号: