On the Travelling Salesman Problem with Neighborhoods in a Polygonal World
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00364297" target="_blank" >RIV/68407700:21230/23:00364297 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/68407700:21730/23:00364297
Výsledek na webu
<a href="https://doi.org/10.1007/978-3-031-15226-9_32" target="_blank" >https://doi.org/10.1007/978-3-031-15226-9_32</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-15226-9_32" target="_blank" >10.1007/978-3-031-15226-9_32</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On the Travelling Salesman Problem with Neighborhoods in a Polygonal World
Popis výsledku v původním jazyce
The Travelling Salesman Problem with Neighborhoods (TSPN), as an extension of the broadly studied Travelling Salesman Problem, has many practical applications in robotics. Although several approaches to the problem have been introduced, they assume an environment without obstacles. In this paper, we introduce a method for the TSPN with polygonal neighborhoods taking polygonal obstacles into account. The method splits the problem into two subproblems: the Generalized Travelling Salesman Problem and the Touring Polygons Problem, which are solved sequentially. While the mature metaheuristic called Generalize Large Neighborhoods Search is employed to solve the first subproblem, the second one is solved by modifying the rubber-band algorithm. The experimental results show that the proposed approach outperforms a state-of-the-art algorithm modified for the environment with obstacles by 10–20% in most cases.
Název v anglickém jazyce
On the Travelling Salesman Problem with Neighborhoods in a Polygonal World
Popis výsledku anglicky
The Travelling Salesman Problem with Neighborhoods (TSPN), as an extension of the broadly studied Travelling Salesman Problem, has many practical applications in robotics. Although several approaches to the problem have been introduced, they assume an environment without obstacles. In this paper, we introduce a method for the TSPN with polygonal neighborhoods taking polygonal obstacles into account. The method splits the problem into two subproblems: the Generalized Travelling Salesman Problem and the Touring Polygons Problem, which are solved sequentially. While the mature metaheuristic called Generalize Large Neighborhoods Search is employed to solve the first subproblem, the second one is solved by modifying the rubber-band algorithm. The experimental results show that the proposed approach outperforms a state-of-the-art algorithm modified for the environment with obstacles by 10–20% in most cases.
Klasifikace
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)
Návaznosti výsledku
Projekt
<a href="/cs/project/EF15_003%2F0000470" target="_blank" >EF15_003/0000470: Robotika pro Průmysl 4.0</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2023
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
Robotics in Natural Settings CLAWAR 2022
ISBN
978-3-031-15225-2
ISSN
2367-3370
e-ISSN
2367-3389
Počet stran výsledku
12
Strana od-do
334-345
Název nakladatele
Springer
Místo vydání
Cham
Místo konání akce
Ponta Delgada
Datum konání akce
12. 9. 2022
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
000881628600029