Exact and heuristic solution approaches for the multi-objective AGV scheduling problem with battery constraints
Maurizio Boccia, Andrea Mancuso, Adriano Masone, Teresa Murino, Claudio Sterle
Abstract
Automated Guided Vehicles (AGVs) are self-driving vehicles used for transporting goods and materials throughout different areas, such as shipping and receiving areas, storage facilities, and workstations. The popularity of AGVs has grown rapidly due to their many benefits, including flexibility in processes, efficient use of space, product safety, and computer integration and control. The design and management of AGV-based systems present various tactical decisions, such as fleet sizing and flow path design, as well as operational decisions such as dispatching, routing, and scheduling. In this study, we focus on a scheduling problem faced by a manufacturing company that utilizes AGVs subject to battery constraints for the horizontal movement of materials. Unlike previous studies, we investigate a Multi-objective AGV scheduling problem where both the AGV fleet size and the makespan need to be minimized. Additionally, AGV charging time depends on battery depletion. To support the company decision-making system, we propose a Mixed Integer Linear Programming formulation and a genetic algorithm. We have tested and validated our proposed methods using real-world instances provided by a manufacturing company. The results show the efficacy and the scalability of the proposed solution methods.