Safety-Aware Multi-Robot Scheduling Under Time-Critical Constraints: A Colored Traveling Salesman Problem Approach

Abstract

The Colored Traveling Salesman Problem (CTSP) is a seminal generalization of the Multiple TSP, where colors represent the heterogeneity of salesmen and their city visits. This work presents a time-critical extension, termed the Time-Critical CTSP (T-CTSP). By emphasizing the timing of visits, T-CTSP explicitly captures spatio-temporal behaviors of agents, enabling the modeling of multi-agent path planning and scheduling in time-critical, safety-aware applications. A distance constraint is incorporated to ensure safe separation between salesmen and to prevent inter-agent conflicts. To solve large-scale instances, we propose a Beam Variable Neighborhood Search (BeamVNS) algorithm that integrates graph sparsification, greedy initialization, swap search, beam insertion, temporal coordination, and route-segment reconstruction. Graph sparsification reduces complexity by constructing a sparse city network, whereas a defined sequential insertion neighborhood has been theoretically proven to fully cover the solution space. Combined with a truncated tree search, this facilitates efficient beam-guided exploration. Extensive experiments validate the proposed formulation and demonstrate that BeamVNS outperforms baseline methods adapted for T-CTSP. Finally, T-CTSP and BeamVNS are applied to multi-robot 3D printing and rebar mesh welding, proving their effectiveness in optimizing complex robotic manufacturing processes. Note to Practitioners—This work is motivated by practical challenges in safety-aware multi-robot coordination. The proposed time-critical colored traveling salesman problem provides a unified mathematical formulation that simultaneously captures routing decisions, temporal coordination, and safety-distance constraints. The beam variable neighborhood search is developed to address the large-scale T-CTSP instances. Extensive experiments demonstrate that BeamVNS can provide high-quality and safety-aware operational plans for decision-makers. For practitioners, this framework can serve as a planning tool for multi-robot task scheduling and path planning in manufacturing and automation systems. Case studies in multi-robot 3D printing and rebar mesh welding further verify that the proposed approach effectively ensures collision avoidance among robots and significantly improves operational efficiency.