On the Performance of Self-organizing Maps for the Non-Euclidean Traveling Salesman Problem in the Polygonal Domain

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F11%3A00182180" target="_blank" >RIV/68407700:21230/11:00182180 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.sciencedirect.com/science/article/pii/S0020025511002684" target="_blank" >http://www.sciencedirect.com/science/article/pii/S0020025511002684</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ins.2011.05.019" target="_blank" >10.1016/j.ins.2011.05.019</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Performance of Self-organizing Maps for the Non-Euclidean Traveling Salesman Problem in the Polygonal Domain

Popis výsledku v původním jazyce

In this paper, two state-of-the-art algorithms for the Traveling Salesman Problem (TSP) are examined in the multi-goal path planning problem motivated by inspection planning in the polygonal domain W. Both algorithms are based on the self-organizing map(SOM) for which an application in W is not typical. The first is Somhom's algorithm, and the second is the Co-adaptive net. These algorithms are augmented by a simple approximation of the shortest path among obstacles in W. Moreover, the competitive andcooperative rules are modified by recent adaptation rules for the Euclidean TSP, and by proposed enhancements to improve the algorithms' performance in the non-Euclidean TSP. Based on the modifications, two new variants of the algorithms are proposed that reduce the required computational time of their predecessors by an order of magnitude, therefore making SOM more competitive with combinatorial heuristics.

Název v anglickém jazyce

On the Performance of Self-organizing Maps for the Non-Euclidean Traveling Salesman Problem in the Polygonal Domain

Popis výsledku anglicky

In this paper, two state-of-the-art algorithms for the Traveling Salesman Problem (TSP) are examined in the multi-goal path planning problem motivated by inspection planning in the polygonal domain W. Both algorithms are based on the self-organizing map(SOM) for which an application in W is not typical. The first is Somhom's algorithm, and the second is the Co-adaptive net. These algorithms are augmented by a simple approximation of the shortest path among obstacles in W. Moreover, the competitive andcooperative rules are modified by recent adaptation rules for the Euclidean TSP, and by proposed enhancements to improve the algorithms' performance in the non-Euclidean TSP. Based on the modifications, two new variants of the algorithms are proposed that reduce the required computational time of their predecessors by an order of magnitude, therefore making SOM more competitive with combinatorial heuristics.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

JC - Počítačový hardware a software

OECD FORD obor

—

Projekt

<a href="/cs/project/7E08006" target="_blank" >7E08006: Robotic Evolutionary Self-Programming and Self-Assembling Organisms</a><br>

Návaznosti

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

Rok uplatnění

2011

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 periodika

Information Sciences

ISSN

0020-0255

e-ISSN

—

Svazek periodika

181

Číslo periodika v rámci svazku

19

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

16

Strana od-do

4214-4229

Kód UT WoS článku

000293304600010

EID výsledku v databázi Scopus

—