Scheduling heterogeneous multi-load AGVs with battery constraints. (December 2021)

• Record Type: Journal Article
• Authors: Dang, Quang-Vinh; Singh, Nitish; Adan, Ivo; Martagan, Tugce; van de Sande, Dirk
• Is Part Of: Computers & operations research. Volume 136(2021)
• Publication Date: 2021-12
• Subjects: Scheduling -- Multi-load automated guided vehicles -- Adaptive large neighborhood search -- Mixed integer linear programming; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105517
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: Recent trends towards larger and more complex systems necessitate the use of heterogeneous and flexible automated guided vehicles (AGVs) to fulfill the transport demand within a factory. To operate the fleet of AGVs efficiently, it is also important to consider their limited battery capacity. In this context, we tackle the problem of scheduling transport requests on multi-load and multi-ability AGVs with battery management. Each AGV can carry more than one load at a time and have specific capabilities such as lift loads, tow loads, or handle loads with a mounted robot arm. Each request consists of a pickup and a delivery task associated with an origin, a destination, a soft time window, and a priority. Each transport request may also require different AGV capabilities, and the AGV batteries can be recharged partially under consideration of a critical battery threshold. The decisions involve assigning transport and charging requests to AGVs, sequencing these requests, and determining the arrival times and charging duration. A mixed-integer linear programming model is formulated. A hybrid adaptive large neighborhood search with an integrated local search method is proposed to find a feasible schedule with the aim to minimize the tardiness costs of requests and travel costs of AGVs. We illustrate the efficacy of the hybrid algorithm with an industry case study using real-world data. The computational results reveal a 20%–50% cost reduction in current practice by using our hybrid algorithm, and around 50% cost reduction with respect to a single-load AGV scheduling approach proposed in the literature. Highlights: We study the scheduling of heterogeneous multi-load AGVs with battery constraints. We propose a hybrid algorithm based on adaptive large neighborhood search. We provide data for an industry case study used in the numerical experiments. The algorithm yields about 20%–50% cost reduction with respect to current practice.