Concurrent and Distributed Shortest-Path Searches in Multiagent-Based Transport Systems

The Fourth Industrial Revolution and the consequent integration of the Internet of Things and Services into industrial processes increase the requirements of transport processes. Customer demanding same-day deliveries, shorter transit-times, individual qualities of shipments, and higher amounts of small size orders raise the complexity and dynamics in logistics. In these highly dynamic environments, multiagent systems (MAS) and multiagent-based simulation (MASB) offer a suitable approach to handle the complexity and to provide the required flexibility, robustness, as well as customized behavior. This article focuses on the impact and the relevance of shortest-path queries in MAS and MABS. It compares the application of state-of-the-art algorithms and investigates different modeling approaches for efficient and concurrent shortest-path searches. The results prove that the application of a highly efficient algorithm such as hub labeling with contraction hierarchies is an essential key component in the agent-based control of dynamic transport processes. Moreover, the results reveal that choosing a modeling approach which slightly restricts the agents’ autonomy increases significantly the runtime performance without losing the advantages of multiagent systems. This allows for applying MAS to solve large scale real-world transport problems and for performing MABS with low hardware requirements.