The orienteering problem with mandatory visits and conflicts: a branch and cut approach

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.