The ripple-spreading algorithm for shortest path tour problems

The shortest path tour problem (SPTP) aims to find the shortest path traversing multiple disjoint vertex subsets in a specified sequence. The SPTP has diverse real-world applications, including warehouse management and network function virtualization. Inspired by ripple patterns observed on water surfaces, this paper proposes a ripple-spreading algorithm (RSA) and an RSA-specific decomposition method to efficiently address the SPTP. Unlike existing decomposition-based methods, the RSA establishes explicit connections among SPTP subproblems, thereby eliminating the need to compute shortest paths between all source-target pairs in each subproblem. Complexity analysis demonstrates that RSA’s running time does not explicitly depend on the total number of vertices, indicating particular efficiency on sparse graphs. Leveraging RSA’s inherent flexibility, we extend it to solve generalized SPTPs involving multiple sources and targets (many-to-many SPTP) and the k shortest paths problem (k-SPTP). To the best of our knowledge, no other effective algorithm currently exists for these two variants. Computational experiments conducted on various graph topologies highlight RSA’s superior efficiency. Notably, RSA solves the many-to-many SPTP with the same complexity as the standard SPTP. Furthermore, an illustrative example confirms RSA’s capability to handle the k-SPTP, complemented by an approximate method to further enhance efficiency. These findings demonstrate that RSA provides an effective and scalable solution framework for real-world problems modeled as SPTPs.

Authors

• Yiming Ma
• Xiao-Bing Hu
• Hang Zhou Huazhong University of Science and Technology
• Ying-Fei Zhang
• Da-Qing Li
• Gong-Peng Zhang
• Ezequiel A Di Paolo
• Mark S. Leeson

Keywords

• Shortest path tour problem
• k shortest paths
• Many-to-many path optimization
• Ripple-spreading algorithm
• Optimality