On the Solution of the Travelling Salesman Problem for Nonlinear Salesman Dynamics using Symbolic Optimal Control
This addresses the problem of solving TSP with complex dynamics for applications like logistics and robotics, but it is incremental as it builds on existing symbolic control and TSP solvers.
The paper tackles the Travelling Salesman Problem with nonlinear dynamics by proposing a heuristic method based on symbolic control, which returns a provably correct state-feedback controller for coverage and uses the Lin-Kernighan-Helsgaun solver to optimize route cost, as demonstrated in urban delivery and UAV reconnaissance examples.
This paper proposes an algorithmic method to heuristically solve the famous Travelling Salesman Problem (TSP) when the salesman's path evolves in continuous state space and discrete time but with otherwise arbitrary (nonlinear) dynamics. The presented method is based on the framework of Symbolic Control. In this way, our method returns a provably correct state-feedback controller for the underlying coverage specification, which is the TSP leaving out the requirement for optimality on the route. In addition, we utilize the Lin-Kernighan-Helsgaun TSP solver to heuristically optimize the cost for the overall taken route. Two examples, an urban parcel delivery task and a UAV reconnaissance mission, greatly illustrate the powerfulness of the proposed heuristic.