research-article

Greedy randomized adaptive search procedure for close enough orienteering problem

Authors:

Petra Štefaníková,

Jan FaiglAuthors Info & Claims

SAC '20: Proceedings of the 35th Annual ACM Symposium on Applied Computing

Pages 808 - 814

https://doi.org/10.1145/3341105.3374010

Published: 30 March 2020 Publication History

Abstract

In this paper, we address the Close Enough Orienteering Problem (CEOP) that is motivated to find the most rewarding route visiting disk-shaped regions under the given travel budget. The CEOP differs from the regular OP in the continuous optimization of finding the most suitable waypoint locations to collect the reward associated with each region of interest in addition to the selection of the subset of the regions and sequence of their visits as in the OP. We propose to employ the Greedy Randomized Adaptive Search Procedure (GRASP) combinatorial metaheuristic to solve the addressed CEOP, in particular, the GRASP with Segment Remove. The continuous optimization is addressed by the newly introduced heuristic search that is applied in the construction phase and also in the local search phase of the GRASP. The proposed approach has been empirically evaluated using existing benchmarks, and based on the reported comparison with existing algorithms, the proposed GRASP-based approach provides solutions with the competitive quality while its computational requirements are low.

References

[1]

Best, G., Faigl, J., and Fitch, R. Online planning for multi-robot active perception with self-organising maps. Autonomous Robots 42, 4 (2018), 715--738.

[2]

Campos, V., Martí, R., Sánchez-Oro, J., and Duarte, A. Grasp with path relinking for the orienteering problem. Journal of the Operational Research Society 65, 12 (2014), 1800--1813.

[3]

Chao, I.-M., Golden, B. L., and Wasil, E. A. A fast and effective heuristic for the orienteering problem. European Journal of Operational Research 88, 3 (1996), 475--489.

[4]

Croes, G. A. A method for solving traveling-salesman problems. Operations Research 6, 6 (1958), 791--812.

Digital Library

[5]

Faigl, J. GSOA: growing self-organizing array - unsupervised learning for the close-enough traveling salesman problem and other routing problems. Neurocomputing 312 (2018), 120--134.

Digital Library

[6]

Faigl, J. Data collection path planning with spatially correlated measurements using growing self-organizing array. Applied Soft Computing 75 (2019), 130--147.

[7]

Faigl, J. Unsupervised learning-based solution of the close enough dubins orienteering problem. Neural Computing and Applications (2019).

[8]

Faigl, J., and Pěnička, R. On close enough orienteering problem with dubins vehicle. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (2017), pp. 5646--5652.

Digital Library

[9]

Faigl, J., Pěnička, R., and Best, G. Self-organizing map-based solution for the orienteering problem with neighborhoods. In IEEE International Conference on Systems, Man, and Cybernetics (SMC) (2016), pp. 1315--1321.

Digital Library

[10]

Feillet, D., Dejax, P., and Gendreau, M. Traveling salesman problems with profits. Transportation Science 39, 2 (2005), 188--205.

Digital Library

[11]

Feo, T. A., and Resende, M. G. C. Greedy randomized adaptive search procedures. Journal of Global Optimization 6, 2 (1995), 109--133.

[12]

Golden, B. L., Levy, L., and Vohra, R. The orienteering problem. Naval Research Logistics (NRL) 34, 3 (1987), 307--318.

[13]

Gunawan, A., Lau, H. C., and Vansteenwegen, P. Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research 255, 2 (2016), 315--332.

[14]

Hansen, P., and Mladenović, N. Variable neighborhood search: Principles and applications. European Journal of Operational Research 130, 3 (2001), 449--467.

[15]

Keshtkaran, M., and Ziarati, K. A novel grasp solution approach for the orienteering problem. Journal of Heuristics 22, 5 (2016), 699--726.

Digital Library

[16]

Pěnička, R., Faigl, J., and Saska, M. Variable neighborhood search for the set orienteering problem and its application to other orienteering problem variants. European Journal of Operational Research 276, 3 (2019), 816--825.

[17]

Pěnička, R., Faigl, J., Váňa, P., and Saska, M. Dubins orienteering problem. IEEE Robotics and Automation Letters 2, 2 (2017), 1210--1217.

[18]

Ramesh, R., and Brown, K. M. An efficient four-phase heuristic for the generalized orienteering problem. Computers & Operations Research 18, 2 (1991), 151--165.

Digital Library

[19]

Sevkli, Z., and Sevilgen, F. E. Variable neighborhood search for the orienteering problem. In 21th International Symposium on Computer and Information Sciences (ISCIS) (2006), pp. 134--143.

Digital Library

[20]

Tsiligirides, T. Heuristic methods applied to orienteering. The Journal of the Operational Research Society 35, 9 (1984), 797--809.

[21]

Tsiligirides, T. Heuristic methods applied to orienteering. Journal of the Operational Research Society 35, 9 (1984), 797--809.

[22]

Vansteenwegen, P., Souffriau, W., Berghe, G. V., and Oudheusden, D. V. A guided local search metaheuristic for the team orienteering problem. European Journal of Operational Research 196, 1 (2009), 118--127.

