The parallel AGV scheduling problem with battery constraints: A new formulation and a matheuristic approach

Nowadays, automated guided vehicles (AGVs) are frequently used in larger systems, known as AGV-based transportation systems, for the movement of goods and materials from one location to another. The de-sign of an efficient and effective AGV-based transportation system requires to address many tactical and operational issues. Among the others, the scheduling of transfer jobs on the AGVs represents one of the main operational issues that has to be solved to overcome delays in production and material handling processes. In this context, a significant research activity on AGV systems and on related scheduling prob-lems has been conducted in the last twenty years. However, most of the contributions neglected the issues related to the AGV battery depletion and recharge. Thus, in this work, we study the AGV schedul-ing problem with battery constraints ( ASP-BC ). It consists in determining the scheduling of transfer jobs and charging operations of a fleet of homogeneous AGVs such that the makespan of the handling pro-cess is minimized. The methodological contribution of our work is twofold. On one side, we propose an original mixed integer linear programming formulation based on the bottleneck generalized assignment problem. On the other side, we propose a three step matheuristic based on the sequential solution of the two subproblems arising from the natural decomposition of the ASP-BC and a local search heuristic. The proposed approaches have been tested and validated on simulated and real instances provided by a manufacturing company. The results show the effectiveness and the scalability of the proposed solution methods. & COPY; 2022 Elsevier B.V. All rights reserved.

Automated summary

Automated guided vehicles (AGVs) are widely used in AGV-based transportation systems for the movement of goods and materials. The scheduling of transfer jobs on AGVs is crucial to overcome delays in production and material handling processes. However, the issue of AGV battery depletion and recharge has been neglected in previous research. This study focuses on the AGV scheduling problem with battery constraints and proposes novel solution methods.