An adaptive large neighborhood search method for the AGV scheduling problem with a limited number of chargers.

International Journal of Production Research. Feb2025, p1-33. 33p. 13 Illustrations.

Automated guided vehicles (AGVs) are widely used in various fields to fulfill the transportation demands of factories or workshops due to their intelligence, flexibility, and efficiency. Scheduling multiple AGVs in the operational practice under these scenarios is challenging, where charging operations must be jointly optimised with the task processing process. Most studies on the AGV scheduling problem assume that the charging station can simultaneously charge an unlimited number of AGVs, where each AGV must be fully charged upon each charging operation. We investigate a new AGV scheduling problem with a limited number of chargers and a flexible charging strategy, denoted as ASP-LC-FCS. We first formulate the problem as a mixed-integer linear program (MILP) and show that it is strongly NP-hard. We then derive a valid lower bound. Considering the NP-hardness of the problem, we then develop a tailored adaptive large neighbourhood search (ALNS) algorithm based on the problem structure. The ALNS employs a matheuristic to generate initial feasible solutions, designs problem-specific destroy and repair operators, and innovatively uses a local search mechanism to improve the solution during each iteration. Computational experiments on 729 randomly generated instances demonstrate the good performance of the proposed ALNS, which significantly outperforms the state-of-the-art commercial solver CPLEX and an adapted artificial bee colony algorithm. Besides, we apply the proposed ALNS method to solve a real industrial case to provide practical solutions and managerial insights. [ABSTRACT FROM AUTHOR]

*Bees algorithm, Mixed integer linear programming, Automated guided vehicle systems, NP-hard problems, Neighborhoods

Copyright of International Journal of Production Research is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)