Solving the shortest path tour problem

In this paper, we study the shortest path tour problem in which a shortest path from a given origin node to a given destination node must be found in a directed graph with non-negative arc lengths. Such path needs to across a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be different-sized. A polynomial reduction of the problem to a classical shortest path problem over a modified digraph is described and two solution approaches based on the above reduction and Dynamic Programming, respectively, are proposed and compared with the state-of-the-art solving procedure. The proposed approaches are tested on existing datasets for this problem and on a large class of new benchmark instances. The computational experience shows that both the proposed approaches exhibit a consistent improved performance in terms of computational time with respect to the existing solving method