Combinatorial lower bounds for the Generalized Traveling Salesman Problem with Neighborhoods

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F24%3A00380507" target="_blank" >RIV/68407700:21230/24:00380507 - isvavai.cz</a>

Result on the web

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

DOI - Digital Object Identifier

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

Result language

angličtina

Original language name

Combinatorial lower bounds for the Generalized Traveling Salesman Problem with Neighborhoods

Original language description

In this paper, we study the Generalized Traveling Salesman Problem with Neighborhoods (GTSPN), a variant of the Traveling Salesman Problem (TSP), where the goal is to find the shortest path visiting each of the given neighborhood sets represented as a set of convex regions. The GTSPN is motivated by the sequencing problem of robotic manipulators, where an operation can be achieved from multiple locations, such as the visual inspection that can be performed from several possible views. The GTSPN formulation allows for exploiting continuous optimization to find the most suitable locations for the inspection, yielding possible solution cost reduction. Moreover, instances with overlapping high-dimensional convex regions further allow modeling neighborhood sets with complex shapes. We propose a novel approach to determine the first lower bounds to the studied GTSPN by employing the Branch-and-Bound (BB) method and the Mixed-Integer Second- Order Cone Programming (MISOCP) model for particular BB subproblems. In addition, the proposed method allows for solving the GTSPN to optima. The developed lower bound determination is further exploited in the empirical evaluation of existing heuristic approaches to the GTSPN and assesses the solution quality using the relative optimality gap. Regarding the presented results, the proposed BB-based approach provides tight lower bounds and solutions with up to 20 % optimality gap for the GTSPN instances with less than 15 neighborhood sets for the given limited computational time. Furthermore, the presented results support that the proposed approach is suitable for solving high-dimensional instances of the GTSPN that can be found in inspection tasks with robotic manipulators.

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

2024

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

258

Issue of the periodical within the volume

December

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

11

Pages from-to

—

UT code for WoS article

001308848900001

EID of the result in the Scopus database

2-s2.0-85202298350