Presentation on YouTube.

This study addresses the Dubins Travelling Salesman Problem with Neighbourhoods (DTSPN), a problem in which a Dubins vehicle, such as a drone or an underwater vehicle, must visit a set of continuous regions rather than discrete points, such as the neighbourhood of some areas of interest. Existing approaches for the DTSPN rely only on heuristic methods. We propose three Optimal Control (OC) formulations for the DTSPN and apply a direct transcription technique to convert the OC problems into Nonlinear Programming (NLP) counterparts, solvable by standard NLP solvers. Furthermore, we develop a decomposition algorithm to handle relatively large instances. Preliminary experiments indicate the effectiveness of the proposed framework. To our knowledge, this is the first work to deliver exact solutions for the DTSPN.