Publications / 2020 Proceedings of the 37th ISARC, Kitakyushu, Japan

Comparison of Shortest Path Finding Algorithms for Cable Networks on Industrial Construction Projects

Fatima Alsakka, Salam Khalife, Maram Nomir, Yasser Mohamed and Rick Hermann
Pages 409-416 (2020 Proceedings of the 37th ISARC, Kitakyushu, Japan, ISBN 978-952-94-3634-7, ISSN 2413-5844)
Abstract:

Cable path optimization is a commonly encountered problem in industrial construction projects. Numerous designs are technically feasible but are associated with varying construction costs and effort. Hence, selecting the right network is deemed a critical decision. Multiple shortest path algorithms could be deployed to identify the optimal solution. Although they could potentially identify solutions of equal values, there could be differences among their performance which become more significant as the project size increases. Thus, this study compares the results of applying three shortest path algorithms, Dijkstra, A* and Bellman-Ford, in finding the shortest paths for power and instrument cables in an industrial facility project. Moreover, it presents an integrated methodology that combines different software to help practitioners experiment with different scenarios in a fast and systematic manner and make decisions accordingly: (1) Build a 3D model of the project under study, (2) Design a database for data retrieval and management, (3) Import data from the model into the database, (4) Develop a code that reads from the database, finds the optimal paths for the planned cables in the facility, and writes the results back into the database, and (5) Import the obtained results into NavisWorks for visualization and validation purposes. The results have shown that the three algorithms identified the same paths for six cables. Yet the optimal path found using Dijkstra and A* for the seventh cable was one node longer than that identified using Bellman-Ford, but the three paths were of equal weights. Generally, Dijkstra and A* exhibited a close performance. Meanwhile, the main difference between Dijkstra and A*, on one hand, and Bellman-Ford, on the other hand, lied in fact in the time needed to solve the optimization problem. The percent difference between Dijkstra and Bellman-Ford's runtimes for one of the cables reached 4,800% making Dijkstra superior with respect to runtime. Even though the impact of the runtime difference is considered insignificant within the scope of this study as it is in the range of milliseconds, its criticality would increase as the size of the network increases. Therefore, a proper selection of the optimization algorithm would support a rapid and efficient decision-making process.

Keywords: Cable Network; Shortest path algorithms; Optimal path; Nodes; Edges