Greedy Randomized Adaptive Search Procedure for Close Enough Orienteering Problem
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F20%3A00342394" target="_blank" >RIV/68407700:21230/20:00342394 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1145/3341105.3374010" target="_blank" >https://doi.org/10.1145/3341105.3374010</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3341105.3374010" target="_blank" >10.1145/3341105.3374010</a>
Alternative languages
Result language
angličtina
Original language name
Greedy Randomized Adaptive Search Procedure for Close Enough Orienteering Problem
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA19-20238S" target="_blank" >GA19-20238S: Multi-Robot Persistent Monitoring of Dynamic Environments</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the ACM Symposium on Applied Computing
ISBN
978-1-4503-6866-7
ISSN
—
e-ISSN
—
Number of pages
7
Pages from-to
808-814
Publisher name
Association for Computing Machinery
Place of publication
New York
Event location
Brno
Event date
Mar 30, 2020
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000569720900117