On Improvement Heuristic to Solutions of the Close Enough Traveling Salesman Problem in Environments with Obstacles
Authors: Jindřiška Deckerová, Kristýna Kučerová, and Jan Faigl
The Close Enough Traveling Salesman Problem in environment with polygonal obstacles is addressed by an improvement heuristic based on the Mixed Integer Non-Linear Programming (MINLP) model.
Abstract
In this paper, we present a novel improvement heuristic to address the Close Enough Traveling Salesman Problem in environments with obstacles (CETSPo). The CETSPo 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 CETSPo. 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 CETSPo.
Citation:
@inproceedings{deckerova23ecmr,
author = {Deckerová, Jindřiška and Kučerová, Kristýna and Faigl, Jan},
title = {On Improvement Heuristic to Solutions of the Close Enough Traveling Salesman Problem in Environments with Obstacles},
booktitle = {European Conference on Mobile Robots (ECMR)},
pages = {},
year = {2023}
}