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