On Improvement Heuristic to Solutions of the Close Enough Traveling Salesman Problem in Environments with Obstacles

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F23%3A00372383" target="_blank" >RIV/68407700:21230/23:00372383 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1109/ECMR59166.2023.10256328" target="_blank" >https://doi.org/10.1109/ECMR59166.2023.10256328</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/ECMR59166.2023.10256328" target="_blank" >10.1109/ECMR59166.2023.10256328</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Improvement Heuristic to Solutions of the Close Enough Traveling Salesman Problem in Environments with Obstacles

Popis výsledku v původním jazyce

In this paper, we present a novel improvement heuristic to address the Close Enough Traveling Salesman Problem in environments with obstacles (CETSPobs). The CETSPobs is a variant of the Traveling Salesman Problem (TSP), where the goal is to find a sequence of visits to given disk-shaped regions together with the points of visits to the regions. We address challenging instances in a polygonal domain with polygonal obstacles, where the final path connecting the regions must be collision-free. We propose a novel Post-Optimization procedure using Mixed Integer Non-Linear Programming (MINLP) to improve existing heuristic solutions to the CETSPobs. We deploy the method with existing heuristic solvers and based on the presented evaluation results, the proposed Post-Optimization significantly improves the heuristic solutions of all examined solvers and makes them competitive regarding the solution quality. The statistical evaluation reveals that the sequence found using relatively sparse sampling of the disk regions yields the best solutions among the evaluated solvers. The results support the benefit of the proposed MINLP-based solution to the continuous optimization of the CETSPobs.

Název v anglickém jazyce

On Improvement Heuristic to Solutions of the Close Enough Traveling Salesman Problem in Environments with Obstacles

Popis výsledku anglicky

In this paper, we present a novel improvement heuristic to address the Close Enough Traveling Salesman Problem in environments with obstacles (CETSPobs). The CETSPobs is a variant of the Traveling Salesman Problem (TSP), where the goal is to find a sequence of visits to given disk-shaped regions together with the points of visits to the regions. We address challenging instances in a polygonal domain with polygonal obstacles, where the final path connecting the regions must be collision-free. We propose a novel Post-Optimization procedure using Mixed Integer Non-Linear Programming (MINLP) to improve existing heuristic solutions to the CETSPobs. We deploy the method with existing heuristic solvers and based on the presented evaluation results, the proposed Post-Optimization significantly improves the heuristic solutions of all examined solvers and makes them competitive regarding the solution quality. The statistical evaluation reveals that the sequence found using relatively sparse sampling of the disk regions yields the best solutions among the evaluated solvers. The results support the benefit of the proposed MINLP-based solution to the continuous optimization of the CETSPobs.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/GA22-05762S" target="_blank" >GA22-05762S: Optimální řešení robotických směrovacích úloh</a><br>

Návaznosti

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

Rok uplatnění

2023

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 statě ve sborníku

Proceedings of 11th European Conference on Mobile Robots

ISBN

979-8-3503-0704-7

ISSN

2639-7919

e-ISSN

—

Počet stran výsledku

6

Strana od-do

180-185

Název nakladatele

Institute of Electrical and Electronics Engineers

Místo vydání

Brighton

Místo konání akce

Coimbra

Datum konání akce

4. 9. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001082260500027