Parallel Three-Dimensional Distance Transform for Railway Alignment Optimization Using OpenMP
Publication: Journal of Transportation Engineering, Part A: Systems
Volume 146, Issue 5
Abstract
Railway alignment optimization is a large-scale and time-consuming civil engineering problem. To solve it, a three-dimensional distance transform (3D-DT) algorithm, which is a variant of the three-dimensional Euclidean distance transform (3D-EDT), was previously designed. However, that algorithm is quite computationally intensive. In addition, the 3D-DT is inherently sequential, and it is thus challenging to parallelize. Thus, this study focuses on improving the sequential 3D-DT by transforming it into a parallel one. First, existing representative parallel EDT methods are reviewed and assessed. Then the railway alignment optimization model and the sequential 3D-DT are described. After that, critical execution properties of the 3D-DT that significantly influence its parallelization are explored in depth. Lastly, a novel so-called parallel linkage method is presented. This parallel implementation, which is developed using the OpenMP library, is highly effective and scalable by fully exploiting the parallelism of the algorithm. Using this parallel 3D-DT method, a large-scale, real-world railway case is tested and analyzed in detail. The outcomes verify that the proposed parallel method can accelerate the optimization process significantly without reducing the quality of computation results.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Some or all data, models, or code generated or used during the study are proprietary or confidential in nature and may only be provided with restrictions. All design data for the case study presented here, such as topography, satellite imagery, and land cover, are provided by the China Railway First Survey and Design Institute Group Co. Ltd. These data were provided to support this research project, but detailed information cannot be presented in this paper because the proprietary rights belong to that company.
Acknowledgments
This work was partially funded by the National Science Foundation of China (NSFC) with Awards 51778640, 51608543, 51378512, and 51678574, the National Key Research and Development (R&D) Program of China with Award 2017YFB1201102, the Natural Science Foundation of Hunan Province of China with Award 2017JJ3382, the China Railway Eryuan Engineering Group Co. Ltd. with Award 2015-41, the State Key Laboratory of Rail Transit Engineering Informatization (FSDI) with Award SKLK18-04, and the China Railway Siyuan Survey and Design Group Co. Ltd. with Award 2016D02-1. The authors are very grateful to the State Key Laboratory of Rail Transit Engineering Informatization, the China Railway Eryuan Engineering Group Co. Ltd., the China Railway Siyuan Survey and Design Group Co. Ltd., and China Railway First Survey and Design Institute Group Co. Ltd. for their support on many real cases.
References
Amdahl, G. M. 1967. “Validity of the single processor approach to achieving large scale computing capabilities.” In Proc., AFIPS 1967 Spring Joint Computer Conf. 30 (April), 483–485. Reston, VA: AFIPS Press.
Arcelli, C., G. S. D. Baja, and L. Serino. 2009. “A parallel algorithm to skeletonize the distance transform of 3D objects.” Image Vision Comput. 27 (6): 666–672. https://doi.org/10.1016/j.imavis.2008.07.014.
Babapour, R., R. Naghdi, I. Ghajar, and Z. Mortazavi. 2018. “Forest road profile optimization using meta-heuristic techniques.” Appl. Soft Comput. 64 (Mar): 126–137. https://doi.org/10.1016/j.asoc.2017.12.015.
Bruno, O. M., and L. D. F. Costa. 2004. “A parallel implementation of exact Euclidean distance transform based on exact dilations.” Microprocess. Microsys. 28 (3): 107–113. https://doi.org/10.1016/j.micpro.2004.01.001.
Chen, L., and H. Y. H. Chuang. 1995. An efficient algorithm for complete Euclidean distance transform on mesh-connected SIMD. Amsterdam, Netherlands: Elsevier.
Chen, L., Y. Pan, Y. Chen, and X. H. Xu. 2004. “Efficient parallel algorithms for Euclidean distance transform.” Comput. J. 47 (6): 694–700. https://doi.org/10.1093/comjnl/47.6.694.
Cheng, J. F., and Y. Lee. 2006. “Model for three-dimensional highway alignment.” J. Transp. Eng. 132 (12): 913–920. https://doi.org/10.1061/(ASCE)0733-947X(2006)132:12(913).
Chew, E. P., C. J. Goh, and T. F. Fwa. 1989. “Simultaneous optimization of horizontal and vertical alignments for highways.” Transp. Res. Part B: Methodol. 23 (5): 315–329. https://doi.org/10.1016/0191-2615(89)90008-8.
Chia, T. L., K. B. Wang, Z. Chen, and D. C. Lou. 2002. “Parallel distance transforms on a linear array architecture.” Inf. Process. Lett. 82 (2): 73–81. https://doi.org/10.1016/S0020-0190(01)00250-2.
China Ministry of Railways. 2017. Code for design of railway line. Beijing: China Railway Publishing House.
China Railway First Survey and Design Institute Group. 1999. China railway engineering design manual-alignment. Beijing: China Railway Press.
Davey, N., S. Dunstall, and S. Halgamuge. 2017. “Optimal road design through ecologically sensitive areas considering animal migration dynamics.” Transp. Res. Part C: Emerging Technol. 77 (Apr): 478–494. https://doi.org/10.1016/j.trc.2017.02.016.
de Smith, M. J. 2006. “Determination of gradient and curvature constrained optimal paths.” Comput.-Aided Civ. Infrastruct. Eng. 21 (1): 24–38. https://doi.org/10.1111/j.1467-8667.2005.00414.x.
Easa, S. M. 1988. “Selection of roadway grades that minimize earthwork cost using linear programming.” Transp. Res. Part A: Gen. 22 (2): 121–136. https://doi.org/10.1016/0191-2607(88)90024-6.
Gavrilova, M. L., and M. H. Alsuwaiyel. 2003. “Computing the euclidean distance transform on a linear array of processors.” J. Supercomputing 25 (2): 177–185. https://doi.org/10.1023/A:1023948712732.
Hayman, R. W. 1970. “Optimization of vertical alignment for highways through mathematical programming.” Highway Res. Rec. 306: 1–9.
Hesselink, W. H., and J. B. T. M. Roerdink. 2008. “Euclidean skeletons of digital image and volume data in linear time by the integer medial axis transform.” IEEE Trans. Pattern Anal. Mach. Intell. 30 (12): 2204–2217. https://doi.org/10.1109/TPAMI.2008.21.
Hirpa, D., W. Hare, Y. Lucet, Y. Pushak, and S. Tesfamariam. 2016. “A bi-objective optimization framework for three-dimensional road alignment design.” Transp. Res. Part C: Emerging Technol. 65 (Apr): 61–78. https://doi.org/10.1016/j.trc.2016.01.016.
Hogan, J. D. 1973. “Experience with OPTLOC: Optimum location of highway by computer.” In PTRC Seminar Proc. on Cost Models and Optimization in Highways (Session L10). Washington, DC: Transportation Research Board.
Howard, B. E., Z. Bramnick, and J. F. B. Shaw. 1968. “Optimum curvature principle in highway routing.” J. Highway Div. 94 (HW1): 61–82.
Jha, M. K., and P. Schonfeld. 2004. “A highway alignment optimization model using geographic information systems.” Transp. Res. Part A: Policy Pract. 38 (6): 455–481.
Jha, M. K., P. Schonfeld, and S. Samanta. 2007. “Optimizing rail transit routes with genetic algorithms and geographic information system.” J. Urban Plann. Dev. 133 (3): 161–171. https://doi.org/10.1061/(ASCE)0733-9488(2007)133:3(161).
Jin, H., D. Jespersen, P. Mehrotra, R. Biswas, L. Huang, and B. Chapman. 2011. “High Performance computing using MPI and OpenMP on multi-core parallel systems.” Parallel Comput. 37 (9): 562–575. https://doi.org/10.1016/j.parco.2011.02.002.
Jong, J. C., and P. Schonfeld. 2003. “An evolutionary model for simultaneously optimizing three-dimensional highway alignments.” Transp. Res. Part B: Methodol. 37 (2): 107–128. https://doi.org/10.1016/S0191-2615(01)00047-9.
Kang, M., M. Jha, and P. Schonfeld. 2012. “Applicability of highway alignment optimization models.” Transp. Res. Part C: Emerging Technol. 21 (1): 257–286. https://doi.org/10.1016/j.trc.2011.09.006.
Kang, M., P. Schonfeld, and N. Yang. 2009. “Prescreening and repairing in a genetic algorithm for highway alignment optimization.” Comput.-Aided Civ. Infrastruct. Eng. 24 (2): 109–119. https://doi.org/10.1111/j.1467-8667.2008.00574.x.
Lee, Y., Y. R. Tsou, and H. L. Liu. 2009. “Optimization method for highway horizontal alignment design.” J. Transp. Eng. 135 (4): 217–224. https://doi.org/10.1061/(ASCE)0733-947X(2009)135:4(217).
Li, C., L. Ding, and B. Zhong. 2019a. “Highway planning and design in the Qinghai–Tibet Plateau of China: A cost–safety balance perspective.” Engineering 5 (2): 337–349. https://doi.org/10.1016/j.eng.2018.12.008.
Li, W., H. Pu, P. Schonfeld, Z. Song, H. Zhang, L. Wang, J. Wang, X. Peng, and L. Peng. 2019b. “A method for automatically recreating the horizontal alignment geometry of existing railways.” Comput.-Aided Civ. Infrastruct. Eng. 34 (1): 71–94. https://doi.org/10.1111/mice.12392.
Li, W., H. Pu, P. Schonfeld, J. Yang, H. Zhang, L. Wang, and J. Xiong. 2017. “Mountain railway alignment optimization with bidirectional distance transform and genetic algorithm.” Comput.-Aided Civ. Infrastruct. Eng. 32 (8): 691–709. https://doi.org/10.1111/mice.12280.
Li, W., H. Pu, P. Schonfeld, H. Zhang, and X. Zheng. 2016. “Methodology for optimizing constrained 3-dimensional railway alignments in mountainous terrain.” Transp. Res. Part C: Emerging Technol. 68 (Jul): 549–565. https://doi.org/10.1016/j.trc.2016.05.010.
Li, W., H. Pu, H. Zhao, and W. Liu. 2013. “Approach for optimizing 3D highway alignments based on two-stage dynamic programming.” J. Software 8 (11): 2967–2973.
Migallón, H., V. Migallón, and J. Penadés. 2018. “Parallel two-stage algorithms for solving the PageRank problem.” Adv. Eng. Software 10.1016/j.advengsoft.2018.03.002.
Mondal, S., Y. Lucet, and W. Hare. 2015. “Optimizing horizontal alignment of roads in a specified corridor.” Comput. Oper. Res. 64 (C): 130–138. https://doi.org/10.1016/j.cor.2015.05.018.
Nikolić, M., M. Hajduković, D. D. Milašinović, D. Goleš, P. Marić, and Ž. Živanov. 2015. “Hybrid MPI/OpenMP cloud parallelization of harmonic coupled finite strip method applied on reinforced concrete prismatic shell structure.” Adv. Eng. Software 84 (Jun): 55–67. https://doi.org/10.1016/j.advengsoft.2014.12.006.
Oh, S. E., and J. W. Hong. 2017. “Parallelization of a finite element Fortran code using OpenMP library.” Adv. Eng. Software 104 (Feb): 28–37. https://doi.org/10.1016/j.advengsoft.2016.11.004.
Parker, N. A. 2007. “Rural highway route corridor selection.” Transp. Plann. Technol. 3 (4): 247–256. https://doi.org/10.1080/03081067708717111.
Pradhan, A., and G. Mahinthakumar. 2013. “Finding all-pairs shortest path for a large-scale transportation network using parallel floyd-warshall and parallel dijkstra algorithms.” J. Comput. Civ. Eng. 27 (3): 263–273. https://doi.org/10.1061/(ASCE)CP.1943-5487.0000220.
Pu, H., T. Song, P. Schonfeld, W. Li, H. Zhang, J. Hu, X. Peng, and J. Wang. 2019a. “Mountain railway alignment optimization using stepwise & hybrid particle swarm optimization incorporating genetic operators.” Appl. Soft Comput. 78 (May): 41–57. https://doi.org/10.1016/j.asoc.2019.01.051.
Pu, H., T. Song, P. Schonfeld, W. Li, H. Zhang, J. Wang, J. Hu, and X. Peng. 2019b. “A three-dimensional distance transform for optimizing constrained mountain railway alignments.” Comput.-Aided Civ. Infrastruct. Eng. 34 (11): 972–990. https://doi.org/10.1111/mice.12475.
Pu, H., H. Zhang, W. Li, J. Xiong, J. Hu, and J. Wang. 2018. “Concurrent optimization of mountain railway alignment and station locations using a distance transform algorithm.” Comput. Ind. Eng. 127 (Jan): 1297–1314.
Pu, H., H. Zhang, P. Schonfeld, W. Li, J. Wang, X. Peng, and J. Hu. 2019c. “Maximum gradient decision-making for railways based on convolutional neural network.” J. Transp. Eng. Part A: Syst. 145 (11): 04019047. https://doi.org/10.1061/JTEPBS.0000272.
Pushak, Y., W. Hare, and Y. Lucet. 2016. “Multiple-path selection for new highway alignments using discrete algorithms.” Eur. J. Oper. Res. 248 (2): 415–427. https://doi.org/10.1016/j.ejor.2015.07.039.
Revelle, C. S., E. Whitlach, and J. Wright. 1996. Civil and environmental systems engineering. Upper Saddle River, NJ: Prentice Hall PTR.
Robinson, R. 1973. “Automatic design of the road vertical alignment.” In PTRC Seminar Proc. on Cost Models and Optimisation in Highways (Session L19). Washington, DC: Transportation Research Board.
Rosenfeld, A. 1966. “Sequential operations in digital picture processing.” J. ACM 13 (4): 471–494.
Shafahi, Y., and M. Bagherian. 2013. “A customized particle swarm method to solve highway alignment optimization problem.” Comput.-Aided Civ. Infrastruct. Eng. 28 (1): 52–67. https://doi.org/10.1111/j.1467-8667.2012.00769.x.
Shaw, J., and B. E. Howard. 1982. “Expressway route optimization by OCP.” J. Transp. Eng. 108 (3): 227–243.
Shaw, J. F. B., and B. E. Howard. 1981. “Comparison of two integration methods in transportation routing.” Transp. Res. Rec. 806: 8–13.
State Bureau of Surveying and Mapping of China. 2008. Quality requirement for digital surveying and mapping achievements. Beijing: Standardization Administration of China.
Takala, J. H., and J. O. Viitanen. 1999. Distance transform algorithm for bit-serial SIMD architectures. Amsterdam, Netherlands: Elsevier.
Thomson, N. R., and J. F. Sykes. 1988. “Route selection through a dynamic ice field using the maximum principle.” Transp. Res. Part B: Methodol. 22 (5): 339–356. https://doi.org/10.1016/0191-2615(88)90039-2.
Torelli, J. C., R. Fabbri, G. Travieso, and O. M. Bruno. 2011. “A high performance 3D exact euclidean distance transform algorithm for distributed computing.” Int. J. Pattern Recognit Artif Intell. 24 (06): 897–915. https://doi.org/10.1142/S0218001410008202.
Trietsch, D. 1987a. “A family of methods for preliminary highway alignment.” Transp. Sci. 21 (1): 17–25. https://doi.org/10.1287/trsc.21.1.17.
Trietsch, D. 1987b. “Comprehensive design of highway network.” Transp. Sci. 21 (1): 26–35. https://doi.org/10.1287/trsc.21.1.26.
Turner, A. K., and R. D. Miles. 1971. “A computer-assisted method of regional route location.” Highway Res. Rec. 348: 1–15.
Turner, E. L., and H. Hu. 2001. “A parallel CFD rotor code using OpenMP.” Adv. Eng. Software 32 (8): 665–671. https://doi.org/10.1016/S0965-9978(01)00013-8.
Vázquez-Méndez, M. E., G. Casal, D. Santamarina, and A. Castro. 2018. “A 3D model for optimizing infrastructure costs in road design.” Comput.-Aided Civ. Infrastruct. Eng. 33 (5): 423–439. 10.1111/mice.12350.
Wagoum, A. U. K., B. Steffen, A. Seyfried, and M. Chraibi. 2013. “Parallel real time computation of large scale pedestrian evacuations.” Adv. Eng. Software 60–61 (6): 98–103. https://doi.org/10.1016/j.advengsoft.2012.10.001.
Wright, P. H. 1996. Highway engineering. New York: Wiley.
Yang, N., M. W. Kang, P. Schonfeld, and M. K. Jha. 2014. “Multi-objective highway alignment optimization incorporating preference information.” Transp. Res. Part C: Emerging Technol. 40 (Mar): 36–48. https://doi.org/10.1016/j.trc.2013.12.010.
Information & Authors
Information
Published In
Journal of Transportation Engineering, Part A: Systems
Volume 146 • Issue 5 • May 2020
Copyright
©2020 American Society of Civil Engineers.
History
Received: Jul 11, 2019
Accepted: Oct 11, 2019
Published online: Feb 26, 2020
Published in print: May 1, 2020
Discussion open until: Jul 26, 2020
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.