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

Abstract

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.