In the wake of the introduction of autonomous robots (ARs), modern material-handling systems such as last-mile delivery and production logistics face a variety of new optimization problems. For example, with the rise of delivery drones, new scheduling systems for unmanned aerial vehicles (UAVs), commonly known as drones, have grown increasingly important in order to enable adaptation to various demands and to enhance efficiency. In the case of ground transportation, autonomous delivery robots have attracted significant public and private interest. In addition to these last-mile delivery, utilization of autonomous mobile robots (AMRs) in production logistics has grown quickly, owing especially to their scalability and versatility compared with automated guided vehicles (AGVs).
Traditionally, manned vehicles such as trucks and forklifts have been most widely used in last-mile delivery. In the case of material handling in factories and warehouses, AGVs guided by tape, wire, and magnetic tracks have been utilized in spite of their high investment costs. While those types of vehicles currently have a huge role in logistics, utilization of ARs is growing quickly as more and more companies consider semi-autonomous or fully autonomous vehicles offering scalability and versatility as well as lower costs.
However, many hurdles such as the computational complexity of optimization problems for scheduling and routing must be cleared in order to make the best use of ARs. Those optimization problems can be classified into three sub-problems: path finding, vehicle routing, and conflict resolution. The goal of the path finding problem is to find the best path having the minimum traveling time between two locations. In the case of the vehicle routing problem, the objective is to determine the best allocation of pickup and delivery operations with consideration of the paths calculated in the path finding problem. Finally, in terms of conflict resolution, the main purpose is to minimise collisions or delays based on the vehicle routing and path finding solutions.
All of these sub-problems are not independent, but rather are closely related to each other. For example, in order to find the best path of an AR, the required distance between two locations as well as the routes of the other vehicles must be considered. Also, the expected delivery time largely depends on delays caused by conflicts between ARs or other vehicles. Thus, a comprehensive framework for scheduling and routing of ARs is absolute necessary in order to tackle computational complexity and inherent interdependencies.