Abstract
The AGV Scheduling Problem with Battery Constraints (ASP-BC) has recently attracted attention in the context of automated warehouses, where automated guided vehicles are required to execute transportation tasks under limited battery capacity while coordinating charging operations. Existing approaches typically focus on specific problem variants, considering either fixed or flexible charging policies. In this paper, we propose a Multi-Neighborhood Search (MNS) metaheuristic for solving both variants of the ASP-BC. The proposed approach is based on an implicit solution representation, a fast decoding procedure, and a set of local search neighborhoods. Extensive computational experiments on benchmark and newly generated instances show that the proposed MNS can find optimal or near-optimal solutions in very short computational times, significantly outperforming existing approaches in scalability and making it particularly well suited to real-world cases, where instance sizes can be very large, and decisions must be taken under tight time constraints. Finally, we provide managerial insights into the impact of charging policies on system performance, identifying scenarios in which simpler fixed policies can be effectively adopted and others in which flexible charging becomes essential.