工业工程

工业工程 ›› 2022, Vol. 25 ›› Issue (4): 80-90.doi: 10.3969/j.issn.1007-7375.2022.04.010

• 专题论述 • 上一篇    下一篇

基于有向图强连通改进变邻域搜索算法的AGV单向导向路径网络设计

廖勇1,2, 陈庆新1, 毛宁1, 张惠煜1   

  1. 1. 广东工业大学 广东省计算机集成制造重点实验室，广东 广州 510006;
    2. 湘南学院物理与电子电气工程学院，湖南 郴州，423000
  • 收稿日期:2021-01-20 发布日期:2022-08-30
  • 通讯作者: 张惠煜(1989—)，男，广东省人，讲师，博士，主要研究方向为制造系统设计与优化、系统仿真技术等。E-mail: zhanghuiyu@gdut.edu.cn E-mail:zhanghuiyu@gdut.edu.cn
  • 作者简介:廖勇(1990—)，男，湖南省人，博士研究生，主要研究方向为制造系统设计与优化等
  • 基金资助:
    国家自然科学基金资助项目(51775120, 61973089, 51805096)；广东省自然科学基金资助项目(2018A030313477, 2022A1515011165, 2022A1515011175)

A Refined Variable Neighborhood Search Algorithm for Automated Guided Vehicle Flow Path Design Based on the Theory of Strongly Connected Digraph

LIAO Yong1,2, CHEN Qingxin1, MAO Ning1, ZHANG Huiyu1   

  1. 1. Key Laboratory of Computer Integrated Manufacturing System of Guangdong Province,Guangdong University of Technology, Guangzhou 510006, China;
    2. School of Physics, Electronics and Electrical Engineering, Xiangnan University, Chenzhou, 423000, China
  • Received:2021-01-20 Published:2022-08-30

RichHTML

14

PDF

3776

摘要： 为最小化物料搬运成本，结合有向图强连通性理论，提出一种改进变邻域搜索算法。首先，以最小化AGV的运载和空载成本为目标，建立相应的数学规划模型。接着，给出一种初始解生成方法，并构建目标函数计算的网络流模型。然后，为提高局部搜索能力，以有向图强连通性中反转路、反转圈保持强连通性为基础，提出3种邻域结构生成方法，以保证邻域解搜索过程中解的可行性，提高求解效率和质量。最后，针对6个基准案例，运用算法求解，并将其与其他多种启发式算法进行比较。实验结果表明，对于中小规模问题案例，算法求得案例的最优解；对于两个大规模案例，算法求得新的最好解，验证了提出算法的有效性。

关键词: 自动化导航小车, 导向路径网络设计, 改进变邻域搜索算法, 有向图强连通性质

Abstract: The flow path network for automated guided vehicle (AGV) is an important part for the layout design of material handling system. The AGV flow path network determines shop floor logistics cost by setting the routing and distances of material transportation. A refined variable neighborhood search (VNS) algorithm for AGV flow path design is proposed using the strongly connected theory of digraph. The research is conducted in the following four steps: 1) a mathematical model is established with the optimization objective to minimize the loading costs and no-loading loss for AGV; 2) a new initial solution generation method is proposed, and a network flow model is constructed to calculate objective function of solution; 3) three neighborhood structure generation methods are proposed to enhance the local search ability, and feasible solutions can be ensured in the local search within neighborhood, which in turn improve the efficiency and quality of solution; 4) six AGV flow path design instances are used to make comparisons between the new proposed VNS algorithm and the other heuristic algorithms. The experimental results show that the refined VNS can obtain optimal solutions in small and medium scale instances, and better AGV flow path design schemes can be obtained by the new proposed algorithm in large scale instances. The outcomes reveal the effectiveness of the new proposed VNS algorithm.

Key words: automatic guided vehicle(AGV), flow path design, refined variable neighborhood search algorithm, strongly connected theory of digraph

中图分类号: