A Multi-Objective Decomposition Model for Integrated Urban Transit Line Planning and Passenger Routing

Authors

  • Shubuhan Syukri Hasibuan Graduate Student, Department of Mathematics, Universitas Sumatera Utara, Indonesia
  • Saib Suwilo Department of Mathematics, Universitas Sumatera Utara, Indonesia
  • Mardiningsih Department of Mathematics, Universitas Sumatera Utara, Indonesia

DOI:

10.33395/sinkron.v9i2.14803

Keywords:

multi-objective integer programming; public transport network design; line planning; passenger routing; Dantzig–Wolfe decomposition; Change-and-Go model; urban transit optimization

Abstract

: Urban public transport networks must balance traveler convenience with tight budgetary and capacity constraints. This study develops a comprehensive multi-objective integer programming framework that unifies line selection, frequency setting, and passenger routing to minimize door-to-door travel time and operating cost while respecting vehicle capacities and limiting transfers. The model is solved using a Dantzig–Wolfe decomposition approach with linear-programming relaxation, which enables tractable solutions on realistically scaled networks. To reflect real-world commuting behavior, three increasingly sophisticated formulations are proposed: a Basic Line Planning Model, a Direct Connection Capacity Model, and a Change-and-Go Model that embeds walking and waiting penalties. On a six-edge, four-node network with 6,000 passenger trips, the Change-and-Go Model emerges as the most effective, reducing average travel time by 47%, halving transfers, and increasing cost by only 11% compared to the incumbent plan. Sensitivity analysis reveals that the model remains robust under varying demand levels and cost–time priorities. The proposed framework thus offers a scalable and passenger-friendly decision-support tool that significantly improves public transport efficiency with moderate investment, making it especially valuable for urban transit agencies seeking to modernize their services.

GS Cited Analysis

Downloads

Download data is not yet available.

References

Alçura, G. A., Kuşakcı, S. Ş., Şimşek, G. G., Gürsoy, M., & Tanrıverdi, S. C. (2016). Impact Score Technique for Analyzing the Service Quality of a High-Speed Rail System. Transportation Research Record: Journal of the Transportation Research Board, 2541(1), 64–72. https://doi.org/10.3141/2541-08

Borndörfer, R., Grötschel, M., & Pfetsch, M. E. (2007). A Column-Generation Approach to Line Planning in Public Transport. Transportation Science, 41(1), 123–132. https://doi.org/10.1287/trsc.1060.0161

Borndörfer, R., Karbstein, M., & Pfetsch, M. E. (2012). Models for fare planning in public transport. Discrete Applied Mathematics, 160(18), 2591–2605. https://doi.org/10.1016/j.dam.2012.02.027

Bussieck, M. R., Lindner, T., & Lübbecke, M. E. (2004). A fast algorithm for near cost optimal line plans. Mathematical Methods of Operations Research (ZOR), 59(2), 205–220. https://doi.org/10.1007/s001860300332

Eirola, A. I. (2012). Improving packet transport network efficiency using capacity aware routing. Aalto University.

Farahmand-Tabar, S., & Afrasyabi, P. (2024). Multi-modal Routing in Urban Transportation Network Using Multi-objective Quantum Particle Swarm Optimization. In Applied Multi-objective Optimization (pp. 133–154). Springer. https://doi.org/10.1007/978-981-97-0353-1_7

Green, J., Jones, A., & Roberts, H. (2014). More than A to B: the role of free bus travel for the mobility and wellbeing of older citizens in London. Ageing and Society, 34(3), 472–494. https://doi.org/10.1017/S0144686X12001110

Guo, Z., & Wilson, N. H. M. (2011). Assessing the cost of transfer inconvenience in public transport systems: A case study of the London Underground. Transportation Research Part A: Policy and Practice, 45(2), 91–104. https://doi.org/10.1016/j.tra.2010.11.002

Jahan, J., & Hamidi, S. (2019). A National Study on Transportation Affordability of HUD Housing Assistance Programs. Sustainability, 12(1), 123. https://doi.org/10.3390/su12010123

Morton, C., Caulfield, B., & Anable, J. (2016). Customer perceptions of quality of service in public transport: Evidence for bus transit in Scotland. Case Studies on Transport Policy, 4(3), 199–207. https://doi.org/10.1016/j.cstp.2016.03.002

Schöbel, A. (2012). Line planning in public transportation: models and methods. OR Spectrum, 34(3), 491–510. https://doi.org/10.1007/s00291-011-0251-6

Schöbel, A., & Scholl, S. (2005). Line Planning with Minimal Traveling Time. 5th Workshop on Algorithmic Methods and Models for Optimization of Railways, 1–16. https://doi.org/https://doi.org/10.4230/OASIcs.ATMOS.2005.660

Tang, S., Hou, Z., & Yong, L. (2020). An Accelerating Algorithm for Linear Multiplicative Programming Problem. IEEE Access, 8, 188784–188796. https://doi.org/10.1109/ACCESS.2020.3031354

Xiao, M., Chen, L., Feng, H., Peng, Z., & Long, Q. (2024). Smart City Public Transportation Route Planning Based on Multi-objective Optimization: A Review. Archives of Computational Methods in Engineering, 31(6), 3351–3375. https://doi.org/10.1007/s11831-024-10076-9

Downloads


Crossmark Updates

How to Cite

Hasibuan, S. S., Suwilo, S. ., & Mardiningsih, M. (2025). A Multi-Objective Decomposition Model for Integrated Urban Transit Line Planning and Passenger Routing. Sinkron : Jurnal Dan Penelitian Teknik Informatika, 9(2), 1015-1023. https://doi.org/10.33395/sinkron.v9i2.14803

Issue

Vol. 9 No. 2 (2025): Research Articles April 2025

Section

Articles

License

Copyright (c) 2025 Shubuhan Syukri Hasibuan, Saib Suwilo, Mardiningsih

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Crossref
Scopus
Google Scholar
Europe PMC

Most read articles by the same author(s)

1 2 > >>