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 design 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 problems 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 scheduling 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 process 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.