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.