This paper addresses the Forward Shortest Path Tour Problem (FSPTP). Given a weighted directed graph, whose nodes are partitioned into clusters, the FSPTP consists of finding a shortest path from a source node to a destination node and which crosses all the clusters in a fixed order. We propose a polynomial time algorithm to solve the problem and show that our algorithm can be easily adapted to solve the shortest path tour problem, a slightly different variant of the FSPTP. Moreover, we carried out some preliminary computational tests to verify how the performance of the algorithm is affected by parameters of the instances.
|Titolo:||On the Forward Shortest Path Tour Problem|
|Data di pubblicazione:||2017|
|Appare nelle tipologie:||2.1.2 Articolo su libro con ISBN|