Lower-bound Solutions to the Touring Regions Problem with Polygonal Obstacles and Disk-shaped Regions

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F25%3A00388322" target="_blank" >RIV/68407700:21230/25:00388322 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1109/ECMR65884.2025.11162978" target="_blank" >https://doi.org/10.1109/ECMR65884.2025.11162978</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1109/ECMR65884.2025.11162978" target="_blank" >10.1109/ECMR65884.2025.11162978</a>

Result language
angličtina
Original language name
Lower-bound Solutions to the Touring Regions Problem with Polygonal Obstacles and Disk-shaped Regions
Original language description
The paper studies lower bounds on the optimal solution of the shortest path connecting a sequence of regions with the presence of obstacles. For disk-shaped regions, a straightforward bound can be based on relaxing the obstacles and using Euclidean distance between the disks or the Second Order Cone Programming (SOCP). However, such lower bounds would be poor if regions are mutually close but reachable by relatively long detours, avoiding the obstacles. Therefore, we analyze the two-disk shortest path problem with three possible cases and use the path in lower bound estimation called TriCase. We show TriCase is a tighter lower bound than using Euclidean and SOCP-based approaches for specific instances. Based on the evaluation results, we propose to combine TriCase and SOCP approaches to determine the lower bound on the shortest path connecting disk-shaped regions in environments with polygonal obstacles. The lower bound is further employed in assessing the quality of a feasible sampling-based solution to the touring regions problem, supporting the viability of the proposed approach for routing problems with neighborhoods and the presence of polygonal obstacles.
Czech name
—
Czech description
—

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
2025
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
2025 European Conference on Mobile Robots Conference Proceedings
ISBN
979-8-3315-2705-1
ISSN
2639-7919
e-ISSN
2767-8733
Number of pages
6
Pages from-to
1-6
Publisher name
IEEE
Place of publication
—
Event location
Padua
Event date
Sep 2, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001592487100008

Similar results(10)