Traveling Salesman Problem with neighborhoods on a sphere in reflectance transformation imaging scenarios

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00359349" target="_blank" >RIV/68407700:21230/22:00359349 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.eswa.2022.116814" target="_blank" >https://doi.org/10.1016/j.eswa.2022.116814</a>

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Traveling Salesman Problem with neighborhoods on a sphere in reflectance transformation imaging scenarios

Popis výsledku v původním jazyce

In this paper, we propose a solution to the non-Euclidean variant of the Traveling Salesman Problem with Neighborhoods on a Sphere (TSPNS). The introduced problem formulation is motivated by practical scenarios of employing unmanned aerial vehicles in the Reflectance Transformation Imaging (RTI). In the RTI, a vehicle is requested to visit a set of sites at a constant distance from the object of interest and cast light from different directions to model the object from the images captured from another fixed location. Even though the problem can be formulated as an instance of the regular traveling salesman problem, we report a significant reduction of the solution cost by exploiting a non-zero tolerance on the light direction and defining the sites as regions on a sphere. The continuous neighborhoods of the TSPNS can be sampled into discrete sets, and the problem can be transformed into the generalized traveling salesman problem. However, finding high-quality solutions requires dense sampling, which increases the computational requirements. Therefore, we propose a practical heuristic solution based on the unsupervised learning of the Growing Self-Organizing Array (GSOA) that quickly finds an initial solution with the competitive quality to the sampling-based method. Furthermore, we propose a fast post-processing optimization to improve the initial solutions of both solvers. Based on the reported results, the proposed GSOA-based solver provides solutions of a similar quality to the transformation approach while it is about two orders of magnitude less computationally demanding.

Název v anglickém jazyce

Traveling Salesman Problem with neighborhoods on a sphere in reflectance transformation imaging scenarios

Popis výsledku anglicky

In this paper, we propose a solution to the non-Euclidean variant of the Traveling Salesman Problem with Neighborhoods on a Sphere (TSPNS). The introduced problem formulation is motivated by practical scenarios of employing unmanned aerial vehicles in the Reflectance Transformation Imaging (RTI). In the RTI, a vehicle is requested to visit a set of sites at a constant distance from the object of interest and cast light from different directions to model the object from the images captured from another fixed location. Even though the problem can be formulated as an instance of the regular traveling salesman problem, we report a significant reduction of the solution cost by exploiting a non-zero tolerance on the light direction and defining the sites as regions on a sphere. The continuous neighborhoods of the TSPNS can be sampled into discrete sets, and the problem can be transformed into the generalized traveling salesman problem. However, finding high-quality solutions requires dense sampling, which increases the computational requirements. Therefore, we propose a practical heuristic solution based on the unsupervised learning of the Growing Self-Organizing Array (GSOA) that quickly finds an initial solution with the competitive quality to the sampling-based method. Furthermore, we propose a fast post-processing optimization to improve the initial solutions of both solvers. Based on the reported results, the proposed GSOA-based solver provides solutions of a similar quality to the transformation approach while it is about two orders of magnitude less computationally demanding.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2022

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

Expert Systems with Applications

ISSN

0957-4174

e-ISSN

1873-6793

Svazek periodika

198

Číslo periodika v rámci svazku

116814

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

13

Strana od-do

—

Kód UT WoS článku

000792918500001

EID výsledku v databázi Scopus

2-s2.0-85127006924