Smart Automated Guided Vehicle scheduling with flexible battery management: A new formulation and an exact approach

Automated Guided Vehicles (AGVs) have gained widespread application within modern smart transportation or industrial systems. The AGV scheduling problem, particularly considering battery management, holds a pivotal role in enhancing system efficiency, cost-effectiveness, and safety. Existing research on the AGV scheduling problem predominantly assumes fixed charging or battery swapping strategies, wherein the duration of each energy replenishment operation remains constant and predetermined. However, allowing AGVs to undergo partial charging durations offers increased flexibility and potential efficiency gains by minimizing downtime. The incorporation of flexible charging introduces additional complexity to the AGV scheduling problem, as it necessitates determining the duration for each charging operation. In this study, we investigate an AGV scheduling problem with flexible charging and charging setup time (ASP-FLC-ST). Initially, we propose a novel mixed-integer linear programming model tailored to address the ASP-FLC-ST. Subsequently, we conduct a structural analysis of the problem, demonstrating its strong NP-hardness and deriving a valid lower bound. To tackle the complexity of the ASP-FLC-ST, we develop a customized exact logic-based Benders decomposition algorithm (LBBD) and introduce an “alternating cut” generation scheme to enhance its performance. Computational experiments conducted on 360 random instances of the ASP-FLC-ST showcase the superiority of our approach over state-of-the-art commercial solvers. Moreover, the devised LBBD method effectively addresses benchmark instances of a reduced counterpart, yielding 173 new best solutions and establishing optimality in 161 instances with open solutions.