Underground Metro Interstation Horizontal-Alignment Optimization with an Augmented Rapidly Exploring Random-Tree Connect Algorithm
Publication: Journal of Transportation Engineering, Part A: Systems
Volume 146, Issue 11
Abstract
The design of an underground metro alignment in an urban area is complex and challenging. The metro alignment constantly invades districts with high-density buildings and specially planned districts, which results in large additional expenses due to reconstruction, land requisition, demolition, vibration absorption, and environmental protection. This paper presents a method for the optimization of the horizontal alignment between metro stations to minimize the overall cost. The proposed method includes three steps: (1) low-cost path search, (2) initial horizontal alignment generation, and (3) horizontal alignment optimization. First, an augmented rapidly exploring random-tree connect (RRT-connect) algorithm is developed to search for a low-cost path, in which the buffer zone of the low-cost path defines the corridor constraint of the horizontal alignment optimization. Subsequently, based on the low-cost path, an initial horizontal alignment is generated that determines the number of design variables, i.e., intersection points. Next, within the corridor constraint, the method optimizes the intersection point coordinates and curve radius on the initial horizontal alignment using a differential evolution (DE) algorithm. A real-world metro line was studied to verify the effectiveness of the proposed optimization approach.
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 be provided only with restrictions. The station information and land plan map of Line 11 are anonymized data. The unit costs in Table 3 are suitable only for the gross budget estimate. The topographic map, Line11 horizontal alignment coordinates, and unit cost of the actual subitems are proprietary. Open-source osgEarth version 2.10 and GEOS version 3.7.3 can be downloaded from the corresponding official websites.
Acknowledgments
The authors express their gratitude to Jason Beverage for GIS support with osgEarth and to the GEOS steering committee for providing spatial analysis support. The China Railway Eryuan Engineering Group is acknowledged for providing detailed project data of the Metro Line 11 in Foshan city. This project is partially supported by National Natural Science Foundation of China award No. 51878576.
References
Bennett, W. T. O., and D. W. O’Brien. 1969. “A dynamic programming approach to optimal route location.” In Proc., Symp. of Cost Models and Optimization in Road Location, Design, and Construction, 236–241. Washington, DC: Transportation Research Board.
Booto G. K., H. R. Vignisdottir, G. Marinelli, H. Brattebø, and R. A. Bohne. 2020. “Optimizing road gradients regarding earthwork cost, fuel cost, and tank-to-wheel emissions.” J. Transp. Eng. Part A: Syst. 146(3):1–13. https://doi.org/10.1061/JTEPBS.0000289.
Das, S., and P. N. Suganthan. 2011. “Differential evolution: A survey of the state-of-the-art.” IEEE Trans. Evol. Comput. 15 (1): 4–31. https://doi.org/10.1109/TEVC.2010.2059031.
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.
Fwa, T. F. 1989. “Highway vertical alignment analysis by dynamic programming.” Transp. Res. Rec. 1239 (1): 1–9.
Howard, B. E., Z. Bramnick, and J. F. B. Shaw. 1968. “Optimum curvature principle in highway routing.” J. Highway Div. 94 (1): 61–82.
Jaillet, L., J. Cortés, and T. Siméon. 2008. “Transition-based RRT for path planning in continuous cost spaces.” In Proc., 2008 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, IROS (Section V), 2145–2150. New York: IEEE.
Jha, M. K., M. Cyrus, and P. Schonfeld. 2001. “Using GIS, genetic algorithms, and visualization in highway development.” Comput.-Aided Civ. Infrastruct. Eng. 16 (6): 399–414. https://doi.org/10.1111/0885-9507.00242.
Jha, M. K., S. Paul, 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).
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. M. Schonfeld, J. C. Jong, and E. Ki. 2006. Intelligent road design. Southampton, UK: WIT Press.
Jong, J. C., M. K. Jha, and P. Schonfeld. 2000. “Preliminary highway design with genetic algorithms and geographic information systems.” Comput.-Aided Civ. Infrastruct. Eng. 15 (4): 261–271. https://doi.org/10.1111/0885-9507.00190.
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. W., M. K. 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. W., P. Schonfeld, and J. C. Jong. 2007. “Highway alignment optimization through feasible gates.” J. Adv. Transp. 41 (2): 115–144. https://doi.org/10.1002/atr.5670410202.
Kang, M. W., 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.
Kenneth, V. P., R. M. Storn, and J. A. Lampinen. 2005. Differential evolution a practical approach to global optimization. Berlin: Springer.
Kim, E., M. K. Jha, and P. Schonfeld. 2004. “Intersection construction cost functions for alignment optimization.” J. Transp. Eng. 130 (2): 194–203. https://doi.org/10.1061/(ASCE)0733-947X(2004)130:2(194).
Kim, M., and E. Kim. 2020. “Simulation-based multistage optimization model for railroad alignment design and operations.” J. Transp. Eng. Part A: Syst. 146 (7): 1–9.
Kim, M., N. Marković, and E. Kim. 2019. “A vertical railroad alignment design with construction and operating costs.” J. Transp. Eng. Part A: Syst. 145 (10): 1–8. https://doi.org/10.1061/JTEPBS.0000269.
Kim, M., P. Schonfeld, and E. Kim. 2013. “Simulation-based rail transit optimization model.” Transp. Res. Rec. 2374 (1): 143–153. https://doi.org/10.3141/2374-17.
Kuffner, J. J., and S. M. LaValle. 2000. “RRT-connect: An efficient approach to single-query path planning.” In Proc., IEEE Int. Conf. on Robotics and Automation, 995–1001. New York: IEEE.
Lai, X., and P. Schonfeld. 2012. “Optimization of rail transit alignments considering vehicle dynamics.” Transp. Res. Rec. 2275 (1): 77–87. https://doi.org/10.3141/2275-09.
Lai, X., and P. Schonfeld. 2016. “Concurrent optimization of rail transit alignments and station locations.” Urban Rail Transit 2 (1): 1–15. https://doi.org/10.1007/s40864-016-0033-1.
Lampinen, J. 2002. “A constraint handling approach for the differential evolution algorithm.” In Proc., 2002 Congress on Evolutionary Computation, CEC 2002, 1468–1473. New York: IEEE.
LaValle, S. M. 1998. Rapidly-exploring random trees: A new tool for path planning. Rep. No. TR 98-11. Ames, IA: Iowa State Univ.
Li, W., H. Pu, P. Schonfeld, Z. Song, H. Zhang, L. Wang, J. Wang, X. Peng, and L. Peng. 2019. “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.
Mao, B., and X. Li. 2013. Train performance calculation and design. Beijing: China Communications Press.
Moreb, A. A. 1996. “Linear programming model for finding optimal roadway grades that minimize earthwork cost.” Eur. J. Oper. Res. 93 (1): 148–154. https://doi.org/10.1016/0377-2217(95)00095-X.
NFPA (National Fire Protection Association). 2014. Standard for fixed guideway transit and passenger rail systems. Quincy, MA: NFPA.
Nicholson, A. J., D. G. Elms, and A. Williman. 1976. “A variation approach to optimal route location.” Highway Eng. 23 (3): 22–25.
Parker, N. A. 1977. “Rural highway route corridor selection.” Transp. Plann. Technol. 3 (4): 247–256. https://doi.org/10.1080/03081067708717111.
Pu, H., T. Song, P. Schonfeld, W. Li, H. Zhang, J. Hu, X. Peng, and J. Wang. 2019b. “Mountain railway alignment optimization using stepwise & hybrid particle swarm optimization incorporating genetic operators.” Appl. Soft Comput. J. 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. 2019a. “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. Z., Wei Li, J. Xiong, J. Hu, and J. Wang. 2019c. “Concurrent optimization of mountain railway alignment and station locations using a distance transform algorithm.” Comput. Indus. Eng. 127 (Jan): 1297–1314. https://doi.org/10.1016/j.cie.2018.01.004.
Samanta, S., and M. K. Jha. 2011. “Modeling a rail transit alignment considering different objectives.” Transp. Res. Part A: Policy Pract. 45 (1): 31–45. https://doi.org/10.1016/j.tra.2010.09.001.
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, F. B., and B. E. Howard. 1982. “Expressway route optimization by OCP.” Transp. Eng. J. 108 (3): 227–243.
Song, T., H. Pu, W. Li, H. Zhang, Y. Ren, P. Schonfeld, J. Wang, J. Hu, and X. Peng. 2020. “Parallel three-dimensional distance transform for railway alignment optimization using open MP.” J. Transp. Eng. Part A: Syst. 146 (5): 1–15. https://doi.org/10.1061/JTEPBS.0000344.
Storn, R., and K. Price. 1997. “Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces.” Australas. Plant Pathol. 38 (3): 284–287. https://doi.org/10.1023/A:1008202821328.
Sushma, M. B., and A. Maji. 2020. “A modified motion planning algorithm for horizontal highway alignment development.” Comput.-Aided Civ. Infrastruct. Eng. 35 (8): 818–831. https://doi.org/10.1111/mice.12534.
Trietsch, D. 1987. “Family of methods for preliminary highway alignment.” Transp. Sci. 21 (1): 17–25. https://doi.org/10.1287/trsc.21.1.17.
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 11 • November 2020
Copyright
© 2020 American Society of Civil Engineers.
History
Received: Feb 13, 2020
Accepted: Jun 26, 2020
Published online: Sep 7, 2020
Published in print: Nov 1, 2020
Discussion open until: Feb 7, 2021
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.