Application of Adaptive Parallel Fast Marching Method in Automatic Submarine Cable Path Planning

Submarine optical fiber communication cables (subsequently referred to as submarine cables) form the backbone of the Internet’s infrastructure. Damage to these cables can precipitate Internet outages with far-reaching socio-economic impacts. The prevailing practice of manual cable routing is laborious, considering the thousands of kilometers these cables span. It also fails to strike an optimal balance between cost and risk due to its lack of scalability and precision. The Fast Marching Method (FMM), a non-iterative, precise numerical approach capable of solving the Eikonal equation, offers a viable alternative by optimizing the required path between source and destination, considering a summary objective function of costs and risk factors. An interpretation of its solution signifies the optimum value of the objective function between a starting point and all other points. However, the sequential nature of the FMM algorithm suffers from computational limitations and impedes direct parallelization. In this study, we introduce an Adaptive Parallel FMM (APFMM), an innovative approach utilizing adaptive domain decomposition and dynamic multi-resolution analysis. This scalable and widely applicable method can overcome the limitations of existing methods and achieve planning of high-precision, ultra-long-distance (over 14,000 km) submarine cable routes over the Earth’s surface. Simulated experiment results corroborate that APFMM effectively overcomes the computational challenges posed by the sequential FMM when dealing with large datasets. Additionally, it reduces the running time by more than 81% compared to the traditional parallel FMM. This marks a substantial advancement in facilitating efficient, automated, high-precision planning for long-distance submarine cable paths. Note to Practitioners—This paper introduces APFMM, a novel technique based on adaptive domain decomposition and multi-resolution analysis, facilitating high-precision, ultra-long-distance (over 14,000 km) submarine cable path planning. Results from simulated experiments show that APFMM not only overcomes the computational constraints associated with the sequential FMM for large datasets but also cuts the running time by more than 81% relative to the conventional parallel FMM. This breakthrough improvement holds significant implications for practitioners in submarine cable design and construction. With the use of APFMM, designers can plan and optimize cable paths more efficiently, thereby lowering cabling costs and enhancing network resilience. Furthermore, the application of APFMM is not limited to submarine cable path planning and can be employed in other domains involving large-scale data processing and complex path planning, such as electricity cables, gas pipelines, and transportation route planning. While our focus in this paper is primarily on submarine cable path planning, we anticipate practitioners extending the application of APFMM to other use cases, realizing broader utility and benefits.