Self-Organizing Map for the Curvature-Constrained Traveling Salesman Problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F16%3A00307174" target="_blank" >RIV/68407700:21230/16:00307174 - isvavai.cz</a>

Výsledek na webu

<a href="https://link.springer.com/chapter/10.1007/978-3-319-44781-0_59" target="_blank" >https://link.springer.com/chapter/10.1007/978-3-319-44781-0_59</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-44781-0_59" target="_blank" >10.1007/978-3-319-44781-0_59</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Self-Organizing Map for the Curvature-Constrained Traveling Salesman Problem

Popis výsledku v původním jazyce

In this paper, we consider a challenging variant of the traveling salesman problem (TSP) where it is requested to determine the shortest closed curvature-constrained path to visit a set of given locations. The problem is called the Dubins traveling salesman problem in literature and its main difficulty arises from the fact that it is necessary to determine the sequence of visits to the locations together with particular headings of the vehicle at the locations. We propose to apply principles of unsupervised learning of the self-organizing map to simultaneously determine the sequence of the visits together with the headings. A feasibility of the proposed approach is supported by an extensive evaluation and comparison to existing solutions. The presented results indicate that the proposed approach provides competitive solutions to existing heuristics, especially in dense problems, where the optimal sequence of the visits cannot be determined as a solution of the Euclidean TSP.

Název v anglickém jazyce

Self-Organizing Map for the Curvature-Constrained Traveling Salesman Problem

Popis výsledku anglicky

In this paper, we consider a challenging variant of the traveling salesman problem (TSP) where it is requested to determine the shortest closed curvature-constrained path to visit a set of given locations. The problem is called the Dubins traveling salesman problem in literature and its main difficulty arises from the fact that it is necessary to determine the sequence of visits to the locations together with particular headings of the vehicle at the locations. We propose to apply principles of unsupervised learning of the self-organizing map to simultaneously determine the sequence of the visits together with the headings. A feasibility of the proposed approach is supported by an extensive evaluation and comparison to existing solutions. The presented results indicate that the proposed approach provides competitive solutions to existing heuristics, especially in dense problems, where the optimal sequence of the visits cannot be determined as a solution of the Euclidean TSP.

Druh

D - Stať ve sborníku

CEP obor

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

OECD FORD obor

—

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í

2016

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

ARTIFICIAL NEURAL NETWORKS AND MACHINE LEARNING - ICANN 2016, PT II

ISBN

978-3-319-44780-3

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

9

Strana od-do

497-505

Název nakladatele

Springer VDI Verlag

Místo vydání

Düsseldorf

Místo konání akce

Barcelona

Datum konání akce

6. 9. 2016

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

WRD - Celosvětová akce

Kód UT WoS článku

000389086400059