Towards an R Package for the Shortest Path Problem with Forbidden Paths

Abstract

The shortest path problem with forbidden paths (SPPFP) is a variant of the original shortest path problem. Given a directed graph 𝐺 = (𝑁, 𝐴), there is also a related set 𝐹 of known forbidden sub-paths in 𝐺. The problem is to find the shortest paths from a source to a destination node, with no paths in the solution contain forbidden sub-path. SPPFP has been addressed in the academic literature, and different solutions have been proposed. This problem has several lines of application in research, such as time windows networks, logistics, and more. R is a free- software environment for statistical computing and graphics, and its potential depends on the packages contributed to the project by the community; however no R packages includes the SPPFP.