IB-DARP: An Algorithm for Multi-Vessel Collaborative Task and Path Planning

This paper presents IB-DARP (Iteration Balancing—Divide Areas Routing Problem), an enhanced multi-vessel cooperative mission and path planning method designed to address the limitations of traditional approaches, including uneven task allocation, workload imbalance, and path conflicts. The proposed method integrates four key mechanisms to improve planning robustness and computational efficiency. A historical data mining mechanism is first employed to extract stable navigation patterns from accumulated vessel trajectories and construct a high-confidence maritime route network. Based on this network, a precomputation mechanism significantly reduces planning-stage computational complexity by calculating essential inter-node distances in advance. A heading-aware partitioning mechanism further decomposes the multi-vessel planning problem into tractable single-vessel subproblems, while an iterative auction–equilibrium mechanism dynamically adjusts task assignments to enhance global load balance and suppress conflicts. To evaluate the effectiveness of IB-DARP, comprehensive ablation studies and large-scale scenario experiments were conducted, demonstrating its advantages in mission allocation, conflict mitigation, and cooperative path optimization. The results confirm that IB-DARP provides a scalable and efficient solution for multi-vessel cooperative mission planning in complex maritime environments.