Demand-Aware Heuristic Initialization and NSGA-II for Multi-Objective Transit Route Optimization

Rajabi, Reza; Modarres Khiabania, Farzin; Sadeghi Gavganib, Saba

doi:10.30473/coam.2026.78581.1439

Articles in Press

Document Type : Research Article

Authors

¹ Department of Mathematics, Ta.c., Islamic. Azad University, Tabriz, Iran

² Department of Mathematics, Sara.C., Islamic. Azad University, Sarab, Iran

https://doi.org/10.30473/coam.2026.78581.1439

Abstract

Candidate route sets in the Urban Transit Network Design Problem (UTNDP) must provide adequate network coverage and connectivity while complying with prescribed route-length and route-cardinality requirements. This study develops a demand-aware heuristic-initialized NSGA-II framework for the UTNDP. The method uses demand and travel-time information to construct feasible initial route sets, then applies Pareto ranking, crowding-distance selection, crossover, problem-specific mutation, feasibility repair, and duplicate filtering during the evolutionary search. The optimization model minimizes two explicitly defined objectives: the demand-weighted passenger generalized travel time (F1) and the total route weight, which serves as an operator-cost proxy (F2). In the reported Mandl/Mumford-style benchmark evaluation, every transfer edge of the transfer-expanded graph carries a fixed 5-min penalty, consistent with the standard convention for the urban transit routing problem (UTRP). Candidate route sets that leave any positive-demand origin–destination pair disconnected are first subjected to feasibility repair and, if the repair fails, are rejected before environmental selection. The framework is assessed on established UTNDP benchmark networks ranging from small to large instances. Hypervolume and spacing are formally defined as Pareto-set performance indicators, whereas the reported numerical comparisons are restricted to benchmark objective values directly supported by the available computational records; no run-level inferential comparison is claimed. Duplicate filtering and parameter settings are treated as algorithmic design components rather than being assigned independent gains without a dedicated ablation study. On the reported benchmark data, the framework yields passenger-cost values of 21.34 min for Mumford0 (22.18 min in the original study by Mumford) and 52.18 min for Edinburgh200 (55.34 min in the original study by Mumford). We treat frequency and vehicle capacity as exogenous quantities so the experiments isolate route-set optimization. The resulting framework provides a reproducible basis for passenger–operator trade-off analysis and a clearly delimited platform for future extensions to joint frequency, capacity, uncertainty, and parallel-computing formulations.

Highlights

Proposes a 441-configuration weighted-graph heuristic for seeding UTNDP route sets.
Integrates the heuristic seed with NSGA-II and eight specialized mutation operators.
Reports up to 2.1% average Hypervolume gain over SEAMO2 across seven benchmarks.
Introduces an edge-based Sørensen/Dice diversity measure for route-set populations.
Establishes new best-known passenger-cost solutions on six of seven UTNDP instances.

Keywords

Main Subjects

Optimal Operational Scheduling

References

[1] Almasi, M. H., Oh, Y., Sadollah, A., Byon, Y. J., Kang, S. (2021). “Urban transit network optimization under variable demand with single and multi-objective approaches using metaheuristics: The case of Daejeon, Korea”. International Journal of Sustainable Transportation, 15(5), 386–406. https://doi.org/10.1080/15568318.2020.1821414

[2] Baker, B. M., Ayechew, M. A. (2003). “A genetic algorithm for the vehicle routing problem”. Computers & Operations Research, 30(5), 787–800. https://doi.org/10. 1016/S0305-0548(02)00051-5

[3] Baldacci, R., Christofides, N., Mingozzi, A. (2008). “An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts”. Mathematical Programming, 115(2), 351–385. https://doi.org/10.1007/ s10107-007-0178-5

[4] Beirão, G., Cabral, J. S. (2007). “Understanding attitudes towards public transport and private car: A qualitative study”. Transport Policy, 14(6), 478–489. https://doi.org/10.1016/j.tranpol.2007.04.009

[5] Bell, J. E., McMullen, P. R. (2004). “Ant colony optimization techniques for the vehicle routing problem”. Advanced Engineering Informatics, 18(1), 41–48. https://doi.org/ 10.1016/j.aei.2004.07.001

[6] Brands, T., van Berkum, E. C. (2014). “Performance of a genetic algorithm for solving the multi-objective, multimodal transportation network design problem”. International Journal of Transportation, 2(1), 1–20. https://doi.org/10.14257/ijt.2014.2.1. 01

[7] Carvajal-Carreño, W., Cucala, A. P., Fernández-Cardador, A. (2014). “Optimal design of energy-efficient ATO CBTC driving for metro lines based on NSGA-II with fuzzy parameters”. Engineering Applications of Artificial Intelligence, 36, 164–177. https: //doi.org/10.1016/j.engappai.2014.07.019

