Exact Model and Solution Approach for the Service Agent Transport Problem

This work proposes an alternative formulation for the Service Agent Transport Problem (SATP), a widely studied problem in autonomous transportation. SATP involves service agents performing tasks within polygonal service areas and coordinating with autonomous transport agents for high-speed movement between locations. Actions, including servicing, moving, docking, and deploying, each have known execution times to minimize the mission makespan. Our formulation eliminates dependency on predefined phases used in previous work. It incorporates acceleration techniques such as problem-specific valid inequalities, warm-start strategies, node reduction, and lower bounds from approximation algorithms. Results demonstrate superior performance across lower bounds, upper bounds, and computational time, and we illustrate the approach with a case study on scheduling autonomous underwater surveillance vehicles.