A clustering metaheuristic for large orienteering problems
Open Access
- 22 July 2022
- journal article
- research article
- Published by Public Library of Science (PLoS) in PLOS ONE
- Vol. 17 (7) , e0271751
Abstract
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.Keywords
Funding Information
- QNRF (NPRP Grant 10-0213-170458)
This publication has 37 references indexed in Scilit:
- Lin–Kernighan heuristic adaptations for the generalized traveling salesman problemEuropean Journal of Operational Research, 2011
- The capacitated team orienteering and profitable tour problemsJournal of the Operational Research Society, 2009
- The Euclidean Orienteering Problem RevisitedSIAM Journal on Computing, 2008
- Clustering by Passing Messages Between Data PointsScience, 2007
- An efficient k-means clustering algorithm: analysis and implementationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2002
- New Results on the Old k-opt Algorithm for the Traveling Salesman ProblemSIAM Journal on Computing, 1999
- The team orienteering problemEuropean Journal of Operational Research, 1996
- The selective travelling salesman problemDiscrete Applied Mathematics, 1990
- Transforming asymmetric into symmetric traveling salesman problemsOperations Research Letters, 1983
- The clustered traveling salesman problemComputers & Operations Research, 1975