Scheduling heterogeneous multi-load AGVs with battery constraints

摘要

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.