Submarine optical fiber cables (hereafter submarine cables) are the lifeblood of global communications, carrying more than 99% of the international data traffic. With more than 1.4 million kilometers of active and planned submarine cable systems, this infrastructure represents a substantial financial investment and is critical to our digital future. The submarine cable market is projected to grow to approximately 41.02 billion USD by 2032, and increasing investment in the sector by tech giants and governments underscores the growing importance of this infrastructure.

Considering the pivotal role of submarine cables and the potential for widespread socio-economic impact in the event of damage leading to Internet outages, it's crucial to meticulously plan their paths, taking into account various design considerations that influence cost-effectiveness and reliability. Yet, the current practice of manual cable path planning is exceedingly labor-intensive, especially considering the extensive distances these cables traverse. To get out of this mess, this thesis is dedicated to exploring and developing innovative methods for submarine cable path planning, therefore enhancing the level of automation, precision, and efficiency in the process.

In the first of our series of studies, we introduced an algorithm named Fast Marching Method/Simulated Annealing (FMM/SA), specifically designed for automatic cable path planning in a triangulated piecewise-linear two-dimensional manifold Earth's surface model. In particular, we assign to each point on the manifold a three-dimensional coordinate representing the latitude, longitude, and elevation of this point. During the implementation process of FMM/SA, SA utilizes a real-life, cost-effective, and resilient submarine cable path to derive practical weights for various design considerations by minimizing the Fréchet distance between the real-life cable path and those paths with minimal total life-cycle cost obtained by FMM. Note that these design considerations encompass a wide array of factors, including but not limited to basic cable construction cost, geological hazards (namely earthquakes), water depth, seabed slope, and anthropological hazards (fishing and anchoring activities). The weights of these design considerations are then integrated with the FMM, which performs the path planning optimization based on the weights obtained from SA. The close matching between the cable path produced by FMM/SA (using the weights we obtained from the first real-life cable path) and another existing cable path indicates that our research could provide a foundational step in establishing a standardized approach to cable path creation. Moreover, the FMM/SA algorithm we propose provides insights into the prioritization and preferences of different design considerations utilized by planners, thereby fostering automation in submarine cable path planning.

Our research trajectory was heavily influenced by the Hunga Tonga-Hunga Ha'apai volcano eruption in 2022, which destroyed a Tonga-Fuji cable path of around 80 kilometers. This caused Tonga to completely lose communication with the outside world for about one month, an event which subsequently led us to undertake a second study. Here, we incorporate a volcano-related risk factor, as well as other considerations, into the process of path planning for submarine cables. To consider the impact of volcanoes, we introduce constraints based on keeping a safe distance from each volcano. We evaluated the cost and risk of the existing Tonga-Fiji cable, offering alternative Pareto optimal paths for cost and risk under varying volcano safe distances. Using our automated path planning methodology, we demonstrated the potential for significant cost savings and risk reduction compared to the real-life Tonga-Fiji cable, affirming our FMM-based method's ability to generate optimal cable paths given the data, taking account of volcano-related risk and other considerations.

While FMM yields promising results, it does face computational limitations when dealing with massive data sizes, particularly in the context of ultra-long and high-precision submarine cable path planning. The inherently sequential nature of FMM also hampers parallelization, a commonly employed technique for managing large-scale data and accelerating computations. This leads us to our third study, wherein we propose an Adaptive Parallel Fast Marching Method (APFMM).

Based on the principles of adaptive domain decomposition and multi-resolution analysis, APFMM dynamically segments the target area and adjusts the resolution of various sub-domains throughout its implementation. This approach targets the computational challenges posed by massive datasets within large target regions. A key difference of our APFMM from general parallel FMMs is its ability to ensure a balanced workload distribution across different computing threads to some degree and minimize the frequency of communication between adjacent sub-domains (i.e., the number of rollback operations). As a result, our APFMM optimizes the utilization of all threads as much as possible, leading to a substantial improvement in computational efficiency and making efficient, automatic, and high-precision long-distance submarine cable path planning a tangible possibility.

To conclude, this thesis presents innovative submarine cable path planning methods, which take into account various design considerations and harness the power of parallel computing. The proposed methods enable us to understand the priorities and preferences of the various design considerations adopted by planners and address the computational limitations of the sequential FMM when dealing with massive data size, ultimately helping achieve automation of ultra-long and high-precision submarine cable path planning. This will undoubtedly facilitate more efficient planning for future submarine cable path planning and is paramount in maintaining and strengthening our interconnected world, particularly in light of the increasing demands for data transmission. Moreover, our methods proposed in this thesis have far-reaching potential for application in other scenarios requiring path planning, such as oil and gas pipelines and electrical power cables. We fervently hope that the methods proposed in this thesis will advance related industrial fields and contribute to creating a better and more connected world.