On Self-Organizing Maps for Orienteering Problems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00315452" target="_blank" >RIV/68407700:21230/17:00315452 - isvavai.cz</a>

Výsledek na webu

<a href="http://ieeexplore.ieee.org/document/7966175/" target="_blank" >http://ieeexplore.ieee.org/document/7966175/</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/IJCNN.2017.7966175" target="_blank" >10.1109/IJCNN.2017.7966175</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Self-Organizing Maps for Orienteering Problems

Popis výsledku v původním jazyce

This paper concerns principles of unsupervised learning of self-organizing maps (SOMs) to address optimization routing problems called the Orienteering Problem (OP) and its multi-vehicle variant called the Team Orienteering Problem (TOP). The problems are similar to the traveling salesman problem in finding an optimal tour to visit all the given locations, but here, each location has specified reward that can be collected by the tour and the problem is to select the most valuable subset of the locations that can be visited within the travel budget. In existing SOM for the OP, the locations to be visited are duplicated to adapt the network to locations with higher rewards more frequently. The proposed novel SOM-based solution overcomes this necessity and based on the presented results it significantly reduces the computational burden of the adaptation procedure. Besides, the proposed approach improves the quality of solutions and makes SOM competitive to existing heuristics for the OP, but still behind computationally expensive metaheuristics for the TOP. On the other hand, the main benefit of the SOM-based approaches over the existing heuristics is in solving the generalized variant of the OP and TOP with neighborhoods. These variants of the problem formulation allow to better utilize the travel budget for instances where the reward associated with the location can be collected by visiting a particular neighborhood of the location and not exactly the location itself. This generalized problem formulation better models situations of the robotic data collection, e.g., using wireless communication or range sensors.

Název v anglickém jazyce

On Self-Organizing Maps for Orienteering Problems

Popis výsledku anglicky

This paper concerns principles of unsupervised learning of self-organizing maps (SOMs) to address optimization routing problems called the Orienteering Problem (OP) and its multi-vehicle variant called the Team Orienteering Problem (TOP). The problems are similar to the traveling salesman problem in finding an optimal tour to visit all the given locations, but here, each location has specified reward that can be collected by the tour and the problem is to select the most valuable subset of the locations that can be visited within the travel budget. In existing SOM for the OP, the locations to be visited are duplicated to adapt the network to locations with higher rewards more frequently. The proposed novel SOM-based solution overcomes this necessity and based on the presented results it significantly reduces the computational burden of the adaptation procedure. Besides, the proposed approach improves the quality of solutions and makes SOM competitive to existing heuristics for the OP, but still behind computationally expensive metaheuristics for the TOP. On the other hand, the main benefit of the SOM-based approaches over the existing heuristics is in solving the generalized variant of the OP and TOP with neighborhoods. These variants of the problem formulation allow to better utilize the travel budget for instances where the reward associated with the location can be collected by visiting a particular neighborhood of the location and not exactly the location itself. This generalized problem formulation better models situations of the robotic data collection, e.g., using wireless communication or range sensors.

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/GA16-24206S" target="_blank" >GA16-24206S: Metody informatického plánování cest pro neholonomní mobilní roboty v úlohách monitorování a dohledu</a><br>

Návaznosti

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

Rok uplatnění

2017

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 International Joint Conference on Neural Networks

ISBN

978-1-5090-6181-5

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

2611-2620

Název nakladatele

IEEE Xplore

Místo vydání

—

Místo konání akce

Anchorage

Datum konání akce

14. 5. 2017

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

WRD - Celosvětová akce

Kód UT WoS článku

000426968702113