A Hierarchical Approach for the Shortest Path Problem with Obligatory Intermediate Nodes

A new problem, the shortest path problem with obligatory intermediate nodes (or SPOIN, for short) that is significant in wide range of applications is proposed in this paper. The main difference between the SPOIN and existing constrained shortest path problems is that the final path in the SPOIN should pass through all specified intermediate nodes without constraint of their sequence. A hierarchical approach with Floyd algorithm and genetic algorithm is designed to solve it, and the experimental results prove that our approach is feasible and effective