Evaluating the performance of a genetic algorithm to solve the line planning problem for a bus service
Keywords:
algoritmo genético, problema de planificación de línea, servicios de autobúsAbstract
Planning a bus service requires to explore several feasible solutions attempting to optimize travel time, costs or both. The line planning problem (lpp) solves the combinatorial problem to define the routes for bus lines in a bus service under a set of constraints, input parameters and an objective function. The input parameters such as the demand, infrastructure, travel times, etc., describe the current situation, and provide both input data and the constraints that should be considered during the design. An algorithm that obtains feasible and high-quality solutions for lpp is essential in search of better urban services. In this study, a genetic algorithm is designed and coded to solve the lpp. Finally, an evaluation of the results is carried out from different perspectives, attempting to ensure the solutions obtained by the algorithm are consistent and therefore useful in practice.
Downloads
Metrics
References
Affenzeller, M., Wagner, S., Winkler, S., Beham, A. (2009). Genetic algorithms and genetic programming: modern concepts and practical applications. Boca Ratón, FL: CRC Press.
Baaj, M. H., Hani, S. M. (1991). An AI‐based approach for transit route system planning and design. Journal of Advanced Transportation, 25(2), 187-209.
Borndörfer, R., Grötschel, M., Pfetsch, M. E. (2008). Models for line planning in public transport. In: Computer-aided systems in public transport, pp. 363-378. Berlin, Germany: Springer.
Carrión, C., Levinson, D. (2012). Value of travel time reliability: A review of current evidence. Transportation Research Part A, 46(4), 720-741.
Ceder, A., Wilson, N. (1986). Bus network design. Transportation Research Part B, 20(4), 331-344.
Chakroborty, P., Wivedi, T. (2002). Optimal route network design for transit systems using genetic algorithms. Engineering Optimization, 34(1), 83-100.
Cipriani, E., Gori, S., Petrelli, M. (2012). Transit network design: A procedure and an application to a large urban area. Transportation Research Part C, 20(1), 3-14.
Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
Farahani, R. Z., Miandoabchi, E., Szeto, W., Rashidi, H. (2013). A review of urban transportation network design problems. European Journal of Operational Reserach, 229(2), 281-302.
Guihaire, V., Hao, J. (2008). Transit network design and scheduling: a global review. Transportation Research part A, 42(10), 1251-1273.
Ibarra-Rojas, O., Delgado, F., Giesen, J., Muñoz, J. (2015). Planning, operation, and control of bus transport systems: A literature review. Transportation Research Part B, 77, 38-75.
Kepaptsoglou, K., Karlaftis, M. (2009). Transit route network design problem: review. Journal of Transportation Engineering, 135(8), 491-505.
Mandl, C. E. (1979). Evaluation and optimization of urban public transportation network. European Journal of Operational Research, 5(6), 396-404.
Nayeem, M. A., Rahman, M. K., Rahman, M. S. (2014). Transit network design by genetic algorithm with elitism. Transportation Research Part C, 46, 30-45.
Ngamchai, S., Lovell, D. (2003). Optimal time transfer in bus transit route network design using a genetic algorithm. Journal of Transportation Engineering, 129(5), 510-521.
Nikolić, M., Teodorović, D. (2013). Transit network design by bee colony optimization. Expert Systems with Applications, 40(15), 5945-5955.
Pattnaik, S., Mohan, S., Tom, V. (1998). Urban bus transit route network design using genetic algorithm. Journal of Transportation Engineering, 124(4), 368-375.
Schöbel, A. (2012). Line planning in public transportation: models and methods. OR Spectrum, 34(3), 491-510.
Tarjan, R. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146-160.
Tom, V. M., Mohan, S. (2003). Transit route network design using frequency coded genetic algorithm. Journal of Transportation Engineering, 129(2), 186-195.
Van Oort, N. (2011). Service reliability and urban public transport design. Doctoral thesis, Faculty of Civil Engineering and Geosciences, Delft University of Technology, Delft, The Netherlands.
Zhao, F., Zeng, X. (2006). Optimization of transit network layout and headway with a combined genetic algorithm and simulated annealing method. Engineering Optimization, 38(6), 701-722.
Zhao, H., Xu, W., Jiang, R. (2015). The memetic algorithm for the optimization of urban transit network. Expert Systems with Applications, 42(7), 3760-3773.
Downloads
Published
How to Cite
Issue
Section
License
Copyright © Autors. Creative Commons Attribution 4.0 License. for any article submitted from 6 June 2017 onwards. For manuscripts submitted before, the CC BY 3.0 License was used.
You are free to:
 |
Share — copy and redistribute the material in any medium or format |
 |
Adapt — remix, transform, and build upon the material for any purpose, even commercially. |
Under the following conditions:
 |
Attribution — You must give appropriate credit, provide a link to the licence, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licenser endorses you or your use. |
| No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the licence permits. |
