Time-space network model and MILP formulation of the conflict-free routing problem of a capacitated AGV system

• DOI: 10.1016/j.cie.2020.106270
• Publication Date: 2020-01-08T19:40:24Z
• Authors: Keisuke Murakami
• Keywords: 0211 other engineering and technologies; 02 engineering and technology

Abstract Automated guided vehicles (AGVs) are used to transport materials in flexible manufacturing systems. This paper addresses an AGV routing problem known as the dispatch and conflict-free routing problem of a capacitated AGV system (DCFRPC). In the problem, we consider the additional constraints of collision avoidance, AGV capacities, and capacities of the machine buffers. We use a time-space network (TSN) to model the DCFRPC and formulate it as a mixed-integer linear programming (MILP) problem. In the TSN, we consider the flows of the AGVs and materials separately and then synchronize these flows considering the constraints in the formulation. This approach allows us to formulate the DCFRPC as a MILP problem. The experimental results demonstrate that our proposed approach can find optimal solutions to the majority of instances examined in a previous study.