A branch and cut approach to the orienteering problem with mandatory visits and conflicts
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 fin...
| Main Author: | |
|---|---|
| Format: | Tesis |
| Language: | Spanish / Castilian |
| Published: |
2025
|
| Subjects: | |
| Online Access: | http://eprints.uanl.mx/30650/1/1080287350.pdf |
| _version_ | 1850528659904921600 |
|---|---|
| author | Pérez Franco, Marlene |
| author_facet | Pérez Franco, Marlene |
| author_sort | Pérez Franco, Marlene |
| collection | Repositorio Institucional |
| description | 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. |
| format | Tesis |
| id | eprints-30650 |
| institution | UANL |
| language | Spanish / Castilian |
| publishDate | 2025 |
| record_format | eprints |
| spelling | eprints-306502025-11-18T20:02:25Z http://eprints.uanl.mx/30650/ A branch and cut approach to the orienteering problem with mandatory visits and conflicts Pérez Franco, Marlene TK Ingeniería Eléctrica, Electrónica, Ingeniería Nuclear 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. 2025-10-02 Tesis NonPeerReviewed text es cc_by_nc_nd http://eprints.uanl.mx/30650/1/1080287350.pdf http://eprints.uanl.mx/30650/1.haspreviewThumbnailVersion/1080287350.pdf Pérez Franco, Marlene (2025) A branch and cut approach to the orienteering problem with mandatory visits and conflicts. Maestría thesis, Universidad Autónoma de Nuevo León. |
| spellingShingle | TK Ingeniería Eléctrica, Electrónica, Ingeniería Nuclear Pérez Franco, Marlene A branch and cut approach to the orienteering problem with mandatory visits and conflicts |
| thumbnail | https://rediab.uanl.mx/themes/sandal5/images/online.png |
| title | A branch and cut approach to the orienteering problem with mandatory visits and conflicts |
| title_full | A branch and cut approach to the orienteering problem with mandatory visits and conflicts |
| title_fullStr | A branch and cut approach to the orienteering problem with mandatory visits and conflicts |
| title_full_unstemmed | A branch and cut approach to the orienteering problem with mandatory visits and conflicts |
| title_short | A branch and cut approach to the orienteering problem with mandatory visits and conflicts |
| title_sort | branch and cut approach to the orienteering problem with mandatory visits and conflicts |
| topic | TK Ingeniería Eléctrica, Electrónica, Ingeniería Nuclear |
| url | http://eprints.uanl.mx/30650/1/1080287350.pdf |
| work_keys_str_mv | AT perezfrancomarlene abranchandcutapproachtotheorienteeringproblemwithmandatoryvisitsandconflicts AT perezfrancomarlene branchandcutapproachtotheorienteeringproblemwithmandatoryvisitsandconflicts |