Angle Bisector Algorithm and Modified Dynamic Programming Algorithm for Dubins Traveling Salesman Problem

A Dubin's Travelling Salesman Problem (DTSP) of finding a minimum length tour through a given set of points is considered. DTSP has a Dubins vehicle, which is capable of moving only forward with constant speed. In this paper, first, a worst case upper bound is obtained on DTSP tour length by assuming DTSP tour sequence same as Euclidean Travelling Salesman Problem (ETSP) tour sequence. It is noted that, in the worst case, \emph{any algorithm that uses of ETSP tour sequence} is a constant factor approximation algorithm for DTSP. Next, two new algorithms are introduced, viz., Angle Bisector Algorithm (ABA) and Modified Dynamic Programming Algorithm (MDPA). In ABA, ETSP tour sequence is used as DTSP tour sequence and orientation angle at each point $i_k$ are calculated by using angle bisector of the relative angle formed between the rays $i_{k}i_{k-1}$ and $i_ki_{k+1}$. In MDPA, tour sequence and orientation angles are computed in an integrated manner. It is shown that the ABA and MDPA are constant factor approximation algorithms and ABA provides an improved upper bound as compared to Alternating Algorithm (AA) \cite{savla2008traveling}. Through numerical simulations, we show that ABA provides an improved tour length compared to AA, Single Vehicle Algorithm (SVA) \cite{rathinam2007resource} and Optimized Heading Algorithm (OHA) \cite{babel2020new,manyam2018tightly} when the Euclidean distance between any two points in the given set of points is at least $4\rho$ where $\rho$ is the minimum turning radius. The time complexity of ABA is comparable with AA and SVA and is better than OHA. Also we show that MDPA provides an improved tour length compared to AA and SVA and is comparable with OHA when there is no constraint on Euclidean distance between the points. In particular, ABA gives a tour length which is at most $4\%$ more than the ETSP tour length when the Euclidean distance between any two points in the given set of points is at least $4\rho$.