2024/10/16 by Alberto Guastalla, Guastalla, Alberto, Roberto Aringhieri +3 · 2 citations
Computer Science · #FOS: Mathematics #Mobile Agent-Based Network Management #Optimization and Control (math.OC) #Service-Oriented Architecture and Web Services #Software Engineering Techniques and Practices
paper · pdf · doi:10.48550/arxiv.2410.12368
openalex publication_date 2024/10/16 · openalex created_date 2024/10/20 · openalex updated_date 2026/07/28
The Team Orienteering Problem with Service Times and Mandatory & Incompatible Nodes (TOP-ST-MIN) is a variant of the classic Team Orienteering Problem (TOP), which includes three novel features that stem from two real-world problems previously studied by the authors. We prove that even finding a feasible solution is NP-complete. Two versions of this variant are considered in our study. For such versions, we proposed two alternative mathematical formulations, a mixed and a compact formulations. Based on the compact formulation, we developed a Cutting-Plane Algorithm (CPA) exploiting five families of valid inequalities. Extensive computational experiments showed that the CPA outperforms CPLEX in solving the new benchmark instances, generated in such a way to evaluate the impact of the three novel features that characterise the problem. The CPA is also competitive for the TOP since it is able to solve almost the same number of instances as the state-of-art algorithms.