The orienteering problem with mandatory visits and conflicts: a branch and cut approach
研究了一种带强制访问和冲突的定向问题变体，提出分支切割算法，在公开数据集上得到69个新最优解并改进了60个已知最优解。
In this study, we introduce a branch-and-cut approach to tackle the Orienteering Problem with Mandatory Visits and Conflicts-a variant of the classical Orienteering Problem. In this variant, certain nodes must be visited while others are optional, provided they fit within the time budget and do not conflict with each other. We developed an efficient separation algorithm that incorporates valid cuts at the root node to strengthen the linear relaxation and a heuristic designed to generate a feasible solution from the fractional solution obtained during the linear relaxation process. We evaluated the performance of our method by comparing it to the best-known Mixed Integer Linear Programming model and a hybrid variable neighbourhood search from the literature. Using a publicly available benchmark dataset, our computational results demonstrate that our proposed method yields 69 new optimal solutions and improves upon 60 best-known solutions.