A branch and cut approach to the orienteering problem with mandatory visits and conflicts - Pérez Franco, Marlene (2025)
This work proposed a Branch and Cut (B&C) method to solve the Orienteering Problem with Mandatory Visits and Conflicts (OPMVC), which is a combinatorial optimization problem that has extensive applicability in logistics, transportation, and network design, to mention a few. The goal is to find the route that maximizes the collected score, including all the mandatory and some optional vertices, without generating conflict between vertices or exceeding the time limit. The B&C algorithm is expected to outperform the performance of the best-known methods existing in the OPMVC literature in terms of computational efficiency and solution quality. Experimental analysis using benchmark instances from the literature confirms that the B&C algorithm performs effectively. The B&C method can cut down the computation times and offer optimum quality solutions at the same time by the use of undirected graphs in the formulation of the problem and the strategic integration of the relevant valid inequalities. In addition, this work has opened up prospects for extending the research to other routing problems with similar constraints, highlighting the need for introducing advanced optimization techniques into real-world problems.