Time-space network model and MILP formulation of the conflict-free routing problem of a capacitated AGV system. (March 2020)

• Record Type: Journal Article
• Authors: Murakami, Keisuke
• Is Part Of: Computers & industrial engineering. Volume 141(2020)
• Publication Date: 2020-03
• Subjects: AGV system -- Optimization -- Time-space network -- Mixed-integer linear programming; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2020.106270
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We propose a new approach for the dispatch and conflict-free routing problem of a capacitated AGV system (DCFRPC). The DCFRPC is expressed by a time-space network and formulated as a mixed-integer linear programming (MILP) problem. We also consider the splitting and merging of some materials (tasks) in the DCFRPC. A valid inequality is added into our MILP formulation to shorten the computation time. Our model and formulation can obtain optimal solutions to most of the instances in a previous study. 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.