[23]

Vansteenwegen, P., Souffriau, W., and Oudheusden, D. V. The orienteering problem: A survey. European Journal of Operational Research 209, 1 (2011), 1--10.

[24]

Vansteenwegen, P., and Van Oudheusden, D. The mobile tourist guide: An or opportunity. OR Insight 20, 3 (Jul 2007), 21--27.

[25]

Štefaníková, P., Váňa, P., and Faigl, J. Greedy randomized adaptive search procedure for close enough orienteering problem. https://purl.org/comrob/sw. [cited on 2019-Dec-9].

Cited By

Davis BBray EBest G(2024)Multi-Goal Path Planning in Cluttered Environments with PRM-Guided Self-Organising Maps2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS58592.2024.10802120(10746-10753)Online publication date: 14-Oct-2024
https://doi.org/10.1109/IROS58592.2024.10802120
Qian QWang YBoyle D(2024)On solving close enough orienteering problems with overlapped neighborhoodsEuropean Journal of Operational Research10.1016/j.ejor.2024.05.032318:2(369-387)Online publication date: Oct-2024
https://doi.org/10.1016/j.ejor.2024.05.032
Singh HBiken Singh MPratik HPratap A(2023)UAV and UGV Assisted Path Planning for Sensor Data Collection in Precision Agriculture2023 11th International Symposium on Electronic Systems Devices and Computing (ESDC)10.1109/ESDC56251.2023.10149861(1-6)Online publication date: 4-May-2023
https://doi.org/10.1109/ESDC56251.2023.10149861
Show More Cited By

Index Terms

Greedy randomized adaptive search procedure for close enough orienteering problem

Index terms have been assigned to the content through auto-classification.

Recommendations

A novel GRASP solution approach for the Orienteering Problem

The Orienteering Problem (OP) is a well-known variant of the Traveling Salesman Problem. In this paper, a novel Greedy Randomized Adaptive Search Procedure (GRASP) solution is proposed to solve the OP. The proposed method is shown to outperform state-of-...
A hybrid variable neighborhood search for the Orienteering Problem with mandatory visits and exclusionary constraints

This paper addresses a variant of the Orienteering Problem in which some constraints related to mandatory visits and incompatibilities among nodes are taken into account. A hybrid algorithm based on a reactive GRASP and a general VNS is proposed. ...
Greedy randomized adaptive search procedure with exterior path relinking for differential dispersion minimization

We propose several new hybrid heuristics for the differential dispersion problem, the best of which consists of a GRASP with sampled greedy construction with variable neighborhood search for local improvement. The heuristic maintains an elite set of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SAC '20: Proceedings of the 35th Annual ACM Symposium on Applied Computing

March 2020

2348 pages

ISBN:9781450368667

DOI:10.1145/3341105

Conference Chairs:
Chih-Cheng Hung
Kennesaw State University
,
Tomas Cerny
Baylor University
,
Program Chairs:
Dongwan Shin
New Mexico Tech
,
Alessio Bechini
University of Pisa, Italy

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 March 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Grantová Agentura ðeské Republiky

Conference

SAC '20

Sponsor:

SIGAPP

SAC '20: The 35th ACM/SIGAPP Symposium on Applied Computing

March 30 - April 3, 2020

Brno, Czech Republic

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25

Sponsor:
sigapp

The 40th ACM/SIGAPP Symposium on Applied Computing

March 31 - April 4, 2025

Catania , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
208
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Davis BBray EBest G(2024)Multi-Goal Path Planning in Cluttered Environments with PRM-Guided Self-Organising Maps2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)10.1109/IROS58592.2024.10802120(10746-10753)Online publication date: 14-Oct-2024
https://doi.org/10.1109/IROS58592.2024.10802120
Qian QWang YBoyle D(2024)On solving close enough orienteering problems with overlapped neighborhoodsEuropean Journal of Operational Research10.1016/j.ejor.2024.05.032318:2(369-387)Online publication date: Oct-2024
https://doi.org/10.1016/j.ejor.2024.05.032
Singh HBiken Singh MPratik HPratap A(2023)UAV and UGV Assisted Path Planning for Sensor Data Collection in Precision Agriculture2023 11th International Symposium on Electronic Systems Devices and Computing (ESDC)10.1109/ESDC56251.2023.10149861(1-6)Online publication date: 4-May-2023
https://doi.org/10.1109/ESDC56251.2023.10149861
Paulavičius RStripinis LSutavičiūtė SKočegarov DFilatovas E(2023)A novel greedy genetic algorithm-based personalized travel recommendation systemExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.120580230:COnline publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1016/j.eswa.2023.120580
Pedersen CNielsen KRosenkrands KVasegaard ANielsen PEl Yafrani M(2021)A GRASP-Based Approach for Planning UAV-Assisted Search and Rescue MissionsSensors10.3390/s2201027522:1(275)Online publication date: 30-Dec-2021
https://doi.org/10.3390/s22010275

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten