Suboptimal and conflict-free control of a fleet of AGVs to serve online requests

In this paper we propose a centralized control method for routing and scheduling a fleet of autonomously guided vehicles that serves online transportation requests. Our method maintains a central schedule, which is revised each time a vehicle finishes its current transportation task or a new transportation request arrives. The main benefit of the central schedule is that it ensures provably conflict-free control of a large fleet of vehicles on almost any layout, and permits optimization taking all the vehicle routes and schedules into account at the same time. We pay special attention to parking vehicles which may block the way of the moving vehicles, and our method inserts pull-off routes for them. The schedules are improved by various strategies, such as reducing the delays by swapping the order of the vehicles crossing the same lane, or elimination of loops in the vehicle routes created by pull-offs. We demonstrate the capabilities of our method by a series of computational tests, in which we also compare our mechanism to a recent conflict-free centralized method which is also designed for handling online requests.