Solving Physical Traveling Salesman Problems with policy adaptation

The Physical Traveling Salesman Problem (PTSP) is a current research problem which adds a model of velocity to the classic TSP. In this paper we propose algorithms for solving the PTSP which avoid the fragmented allocation of memory and precompute cell-precise single-source shortest paths for each waypoint by using an engineered implementation of Dijkstra´s algorithm. To determine an initial tour, we solve ordinary and general TSPs. For moderately sized problems, we apply an optimal depth-first branch-and-bound TSP solver which warrants constant-time per search tree node. For larger problems, we apply randomized search with policy adaptation to learn from good tours. We evaluate our solution with a series of benchmark experiments and compare the results to the winner of the PTSP competition at CIG 2013. In comparison, our approach shows similar results but also provides a graph search with optimal time performance.