Time Windows Based Dynamic Routing in Multi-AGV Systems

This paper presents a dynamic routing method for supervisory control of multiple automated guided vehicles (AGVs) that are traveling within a layout of a given warehouse. In dynamic routing a calculated path particularly depends on the number of currently active AGVs' missions and their priorities. In order to solve the shortest path problem dynamically, the proposed routing method uses time windows in a vector form. For each mission requested by the supervisor, predefined candidate paths are checked if they are feasible. The feasibility of a particular path is evaluated by insertion of appropriate time windows and by performing the windows overlapping tests. The use of time windows makes the algorithm apt for other scheduling and routing problems. Presented simulation results demonstrate efficiency of the proposed dynamic routing. The proposed method has been successfully implemented in the industrial environment in a form of a multiple AGV control system. Note To Practitioners-The automated warehouses are the facilities which can be equipped with stationary and mobile robotic sections (e. g. palletization workcells and unmanned forklifts, respectively). The goals, such as the maximal production throughput, efficient utilization of all robotic subsystems and collision avoidance with accommodation to dynamic changes within the manufacturing process itself have been achieved by designing and implementing a supervisory controller whose main characteristics are the ability of dynamic routing and scheduling in accordance with the current status of a given shop floor layout. The maximal throughput is provided by applying a shortest path algorithm, while potential conflicts and deadlocks are resolved by using the time windows insertion and time windows overlapping check algorithms. Because of the safety reasons, the proposed supervisory controller is somewhat restrictive, allowing only one vehicle to reside at one arc at the time. The described multi-AGV control system was successfully installed and put in operation at several European factories.