An Novel Method for Solving Touring-polygons Problem with Obstacles

Abstract Abstract Touring-polygons problem with obstacles (TPPO) is a very open topic in drone routing problems, wireless sensor networks, robot automation etc. How to efficiently solve TPPO has caused huge attention in both academic and industry. Computationally speaking, touring a set of polygons across obstacles, with which agents need to avoid collision, is NP-hard. In this paper, we propose a discrete scheme that transforms the continuous space into a set of discrete points, which enables us to search the upper bound of optimal solution efficiently. Based on the proposed discrete scheme, a gradient descent algorithm is proposed to solve touringpolygons problem. Second, given a set of polygons and a set of obstacles, we propose a mixedinteger programming model to efficiently find the upper bound. An extensive computational tests demonstrate the efficiency of the proposed methods when comparing the existing methods, i.e., rubber-band algorithm.