Recursive Hybrid Heuristic Algorithm for Routing a Track-Geometry Car through a Large-Scale Urban Subway Network
Publication: Journal of Transportation Engineering, Part A: Systems
Volume 146, Issue 8
Abstract
Rail track inspection is essential to urban rail infrastructure management in terms of safety. The track geometry car is one of the important inspection vehicles for track condition measurement. Routing a track geometry car on a large-scale subway network has two objectives: inspection cost and inspection time interval consistency of each line during one planning horizon. An optimization model is developed to route a track geometry car on a large-scale subway network. Because of the model’s nondeterministic polynomial time (NP)-hardness, a recursive hybrid heuristic algorithm using a novel double-layer chromosome genetic algorithm as the global search strategy and a simulated annealing algorithm as the local search strategy are proposed to attain suboptimal inspection schedules. The proposed algorithm is applied to the Beijing subway network for two months, and the 877.260-km track mileage was inspected through one track geometry car. The schedule currently adopted in practice instructs Beijing subway’s track geometry car to complete all prescribed inspections at inconsistent time intervals in 23 days with a dead mileage of 601.180 km. The schedule attained via the proposed algorithm routes the track geometry car to inspect all tracks at consistent time intervals and saves 301.806-km of dead mileage (50.2%) and five days.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
The route map of the Beijing subway and the garage locations are illustrated in this paper. The track geometry car’s schedule currently used in practice is confidential. The code for the proposed recursive hybrid heuristic algorithm to solve the TGCRP is available from the corresponding author on request.
Acknowledgments
This research is supported by the National Natural Science Foundation of China (Nos. 71701009 and 91746201), Beijing Jiaotong University (No. 2019JBZ105), and the science and technology research and development program of China Railway’s “Intelligent Operation and Maintenance Technology for Beijing-Zhangjiakou HSR (No. P2018G051)” project. For this research, the Beijing subway provided the currently used track geometry car’s schedule.
References
Amaya, A., A. Langevin, and M. Trepanier. 2007. “The capacitated arc routing problem with refill points.” Oper. Res. Lett. 35 (1): 45–53. https://doi.org/10.1016/j.orl.2005.12.009.
Amponsah, S. K., and S. Salhi. 2004. “The investigation of a class of capacitated arc routing problems: The collection of garbage in developing countries.” Waste Manage. (Oxford) 24 (7): 711–721. https://doi.org/10.1016/j.wasman.2004.01.008.
Arakaki, R. K., and F. L. Usberti. 2018. “Hybrid genetic algorithm for the open capacitated arc routing problem.” Comput. Oper. Res. 90 (Feb): 221–231. https://doi.org/10.1016/j.cor.2017.09.020.
Arakaki, R. K., and F. L. Usberti. 2019. “An efficiency-based path-scanning heuristic for the capacitated arc routing problem.” Comput. Oper. Res. 103 (Mar): 288–295. https://doi.org/10.1016/j.cor.2018.11.018.
Baldacci, R., and V. Maniezzo. 2006. “Exact methods based on node-routing formulations for undirected arc-routing problems.” Networks 47 (1): 52–60. https://doi.org/10.1002/net.20091.
Bautista, J., E. Fernandez, and J. Pereira. 2008. “Solving an urban waste collection problem using ants heuristics.” Comput. Oper. Res. 35 (9): 3020–3033. https://doi.org/10.1016/j.cor.2007.01.029.
Belenguer, J. M., E. Benavent, N. Labadi, C. Prins, and M. Reghioui. 2010. “Split-delivery capacitated arc-routing problem: Lower bound and metaheuristic.” Transp. Sci. 44 (2): 206–220. https://doi.org/10.1287/trsc.1090.0305.
Beraldi, P., M. E. Bruni, D. Lagana, and R. Musmanno. 2015. “The mixed capacitated general routing problem under uncertainty.” Eur. J. Oper. Res. 240 (2): 382–392. https://doi.org/10.1016/j.ejor.2014.07.023.
Bosco, A., D. Lagana, R. Musmanno, and F. Vocaturo. 2013. “Modeling and solving the mixed capacitated general routing problem.” Optim. Lett. 7 (7): 1451–1469. https://doi.org/10.1007/s11590-012-0552-y.
Chen, Y. N., and J. K. Hao. 2018. “Two phased hybrid local search for the periodic capacitated arc routing problem.” Eur. J. Oper. Res. 264 (1): 55–65. https://doi.org/10.1016/j.ejor.2017.06.025.
Chen, Y. N., J. K. Hao, and F. Glover. 2016. “A hybrid metaheuristic approach for the capacitated arc routing problem.” Eur. J. Oper. Res. 253 (1): 25–39. https://doi.org/10.1016/j.ejor.2016.02.015.
Chu, F., N. Labadi, and C. Prins. 2005. “A scatter search for the periodic capacitated arc routing problem.” Eur. J. Oper. Res. 169 (2): 586–605. https://doi.org/10.1016/j.ejor.2004.08.017.
Ciancio, C., D. Lagana, and F. Vocaturo. 2018. “Branch-price-and-cut for the mixed capacitated general routing problem with time windows.” Eur. J. Oper. Res. 267 (1): 187–199. https://doi.org/10.1016/j.ejor.2017.11.039.
de Armas, J., P. Keenan, A. A. Juan, and S. McGarraghy. 2019. “Solving large-scale time capacitated arc routing problems: From real-time heuristics to metaheuristics.” Ann. Oper. Res. 273 (1–2): 135–162. https://doi.org/10.1007/s10479-018-2777-3.
Golden, B. L., J. S. Dearmon, and E. K. Baker. 1983. “Computational experiments with algorithms for a class of routing-problems.” Comput. Oper. Res. 10 (1): 47–59. https://doi.org/10.1016/0305-0548(83)90026-6.
Golden, B. L., and R. T. Wong. 1981. “Capacitated arc routing-problems.” Networks 11 (3): 305–315. https://doi.org/10.1002/net.3230110308.
Lacomme, P., C. Prins, and W. Ramdane-Cherif. 2004. “Competitive memetic algorithms for arc routing problems.” Ann. Oper. Res. 131 (1–4): 159–185. https://doi.org/10.1023/B:ANOR.0000039517.35989.6d.
Lacomme, P., C. Prins, and W. Ramdane-Cherif. 2005. “Evolutionary algorithms for periodic arc routing problems.” Eur. J. Oper. Res. 165 (2): 535–553. https://doi.org/10.1016/j.ejor.2004.04.021.
Lacomme, P., C. Prins, and M. Sevaux. 2006. “A genetic algorithm for a bi-objective capacitated arc routing problem.” Comput. Oper. Res. 33 (12): 3473–3493. https://doi.org/10.1016/j.cor.2005.02.017.
Liu, T. T., Z. B. Jiang, and N. Geng. 2013. “A memetic algorithm with iterated local search for the capacitated arc routing problem.” Int. J. Prod. Res. 51 (10): 3075–3084. https://doi.org/10.1080/00207543.2012.753165.
Longo, H., M. P. de Aragao, and E. Uchoa. 2006. “Solving capacitated arc routing problems using a transformation to the CVRP.” Comput. Oper. Res. 33 (6): 1823–1837. https://doi.org/10.1016/j.cor.2004.11.020.
Mourao, M. C., and L. Amado. 2005. “Heuristic method for a mixed capacitated arc routing problem: A refuse collection application.” Eur. J. Oper. Res. 160 (1): 139–153. https://doi.org/10.1016/j.ejor.2004.01.023.
Padungwech, W., J. Thompson, and R. Lewis. 2016. “Investigating edge-reordering procedures in a tabu search algorithm for the capacitated arc routing problem.” In Vol. 9668 of Proc., Int. Workshop on Hybrid Metaheuristics, edited by M. J. Blesa et al., 62–74. Cham, Switzerland: Springer. https://doi.org/10.1007/978-3-319-39636-1_5.
Renaud, J., G. Laporte, and F. F. Boctor. 1996. “A tabu search heuristic for the multi-depot vehicle routing problem.” Comput. Oper. Res. 23 (3): 229–235. https://doi.org/10.1016/0305-0548(95)O0026-P.
Riquelme-Rodriguez, J. P., M. Gamache, and A. Langevin. 2014. “Periodic capacitated arc-routing problem with inventory constraints.” J. Oper. Res. Soc. 65 (12): 1840–1852. https://doi.org/10.1057/JORS.2013.159.
Riquelme-Rodriguez, J. P., M. Gamache, and A. Langevin. 2016. “Location arc routing problem with inventory constraints.” Comput. Oper. Res. 76 (Dec): 84–94. https://doi.org/10.1016/j.cor.2016.06.012.
Santos, L., J. Coutinho-Rodrigues, and J. R. Current. 2010. “An improved ant colony optimization based algorithm for the capacitated arc routing problem.” Transp. Res. Part B-Methodol. 44 (2): 246–266. https://doi.org/10.1016/j.trb.2009.07.004.
Shang, R. H., K. Y. Dai, L. C. Jiao, and R. Stolkin. 2016a. “Improved memetic algorithm based on route distance grouping for multiobjective large scale capacitated arc routing problems.” IEEE Trans. Cybern. 46 (4): 1000–1013. https://doi.org/10.1109/TCYB.2015.2419276.
Shang, R. H., B. Q. Du, H. N. Ma, L. C. Jiao, Y. Xue, and R. Stolkin. 2016b. “Immune clonal algorithm based on directed evolution for multi-objective capacitated arc routing problem.” Appl. Soft Comput. 49 (Dec): 748–758. https://doi.org/10.1016/j.asoc.2016.09.005.
Sniezek, J., and L. Bodin. 2006. “Using mixed integer programming for solving the capacitated arc routing problem with vehicle/site dependencies with an application to the routing of residential sanitation collection vehicles.” Ann. Oper. Res. 144 (1): 33–58. https://doi.org/10.1007/s10479-006-0006-y.
Tagmouti, M., M. Gendreau, and J. Y. Potvin. 2007. “Arc routing problems with time-dependent service costs.” Eur. J. Oper. Res. 181 (1): 30–39. https://doi.org/10.1016/j.ejor.2006.06.028.
Tagmouti, M., M. Gendreau, and J. Y. Potvin. 2011. “A dynamic capacitated arc routing problem with time-dependent service costs.” Transp. Res. Part C-Emerging Technol. 19 (1): 20–28. https://doi.org/10.1016/j.trc.2010.02.003.
Tirkolaee, E. B., A. A. R. Hosseinabadi, M. Soltani, A. K. Sangaiah, and J. Wang. 2018. “A hybrid genetic algorithm for multi-trip green capacitated arc routing problem in the scope of urban services.” Sustainability 10 (5): 1366. https://doi.org/10.3390/su10051366.
Ulusoy, G. 1985. “The fleet size and mix problem for capacitated arc routing.” Eur. J. Oper. Res. 22 (3): 329–337. https://doi.org/10.1016/0377-2217(85)90252-8.
Usberti, F. L., P. M. Franca, and A. L. M. Franca. 2013. “GRASP with evolutionary path-relinking for the capacitated arc routing problem.” Comput. Oper. Res. 40 (12): 3206–3217. https://doi.org/10.1016/j.cor.2011.10.014.
Wang, Z., Y. Li, and X. P. Hu. 2015. “A heuristic approach and a tabu search for the heterogeneous multi-type fleet vehicle routing problem with time windows and an incompatible loading constraint.” Comput. Ind. Eng. 89 (Nov): 162–176. https://doi.org/10.1016/j.cie.2014.11.004.
Willemse, E. J., and J. W. Joubert. 2019. “Efficient local search strategies for the mixed capacitated arc routing problems under time restrictions with intermediate facilities.” Comput. Oper. Res. 105 (May): 203–225. https://doi.org/10.1016/j.cor.2019.02.002.
Xia, Z. H., X. H. Wang, X. M. Sun, and Q. Wang. 2016. “A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data.” IEEE Trans. Parallel Distrib. Syst. 27 (2): 340–352. https://doi.org/10.1109/TPDS.2015.2401003.
Zhang, Y. Z., Y. Mei, K. Tang, and K. Q. Jiang. 2017. “Memetic algorithm with route decomposing for periodic capacitated arc routing problem.” Appl. Soft Comput. 52 (Mar): 1130–1142. https://doi.org/10.1016/j.asoc.2016.09.017.
Information & Authors
Information
Published In
Journal of Transportation Engineering, Part A: Systems
Volume 146 • Issue 8 • August 2020
Copyright
©2020 American Society of Civil Engineers.
History
Received: Nov 21, 2019
Accepted: Mar 12, 2020
Published online: Jun 11, 2020
Published in print: Aug 1, 2020
Discussion open until: Nov 11, 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.