Greedy Randomized Adaptive Search Procedure for Close Enough Orienteering Problem

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Greedy Randomized Adaptive Search Procedure for Close Enough Orienteering Problem

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Greedy Randomized Adaptive Search Procedure for Close Enough Orienteering Problem

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA19-20238S" target="_blank" >GA19-20238S: Multi-robotické monitorování dynamických prostředí</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2020

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the ACM Symposium on Applied Computing

ISBN

978-1-4503-6866-7

ISSN

—

e-ISSN

—

Počet stran výsledku

7

Strana od-do

808-814

Název nakladatele

Association for Computing Machinery

Místo vydání

New York

Místo konání akce

Brno

Datum konání akce

30. 3. 2020

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000569720900117