Heuristic approaches for a new variant of the Team Orienteering Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909679434596352 |
|---|---|
| author | Guastalla, Alberto Aringhieri, Roberto Hosteins, Pierre |
| author_facet | Guastalla, Alberto Aringhieri, Roberto Hosteins, Pierre |
| contents | In this paper we tackle the Team Orienteering Problem with Service Times, Mandatory Nodes and Incompatibilities, introduced in~\cite{Guastalla2024} and arising from two real-world healthcare applications. We propose two heuristic algorithms in the form of a Variable Descent Neighbourhood algorithm and a matheuristic based on a Cuts Separation approach. For the former, we also provide a multi-thread version exploiting its intrinsic capability to be parallelised. Both algorithms include a specific heuristic routine to provide a starting feasible solution, since finding a feasible solution has been proved to be NP-complete. The results of our heuristic algorithms are compared with an exact cutting plane approach and have complementary strengths and weaknesses. They are also evaluated on existing TOP benchmarks against TOP state-of-the-art algorithms, demonstrating their competitiveness on general grounds. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_06012 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Heuristic approaches for a new variant of the Team Orienteering Problem Guastalla, Alberto Aringhieri, Roberto Hosteins, Pierre Optimization and Control In this paper we tackle the Team Orienteering Problem with Service Times, Mandatory Nodes and Incompatibilities, introduced in~\cite{Guastalla2024} and arising from two real-world healthcare applications. We propose two heuristic algorithms in the form of a Variable Descent Neighbourhood algorithm and a matheuristic based on a Cuts Separation approach. For the former, we also provide a multi-thread version exploiting its intrinsic capability to be parallelised. Both algorithms include a specific heuristic routine to provide a starting feasible solution, since finding a feasible solution has been proved to be NP-complete. The results of our heuristic algorithms are compared with an exact cutting plane approach and have complementary strengths and weaknesses. They are also evaluated on existing TOP benchmarks against TOP state-of-the-art algorithms, demonstrating their competitiveness on general grounds. |
| title | Heuristic approaches for a new variant of the Team Orienteering Problem |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2507.06012 |