[8] Chai, S., Liang, Q. (2020). “An improved NSGA-II algorithm for transit network design and frequency setting problem”. Journal of Advanced Transportation, 2020, 2895320. https://doi.org/10.1155/2020/2895320

[9] Chakroborty, P., Dwivedi, T. (2002). “Optimal route network design for transit systems using genetic algorithms”. Engineering Optimization, 34(1), 83–100. https://doi.org/ 10.1080/03052150210909

[10] Chen, B., Zhang, R., Long, S., Sakdanuphab, R. (2024). “A multi-objective multi-period low-carbon location-routing problem: Improved NSGA-II approach”. IEEE Access, 12, 51590–51605. https://doi.org/10.1109/ACCESS.2024.3386584

[11] Clarke, G., Wright, J. W. (1964). “Scheduling of vehicles from a central depot to a number of delivery points”. Operations Research, 12(4), 568–581. https://doi.org/10. 1287/opre.12.4.568

[12] Cooper, I. M., John, M. P., Lewis, R., Mumford, C. L., Olden, A. (2014). “Optimising large scale public transport network design problems using mixed-mode parallel multiobjective evolutionary algorithms”. 2014 IEEE Congress on Evolutionary Computation (CEC), 2841–2848. https://doi.org/10.1109/CEC.2014.6900362

[13] Croes, G. A. (1958). “A method for solving traveling-salesman problems”. Operations Research, 6(6), 791–812. https://doi.org/10.1287/opre.6.6.791

[14] Czech, Z. J., Czarnas, P. (2002). “Parallel simulated annealing for the vehicle routing problem with time windows”. Proceedings of the 10th Euromicro Workshop on Parallel, Distributed and Network-Based Processing. https://doi.org/10.1109/EMPDP.2002.994313

[15] Deb, K., Pratap, A., Agarwal, S., Meyarivan, T. (2002). “A fast and elitist multiobjective genetic algorithm: NSGA-II”. IEEE Transactions on Evolutionary Computation, 6(2), 182–197. https://doi.org/10.1109/4235.996017

[16] Faroqi, H. (2024). “Multiobjective route finding in a multimode transportation network by NSGA-II”. Journal of Engineering and Applied Science, 71, 81. https://doi.org/ 10.1186/s44147-024-00417-7

[17] Gardner, B., Abraham, C. (2007). “What drives car use? A grounded theory analysis of commuters’ reasons for driving”. Transportation Research Part F: Traffic Psychology and Behaviour, 10(3), 187–200. https://doi.org/10.1016/j.trf.2006.09.004

[18] Gillett, B. E., Miller, L. R. (1974). “A heuristic algorithm for the vehicle-dispatch problem”. Operations Research, 22(2), 340–349. https://doi.org/10.1287/opre.22.2. 340

[19] Guihaire, V., Hao, J.-K. (2008). “Transit network design and scheduling: A global review”. Transportation Research Part A: Policy and Practice, 42(10), 1251–1273. https://doi. org/10.1016/j.tra.2008.03.011

[20] Holliday, A., El-Geneidy, A., Dudek, G. (2025). “Learning heuristics for transit network design and improvement with deep reinforcement learning”. Transportmetrica B: Transport Dynamics, 13(1), 2561863. https://doi.org/10.1080/21680566.2025. 2561863

[21] Hüsselmann, G., van Vuuren, J. H., Andersen, S. J. (2024). “An improved solution methodology for the urban transit routing problem”. Computers & Operations Research, 163, 106481. https://doi.org/10.1016/j.cor.2023.106481

[22] Jha, S. B., Jha, J. K., Tiwari, M. K. (2019). “A multi-objective meta-heuristic approach for transit network design and frequency setting problem in a bus transit system”. Computers & Industrial Engineering, 130, 166–186. https://doi.org/10.1016/j.cie. 2019.02.025

[23] John, M. P., Mumford, C. L., Lewis, R. (2014). “An improved multi-objective algorithm for the urban transit routing problem”. Evolutionary Computation in Combinatorial Optimisation, Lecture Notes in Computer Science, 8600, 49–60. https://doi.org/10. 1007/978-3-662-44320-0_5

[24] Kılıç, F., Gök, M. (2014). “A demand based route generation algorithm for public transit network design”. Computers & Operations Research, 51, 21–29. https://doi.org/10.1016/j.cor.2014.05.001

[25] Kourepinis, V., Iliopoulou, C., Tassopoulos, I. X., Beligiannis, G. N. (2024). “An artificial fish swarm optimization algorithm for the urban transit routing problem”. Applied Soft Computing, 155, 111446. https://doi.org/10.1016/j.asoc.2024.111446

[26] Li, L., Zhang, C., Niu, C., Zhang, H. (2025). “Parametric multi-objective optimization of urban block morphology using NSGA-II: A case study in Wuhan, China”. Sustainability, 17(21), 9724. https://doi.org/10.3390/su17219724

