A clustering metaheuristic for large orienteering problems
<p dir="ltr">The Orienteering Problem is a routing problem that commonly appears in mapping, transportation, distribution, and scheduling scenarios. The Orienteering Problem is a challenging NP-hard problem, such that obtaining optimal or near optimal solutions usually requires a sig...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2022
|
| Subjects: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1864513522535235584 |
|---|---|
| author | Almiqdad Elzein (13141038) |
| author2 | Gianni A. Di Caro (23275861) |
| author2_role | author |
| author_facet | Almiqdad Elzein (13141038) Gianni A. Di Caro (23275861) |
| author_role | author |
| dc.creator.none.fl_str_mv | Almiqdad Elzein (13141038) Gianni A. Di Caro (23275861) |
| dc.date.none.fl_str_mv | 2022-07-22T09:00:00Z |
| dc.identifier.none.fl_str_mv | 10.1371/journal.pone.0271751 |
| dc.relation.none.fl_str_mv | https://figshare.com/articles/journal_contribution/A_clustering_metaheuristic_for_large_orienteering_problems/31444459 |
| dc.rights.none.fl_str_mv | CC BY 4.0 info:eu-repo/semantics/openAccess |
| dc.subject.none.fl_str_mv | Mathematical sciences Applied mathematics Numerical and computational mathematics Orienteering Problem NP-hard routing problem Metaheuristic algorithms Multi-stage clustering Online optimization |
| dc.title.none.fl_str_mv | A clustering metaheuristic for large orienteering problems |
| dc.type.none.fl_str_mv | Text Journal contribution info:eu-repo/semantics/publishedVersion text contribution to journal |
| description | <p dir="ltr">The Orienteering Problem is a routing problem that commonly appears in mapping, transportation, distribution, and scheduling scenarios. The Orienteering Problem is a challenging NP-hard problem, such that obtaining optimal or near optimal solutions usually requires a significant amount of computation for large and even moderately large instances. As a result, existing algorithms cannot effectively be utilized for solving large Orienteering Problems in an online setting, which is often required in real-world applications where a plan has to be iteratively computed. For instance, a planner might need to adapt to changes in the scenario or in the environment (e.g., this is common in goods delivery, as well as in mobile robotic scenarios for coverage, monitoring, and surveillance). Motivated by these limitations, we propose a multi-stage clustering-based metaheuristic for tackling large Orienteering Problems in an effective, strategically controlled amount of computation time. The metaheuristic starts by decomposing the problem into smaller, independent sub-problems that are efficiently solved using an algorithm of choice, sequentially or in parallel. The obtained solutions are then merged to form a solution for the original problem, and then further optimized and processed to ensure feasibility. The metaheuristic aims to dramatically improve the computation time of a given Orienteering Problem algorithm without a significant decrease in the solution quality of that algorithm, especially for large Orienteering Problems. We have validated the effectiveness of the proposed metaheuristic design through a set of computational experiments. In particular, using a state-of-the-art heuristic and an exact algorithm, we have shown that it is significantly beneficial to use the Orienteering Problem algorithm plugged into our metaheuristic, as opposed to using it as a standalone algorithm. This was found to be especially true for large problems. As a result, large instances of Orienteering Problems can be effectively tackled within reasonable time bounds even for online application scenarios.</p><h2 dir="ltr">Other Information</h2><p dir="ltr">Published in: PLOS ONE<br>License: <a href="http://creativecommons.org/licenses/by/4.0/" target="_blank">http://creativecommons.org/licenses/by/4.0/</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1371/journal.pone.0271751" target="_blank">https://dx.doi.org/10.1371/journal.pone.0271751</a></p> |
| eu_rights_str_mv | openAccess |
| id | Manara2_1fe585cc1fa56189c6ed796a8aa0a9c5 |
| identifier_str_mv | 10.1371/journal.pone.0271751 |
| network_acronym_str | Manara2 |
| network_name_str | Manara2 |
| oai_identifier_str | oai:figshare.com:article/31444459 |
| publishDate | 2022 |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| rights_invalid_str_mv | CC BY 4.0 |
| spelling | A clustering metaheuristic for large orienteering problemsAlmiqdad Elzein (13141038)Gianni A. Di Caro (23275861)Mathematical sciencesApplied mathematicsNumerical and computational mathematicsOrienteering ProblemNP-hard routing problemMetaheuristic algorithmsMulti-stage clusteringOnline optimization<p dir="ltr">The Orienteering Problem is a routing problem that commonly appears in mapping, transportation, distribution, and scheduling scenarios. The Orienteering Problem is a challenging NP-hard problem, such that obtaining optimal or near optimal solutions usually requires a significant amount of computation for large and even moderately large instances. As a result, existing algorithms cannot effectively be utilized for solving large Orienteering Problems in an online setting, which is often required in real-world applications where a plan has to be iteratively computed. For instance, a planner might need to adapt to changes in the scenario or in the environment (e.g., this is common in goods delivery, as well as in mobile robotic scenarios for coverage, monitoring, and surveillance). Motivated by these limitations, we propose a multi-stage clustering-based metaheuristic for tackling large Orienteering Problems in an effective, strategically controlled amount of computation time. The metaheuristic starts by decomposing the problem into smaller, independent sub-problems that are efficiently solved using an algorithm of choice, sequentially or in parallel. The obtained solutions are then merged to form a solution for the original problem, and then further optimized and processed to ensure feasibility. The metaheuristic aims to dramatically improve the computation time of a given Orienteering Problem algorithm without a significant decrease in the solution quality of that algorithm, especially for large Orienteering Problems. We have validated the effectiveness of the proposed metaheuristic design through a set of computational experiments. In particular, using a state-of-the-art heuristic and an exact algorithm, we have shown that it is significantly beneficial to use the Orienteering Problem algorithm plugged into our metaheuristic, as opposed to using it as a standalone algorithm. This was found to be especially true for large problems. As a result, large instances of Orienteering Problems can be effectively tackled within reasonable time bounds even for online application scenarios.</p><h2 dir="ltr">Other Information</h2><p dir="ltr">Published in: PLOS ONE<br>License: <a href="http://creativecommons.org/licenses/by/4.0/" target="_blank">http://creativecommons.org/licenses/by/4.0/</a><br>See article on publisher's website: <a href="https://dx.doi.org/10.1371/journal.pone.0271751" target="_blank">https://dx.doi.org/10.1371/journal.pone.0271751</a></p>2022-07-22T09:00:00ZTextJournal contributioninfo:eu-repo/semantics/publishedVersiontextcontribution to journal10.1371/journal.pone.0271751https://figshare.com/articles/journal_contribution/A_clustering_metaheuristic_for_large_orienteering_problems/31444459CC BY 4.0info:eu-repo/semantics/openAccessoai:figshare.com:article/314444592022-07-22T09:00:00Z |
| spellingShingle | A clustering metaheuristic for large orienteering problems Almiqdad Elzein (13141038) Mathematical sciences Applied mathematics Numerical and computational mathematics Orienteering Problem NP-hard routing problem Metaheuristic algorithms Multi-stage clustering Online optimization |
| status_str | publishedVersion |
| title | A clustering metaheuristic for large orienteering problems |
| title_full | A clustering metaheuristic for large orienteering problems |
| title_fullStr | A clustering metaheuristic for large orienteering problems |
| title_full_unstemmed | A clustering metaheuristic for large orienteering problems |
| title_short | A clustering metaheuristic for large orienteering problems |
| title_sort | A clustering metaheuristic for large orienteering problems |
| topic | Mathematical sciences Applied mathematics Numerical and computational mathematics Orienteering Problem NP-hard routing problem Metaheuristic algorithms Multi-stage clustering Online optimization |