WiSM: Windowing Surrogate Model for Evaluation of Curvature-Constrained Tours With Dubins Vehicle
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00356027" target="_blank" >RIV/68407700:21230/22:00356027 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1109/TCYB.2020.3000465" target="_blank" >https://doi.org/10.1109/TCYB.2020.3000465</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/TCYB.2020.3000465" target="_blank" >10.1109/TCYB.2020.3000465</a>
Alternative languages
Result language
angličtina
Original language name
WiSM: Windowing Surrogate Model for Evaluation of Curvature-Constrained Tours With Dubins Vehicle
Original language description
Dubins tours represent a solution of the Dubins traveling salesman problem (DTSP) that is a variant of the optimization routing problem to determine a curvature-constrained shortest path to visit a set of locations such that the path is feasible for Dubins vehicle, which moves only forward and has a limited turning radius. The DTSP combines the NP-hard combinatorial optimization to determine the optimal sequence of visits to the locations, as in the regular TSP, with the continuous optimization of the heading angles at the locations, where the optimal heading values depend on the sequence of visits and vice versa. We address the computationally challenging DTSP by fast evaluation of the sequence of visits by the proposed windowing surrogate model (WiSM), which estimates the length of the optimal Dubins path connecting a sequence of locations in a Dubins tour. The estimation is sped up by a regression model trained using close to optimum solutions of small Dubins tours that are generalized for large-scale instances of the addressed DTSP utilizing the sliding-window technique and a cache for already computed results. The reported results support that the proposed WiSM enables fast convergence of a relatively simple evolutionary algorithm to high-quality solutions of the DTSP. We show that with an increasing number of locations, our algorithm scales significantly better than other state-of-the-art DTSP solvers.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
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
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2022
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
Name of the periodical
IEEE Transactions on Cybernetics
ISSN
2168-2267
e-ISSN
2168-2275
Volume of the periodical
52
Issue of the periodical within the volume
2
Country of publishing house
US - UNITED STATES
Number of pages
10
Pages from-to
1302-1311
UT code for WoS article
000756813500051
EID of the result in the Scopus database
2-s2.0-85124805783