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

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

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

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.