| Sumario: | 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.
|
|---|
