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

Maurizio Boccia, Adriano Masone, Claudio Sterle and Teresa Murino

European Journal of Operational Research, 2023, vol. 307, issue 2, 590-603

Abstract: 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.

Keywords: Assignment; Scheduling; AGV; Battery constraints; MILP; Matheuristic (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722008116
Full text for ScienceDirect subscribers only

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:eee:ejores:v:307:y:2023:i:2:p:590-603

DOI: 10.1016/j.ejor.2022.10.023

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().