In this paper we study minimum-time motion planning and routing problems for the Dubins vehicle, i.e., a nonholonomic vehicle that is constrained to move along planar paths of bounded curvature, without reversing direction. Motivated by autonomous aerial vehicle applications, we consider the Traveling Salesperson Problem for the Dubins vehicle (DTSP): given n points on a plane, what is the shortest Dubins tour through these points and what is its length? First, we show that the worst-case length of such a tour grows linearly with n and we propose a novel algorithm with worst-case performance within a constant factor approximation of the optimum. In doing this, we also obtain an upper bound on the optimal length in the classical point-to-point problem. Second, we study a stochastic version of the DTSP where the n targets are randomly sampled from a uniform distribution. We show that the expected length of such a tour is of order at least n^(2/3) and we propose a novel algorithm yielding a solution with length of order n^(2/3) with high probability. Third and finally, we study a dynamic version of the DTSP: given a stochastic process that generates target points, is there a policy which guarantees that the number of unvisited points does not diverge over time? If such stable policies exist, what is the minimum expected time that a newly generated target waits before being visited by the vehicle? We propose a novel stabilizing algorithms such that the expected wait time is provably within a constant factor from the optimum.[PDF]