{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:39:11Z","timestamp":1760240351466,"version":"build-2065373602"},"reference-count":37,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T00:00:00Z","timestamp":1558051200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Science and Technology Project of Ministry of Housing and Urban-Rural Development","award":["2016-S5-013"],"award-info":[{"award-number":["2016-S5-013"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>In the network operation stage of urban mass transit, the connection relations between lines can effectively improve travel accessibility. As the last opportunity to travel on the same day, whether the last train can achieve transfer will directly affect passengers\u2019 travel experiences. It is an important work to make the connection scheme of the last train, which needs to take the network structure, the trend, and the volume of passenger flow into overall consideration. This paper analyzes the characters of the last train connection, including the connection structure and the accessible form. Then, we establish a scheme model and define the objectives, the constraints, and the decision data source, and transform it into a graph theory problem. Taking an urban mass transit network as an example, we demonstrate the solution process by using an improved Prim algorithm. Finally, the main aspects and methods of initial scheme optimization are proposed.<\/jats:p>","DOI":"10.3390\/sym11050681","type":"journal-article","created":{"date-parts":[[2019,5,17]],"date-time":"2019-05-17T11:06:46Z","timestamp":1558091206000},"page":"681","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["An Improved Prim Algorithm for Connection Scheme of Last Train in Urban Mass Transit Network"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6547-0685","authenticated-orcid":false,"given":"Xiaoxu","family":"Zeng","sequence":"first","affiliation":[{"name":"School of Traffic &amp; Transportation Engineering, Central South University, Changsha 410083, China"},{"name":"Tianjin Rail Transit Operation Group Co.Ltd., Tianjin 300392, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qinglei","family":"Liu","sequence":"additional","affiliation":[{"name":"Tianjin Rail Transit Operation Group Co.Ltd., Tianjin 300392, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Song","family":"Yao","sequence":"additional","affiliation":[{"name":"School of Traffic &amp; Transportation Engineering, Central South University, Changsha 410083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,5,17]]},"reference":[{"key":"ref_1","first-page":"721","article-title":"Timetable-based operation in urban transport: Run-time optimization and improvements in the operating process","volume":"8","author":"Fleurent","year":"2011","journal-title":"Transp. Res. Part A"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Belenky, A.S. (1998). Operations Research in Transportation Systems, Springer.","DOI":"10.1007\/978-1-4757-6075-0"},{"key":"ref_3","first-page":"651","article-title":"Optimization of transportation system using OR (Operational Research) approaches","volume":"3","author":"Janani","year":"2014","journal-title":"Int. J. Sci. Eng. Technol."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1002\/atr.197","article-title":"Modeling and optimization of transportation systems","volume":"45","author":"Wirasinghe","year":"2011","journal-title":"J. Adv. Transp."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1287\/trsc.1070.0200","article-title":"Optimizing timetable synchronization for rail mass transit","volume":"42","author":"Wong","year":"2008","journal-title":"Transp. Sci."},{"key":"ref_6","first-page":"377","article-title":"A practical model for transfer optimization in a transit network: Model equationtions and solutions","volume":"6","author":"Yousef","year":"2010","journal-title":"Transp. Res. Part A"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1016\/j.trb.2017.05.001","article-title":"Two-phase decomposition method for the last train departure time choice in subway networks","volume":"104","author":"Kang","year":"2017","journal-title":"Transp. Res. Part B Methodol."},{"key":"ref_8","first-page":"108","article-title":"Timetable synchronization optimization for urban rail transit in the last trains\u2019 hour","volume":"16","author":"Ning","year":"2016","journal-title":"J. Transp. Syst. Eng. Inf. Technol."},{"key":"ref_9","first-page":"228","article-title":"Last train timetable synchronization optimization on urban rail networks with dwell time extension","volume":"17","author":"Chen","year":"2017","journal-title":"J. Transp. Syst. Eng."},{"key":"ref_10","unstructured":"Alireza, K., and Yousef, S. (2011, January 5\u20137). Transfer optimization in transit networks: Headway and departure time coordination. Proceedings of the 14th International IEEE Conference on Intelligent Transportation Systems (ITSC), Washington, DC, USA."},{"key":"ref_11","first-page":"134","article-title":"Optimization of convergence based on the coordination of train departure time in the subway transfer station","volume":"13","author":"Bai","year":"2013","journal-title":"J. Transp. Syst. Eng. Inf. Technol."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.trb.2014.09.003","article-title":"A case study on the coordination of last trains for the Beijing subway network","volume":"72","author":"Kang","year":"2014","journal-title":"Transp. Res. Part B"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1061\/(ASCE)CP.1943-5487.0000407","article-title":"Departure time optimization of last trains in subway networks: Mean-Variance model and GSA algorithm","volume":"29","author":"Kang","year":"2015","journal-title":"J. Comput. Civ. Eng."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1436","DOI":"10.1007\/s12205-017-1786-0","article-title":"Last train delay management in urban rail transit network: Bi-objective MIP model and genetic algorithm","volume":"22","author":"Xu","year":"2018","journal-title":"KSCE J. Civ. Eng."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Chen, X.F., and Wang, B.X. (2016, January 6\u20139). Coordination and optimization of connecting trains in a transfer station of urban mass transit. Proceedings of the 16th COTA International Conference of Transportation Professionals, Shanghai, China.","DOI":"10.1061\/9780784479896.082"},{"key":"ref_16","first-page":"9","article-title":"Synchronized and coordinated train connecting optimization for transfer stations of urban rail networks","volume":"3","author":"Zhou","year":"2011","journal-title":"J. China Railw. Soc."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1155\/2013\/848292","article-title":"Coordination optimization of the first and last trains\u2019 departure time on urban rail transit network","volume":"5","author":"Zhou","year":"2013","journal-title":"Adv. Mech. Eng."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"2211","DOI":"10.4028\/www.scientific.net\/AMR.1030-1032.2211","article-title":"Study on connection optimization of last train departure time on urban mass transit network","volume":"1030","author":"Kou","year":"2014","journal-title":"Adv. Mater. Res."},{"key":"ref_19","unstructured":"Xiang, W.X., and Wang, Y.H. (2017, January 20\u201322). A multi-objective programming model for subway last train timetabling. Proceedings of the 3rd International Conference on Electrical and Information Technologies for Rail Transportation (EITRT), Changsha, China."},{"key":"ref_20","unstructured":"Chung, E.H. (2009). Transfer Coordination Model and Real-Time Strategy for Inter-Modal Transit Services, University of Toronto."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1311","DOI":"10.4028\/www.scientific.net\/AMM.409-410.1311","article-title":"The research of first and last trip optimization under the network of urban mass transit","volume":"409\u2013410","author":"Shang","year":"2013","journal-title":"Appl. Mech. Mater."},{"key":"ref_22","unstructured":"Bassel, J.Y. (2004). Improving Transit Service Connectivity: The Application of Operations Planning and Operations Control Strategies, MIT."},{"key":"ref_23","first-page":"9","article-title":"Optimization of train connection time at urban mass transit transfer station","volume":"4","author":"Liang","year":"2015","journal-title":"Urban Mass Transit."},{"key":"ref_24","first-page":"3334","article-title":"Research on the last train connection in the urban mass transit system","volume":"1065\u20131069","author":"Cai","year":"2015","journal-title":"Adv. Mater. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.apm.2016.12.016","article-title":"Strategic timetable scheduling for last trains in urban railway transit networks","volume":"45","author":"Kang","year":"2017","journal-title":"Appl. Math. Model."},{"key":"ref_26","first-page":"9","article-title":"Transfer coordination optimization for network operation of urban rail transit based on hierarchical preference","volume":"31","author":"Zhang","year":"2009","journal-title":"J. China Railw. Soc."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.omega.2014.07.005","article-title":"A practical model for last train rescheduling with train delay in urban railway transit networks","volume":"50","author":"Kang","year":"2015","journal-title":"Omega"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"3603","DOI":"10.1007\/s11771-012-1448-9","article-title":"A simulation model for estimating train and passenger delays in large-scale rail transit networks","volume":"12","author":"Jiang","year":"2012","journal-title":"J. Cent. South Univ."},{"key":"ref_29","first-page":"757","article-title":"Study on stability of last train connection under delays on urban rail transit","volume":"641\u2013642","author":"Li","year":"2014","journal-title":"Appl. Mech. Mater."},{"key":"ref_30","first-page":"111","article-title":"Research on passenger guidance system of urban rail transit network based on timetable of last train","volume":"2","author":"Xu","year":"2014","journal-title":"China Railw. Sci."},{"key":"ref_31","unstructured":"Guo, J.Y., Jia, L.M., Qin, Y., and Wang, B. (2013, January 6\u20139). Trip planning considering last trains running. Proceedings of the 16th International IEEE Conference on Intelligent Transportation Systems\u2014(ITSC 2013), The Hague, The Netherlands."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Guo, J.Y., Jia, L.M., Xu, J., and Qin, Y. (2012, January 19\u201322). An algorithm for trip planning with constraint of transfer connection in urban mass transit network. Proceedings of the 11th International Symposium on Distributed Computing and Applications to Business, Engineering & Science, Guilin, China.","DOI":"10.1109\/DCABES.2012.79"},{"key":"ref_33","first-page":"15","article-title":"A few remarks on the history of MST-problem","volume":"33","author":"Jaroslav","year":"1997","journal-title":"Arch. Math."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","article-title":"Shortest connection networks and some generalizations","volume":"36","author":"Prim","year":"1957","journal-title":"Bell Syst. Tech. J."},{"key":"ref_35","first-page":"49","article-title":"An optimal minimum spanning tree algorithm","volume":"1853","author":"Pettie","year":"2000","journal-title":"J. ACM ICALP"},{"key":"ref_36","first-page":"1510","article-title":"Comprehensive optimization for connection scheme of last trains in urban mass transit network","volume":"10","author":"Xu","year":"2012","journal-title":"J. Tongji Univ. (Nat. Sci.)"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1109\/TSMCC.2008.923872","article-title":"Timetable synchronization of mass rapid transit system using multiobjective evolutionary approach","volume":"5","author":"Chung","year":"2008","journal-title":"IEEE Trans. Syst. Man Cybern. Part C"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/5\/681\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:53:14Z","timestamp":1760187194000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/5\/681"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,17]]},"references-count":37,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2019,5]]}},"alternative-id":["sym11050681"],"URL":"https:\/\/doi.org\/10.3390\/sym11050681","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2019,5,17]]}}}