Multiagent Coordination and Teamwork: A Case Study for Large-Scale Dynamic Ready-Mixed Concrete Delivery Problem

Abstract

The ready-mixed concrete delivery (RMC) problem is a scheduling problem, where multiple trucks deliver concrete to order sites abiding by hard constraints in a dynamic environment. It is an NP-hard problem, impractical to solve using exhaustive methods. Thus, it requires heuristic-based approaches for generating sub-optimal schedules. Due to its distributed nature, we address this problem using a decentralised, scalable, cooperative MAS (multiagent system) that dynamically generates schedules. We explore the impact of teamwork by trucks on schedule optimisation. This work illustrates two novel approaches that address the dynamic RMC problem; a Delegate MAS approach and a team-extended approach. We present an empirical study, comparing our novel approaches with existing ones. The evaluation is performed by classifying the RMC case study scenarios into unique stress, scale, and dynamism characteristics. With 40% to 70% improvement over different metrics, the results show that both approaches generate better schedules, and using agent teams augments the performance. Thus, such decentralized MAS with the appropriate coordination approach and teamwork can be used for solving constrained dynamic scheduling problems.

Keywords

• bio-inspired computing
• decentralised coordination
• dynamic pickup and delivery problems
• dynamic scheduling
• large scale
• multiagent systems