[27] Mandl, C. E. (1980). “Evaluation and optimization of urban public transportation networks”. European Journal of Operational Research, 5(6), 396–404. https://doi.org/ 10.1016/0377-2217(80)90126-5

[28] Martínez-Quezada, D. O., Cortés, C. E., Mauttone, A., Munizaga, M. A. (2026). “A multiobjective optimization approach for the electric transit network design and frequency setting problem”. Applied Mathematical Modelling, 154, 116669. https://doi.org/10. 1016/j.apm.2025.116669

[29] Miandoabchi, E., Farahani, R. Z., Dullaert, W., Szeto, W. Y. (2012). “Hybrid evolutionary metaheuristics for concurrent multi-objective design of urban road and public transit networks”. Networks and Spatial Economics, 12(3), 441–480. https://doi.org/10. 1007/s11067-011-9163-x

[30] Momenitabar, M., Mattson, J. (2021). “A multi-objective meta-heuristic approach to improve the bus transit network: A case study of Fargo–Moorhead area”. Sustainability, 13(19), 10885. https://doi.org/10.3390/su131910885

[31] Mumford, C. L. (2013). “New heuristic and evolutionary operators for the multi-objective urban transit routing problem”. 2013 IEEE Congress on Evolutionary Computation, 939– 946. https://doi.org/10.1109/CEC.2013.6557668

[32] Nayeem, M. A., Rahman, M. K., Rahman, M. S. (2014). “Transit network design by genetic algorithm with elitism”. Transportation Research Part C: Emerging Technologies, 46, 30–45. https://doi.org/10.1016/j.trc.2014.05.002

[33] Nikolić, M., Teodorović, D. (2013). “Transit network design by Bee Colony Optimization”. Expert Systems with Applications, 40(15), 5945–5955. https://doi.org/10. 1016/j.eswa.2013.05.002

[34] Qi, L., Zhang, R., Luan, W., Li, M., Guo, X. (2025). “Multi-objective optimization for multi-modal route planning integrating shared taxi and bus”. Computing and Informatics, 44(4), 769–799. https://doi.org/10.31577/cai_2025_4_769

[35] Seifpour, M., Asghari, S. A., Ghobaei-Arani, M. (2024). “A stochastic multi-objective optimization method for railways scheduling: A NSGA-II-based hybrid approach”. The Journal of Supercomputing, 80(2), 2128–2163. https://doi.org/10.1007/ s11227-023-05529-0

[36] Stradling, S. G., Carreno, M., Rye, T., Noble, A. (2007). “Passenger perceptions and the ideal urban bus journey experience”. Transport Policy, 14(4), 283–292. https://doi. org/10.1016/j.tranpol.2007.02.003

[37] Tan, K. C., Chew, Y., Lee, L. H. (2006). “A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems”. European Journal of Operational Research, 172(3), 855–885. https://doi.org/10.1016/j.ejor.2004.11.019

[38] Tan, K. C., Chew, Y. H., Lee, L. H. (2006). “A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows”. Computational Optimization and Applications, 34(1), 115–151. https://doi.org/10.1007/ s10589-005-3070-3

[39] Toth, P., Vigo, D. (2003). “The granular tabu search and its application to the vehicle-routing problem”. INFORMS Journal on Computing, 15(4), 333–346. https://doi. org/10.1287/ijoc.15.4.333.24890

[40] Yoo, S., Lee, J. B., Han, H. (2023). “A reinforcement learning approach for bus network design and frequency setting optimisation”. Public Transport, 15, 503–534. https:// doi.org/10.1007/s12469-022-00319-y

[41] Zervas, A., Iliopoulou, C., Tassopoulos, I. X., Beligiannis, G. N. (2024). “Solving large-scale instances of the urban transit routing problem with a parallel artificial bee colony-hill climbing optimization algorithm”. Applied Soft Computing, 167, 112335. https://doi. org/10.1016/j.asoc.2024.112335

[42] Zhang, Z., Cheng, X., Xing, Z., Gui, X. (2023). “Pareto multi-objective optimization of metro train energy-saving operation using improved NSGA-II algorithms”. Chaos, Solitons & Fractals, 176, 114183. https://doi.org/10.1016/j.chaos.2023.114183

[43] Zitzler, E., Thiele, L. (1998). “Multiobjective optimization using evolutionary algorithms—A comparative case study”. Parallel Problem Solving from Nature — PPSN V, Lecture Notes in Computer Science, 292–301. https://doi.org/10.1007/BFb0056872

Control and Optimization in Applied Mathematics

Demand-Aware Heuristic Initialization and NSGA-II for Multi-Objective Transit Route Optimization

References

References

Articles in Press, Corrected Proof
Available Online from 03 October 2026

Demand-Aware Heuristic Initialization and NSGA-II for Multi-Objective Transit Route Optimization

References

References

Articles in Press, Corrected Proof Available Online from 03 October 2026

Articles in Press, Corrected Proof
Available Online from 03 October 2026