On the Travelling Salesman Problem with Neighborhoods in a Polygonal World
The result's identifiers
Result code in 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>
Alternative codes found
RIV/68407700:21730/23:00364297
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
On the Travelling Salesman Problem with Neighborhoods in a Polygonal World
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/EF15_003%2F0000470" target="_blank" >EF15_003/0000470: Robotics 4 Industry 4.0</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Others
Publication year
2023
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Robotics in Natural Settings CLAWAR 2022
ISBN
978-3-031-15225-2
ISSN
2367-3370
e-ISSN
2367-3389
Number of pages
12
Pages from-to
334-345
Publisher name
Springer
Place of publication
Cham
Event location
Ponta Delgada
Event date
Sep 12, 2022
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000881628600029