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

Yantong Li, Bo Ren, Xin Wen and Sai-Ho Chung

International Journal of Production Research, 2025, vol. 63, issue 15, 5749-5781

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.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2025.2462670 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tprsxx:v:63:y:2025:i:15:p:5749-5781

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2025.2462670

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().