The team orienteering problem with service times and mandatory & incompatible nodes
研究了团队定向问题的新变种，包含服务时间、强制节点和节点间不兼容性，证明了可行性问题的NP完全性，提出了割平面算法并验证其优于CPLEX。
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 features that stem from two real-world problems previously studied by the authors: service time at nodes, mandatory nodes and physical or logical incompatibilities between pairs of nodes. We gather all these ingredients for the first time in the same model and prove that even finding a feasible solution to this problem is NP-complete unlike the TOP where finding a feasible solution is straightforward. Two versions of this variant are considered in our study. For such versions, we proposed two alternative mathematical formulations, a route-based and a flow-based formulations. Based on the flow-based formulation, we developed a Cutting-Plane Algorithm (CPA) exploiting five families of valid inequalities, which are either new or have generally not been used as such in the TOP literature and separated by means of new algorithmic methods. 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. • We formalise the TOP-ST-MIN, a new variant of the Team Orienteering Problem. • TOP-ST-MIN includes service times, mandatory nodes and two node incompatibilities. • We prove the NP-completeness of the feasibility version of the TOP-ST-MIN. • We provide a new formulation, new valid inequalities and cut separation techniques. • We design new instances to better evaluate our Cutting-Plane Algorithm.