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

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - 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)

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)

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Expert Systems with Applications

ISSN

0957-4174

e-ISSN

1873-6793

Volume of the periodical

198

Issue of the periodical within the volume

116814

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

13

Pages from-to

—

UT code for WoS article

000792918500001

EID of the result in the Scopus database

2-s2.0-85127006924