An Accurate MILP Formulation for Multi-UAV Routing with Spatiotemporal Collision Avoidance

The use of Unmanned Aerial Vehicles (UAVs) in indoor logistics requires secure routing. Classical models (mTSP) ignore the physical volume of aircraft, generating collisions, while reactive strategies fail in dense aisles. To fill this gap, this work proposes ST-mTSP (Spatio-Temporal mTSP), an exact model in Mixed Integer Linear Programming (MILP). The formulation introduces collision avoidance constraints via the Big-M method, imposing time separation windows t_min on spatially conflicting nodes. Computational experiments reveal that strict security assurance requires an acceptable average 'cost of security' of 8.95% in the objective function relative to standard mTSP. Scalability analysis indicates that larger fleets mitigate T_max restricted flight range bottlenecks. It is concluded that the ST-mTSP offers a rigorous basis for multi-UAV operations, justifying the small operational trade-off by the total mitigation of the risk of collisions.