A Matheuristic for Optimizing Skip–Stop Operation Strategies in Rail Transit Lines

A Matheuristic for Optimizing Skip–Stop Operation Strategies in Rail Transit Lines

Francisco A. Ortega Juan A. Mesa Ramón Piedra-de-la-Cuadra Miguel A. Pozo

Higher Technical School of Architecture, Universidad de Sevilla, Spain

Higher Technical School of Engineering, Universidad de Sevilla, Spain

Department of Mathematics, Universidad de Cordoba, Spain

Faculty of Mathematics, Universidad de Sevilla, Spain

Available online: 
| Citation



In many transit systems, operators use skip–stop strategies to reduce travel time of particular train services by not stopping (skipping) at less densely populated stations. This decision of omitting some stops reduces the travel time for the users within the vehicle and increases the speed of operation, favouring the provision of new transit services where are more necessary. In this work, the best A/b stop–skip patterns for a set of transit services along a railway corridor are determined by means a three-phase methodology that includes the formulation of a nonlinear integer programming inspired in the multiple knapsack problem and the application of a heuristic algorithm based on mathematical properties (matheuristic).


matheuristics, optimization, railways, stop–skip strategy


[1] Chicago-L.org. North Side Express Operations, available at http://www.chicago-l.org/operations/lines/route_ops/north.html, (accessed 23 March 2019).

[2] Chicago-L.org. A/B Skip-Stop Express Service, available at http://www.chicago-l.org/operations/lines/route_ops/A-B.html, (accessed 23 March March 2019).

[3] Freyss, M., Giesen, R. & Muñoz, J. C., Continuous approximation for skip-stop operation in rail transit. Transportation Research Part C: Emerging Technologies, 36, pp. 419–433, 2013.

[4] Leiva, C., Muñoz, J.C., Giesen, R. & Larrain, H., Design of limited-stop services for an urban bus corridor with capacity constraints. Transportation Research B, 44(10), pp. 1186–1201, 2010.

[5] Zhang, P., Sun, Z. & Liu, X., Optimized skip-stop metro line operation using smart card data. Journal of Advanced Transportation, 2017, Article ID 3097681, pp. 17.

[6] Chen, Z., Liu, Zhu, S. & Wang, W., Design of limited-stop bus service with capacity constraint and stochastic travel time. Transportation Research Part E: Logistics and Transportation Review, 83, pp. 1–15, 2015.

[7] Transportes Urbanos de Sevilla S. A. M. (TUSSAM), available at http://www.tussam.es,(accessed 23 March 2019).

[8] Lee, Y., Shariat, S. & Choi, K., Optimizing skip-stop rail transit stopping strategy using a genetic algorithm. Journal of Public Transportation, 17(2), pp. 135–164, 2014.

[9] Feng, S., Zhu, W., Ye, Y. & Wang, D., Optimal skip-stop schedule under mixed traffic conditions for minimizing travel time of passengers. Discrete Dynamics in Nature and Society, 2013, Article ID 930562, p. 8.

[10] Official Journal of the European Union 26.5.2016. available at https://www.era.europa. eu/activities/technical-specifications-interoperability_en, (accessed 25 April 2019).

[11] Mesa, J. A., Ortega, F. A. & Pozo, M. A., Effective allocation of fleet frequencies by reducing intermediate stops and short turning in transit systems, Lecture Notes in Computer Science, 5868(8), pp. 293 – 309, 2009.

[12] Sun, A. & Hickman, M., The real-time stop-skipping problem. Journal of Intelligent Transportation Systems, 9(2), pp. 91–109, 2005.

[13] Vuchic, V.R., Skip-stop operation as a method for transit speed increase. Traffic Quarterly, 27, pp. 307–327, 1973.

[14] Eberlein, X. J., Wilson, N. H., Barnhart, C. & Bernstein, D., The real-time deadheading problem in transit operations control. Transportation Research Part B: Methodological, 32(2), pp. 77–100, 1998.

[15] Yu, B., Yang, Z. & Li, S., Real-time partway deadheading strategy based on transit service reliability assessment. Transportation Research Part A: Policy and Practice, 46(8), pp. 1265–1279, 2012.

[16] Fu, L. & Liu, Q., Real-time optimization model for dynamic scheduling of transit operations. Transportation Research Record Journal of the Transportation Research Board, 1857(1), pp. 48–55, 2003.

[17] Vuchic, V.R., Skip-Stop Operation: high speed with good area coverage. Revue de I’UITP, 2, pp. 105–128, 1976.

[18] Vuchic, V.R., Urban Transit: Operations, Planning and Economics, John Wiley & Sons, 2005. ISBN: 978-0-471-63265-8.

[19] Ghoneim, N. & Wirasinghe, S., Optimum zone structure during peak periods for existing urban rail lines. Transportation Research Part B, 20(1) (1986), pp. 7–18, 1986.

[20] Nemhauser, G., Scheduling local and express service. Transportation Science, 3, pp. 164–175, 1969.

[21] Assad, A., A class of train-scheduling problems. Transportation Science, 16, pp. 281–310, 1982.

[22] Chang, Y., Yeh, C. & Shen, C., A multiobjective model for passenger train services planning: Application to Taiwan’s high-speed rail line. Transportation Research Part B, 34, pp. 91–106, 2000.

[23] Fu, L., Liu, Q. & Calamai, P., Real-time optimization model for dynamic scheduling of transit operations. Proceedings of the 82nd Annual Meeting of the Transportation Research Board, pp. 48–55, 2003.

[24] Larrain, H., Giesen, R. & Muñoz, J. C., Choosing the right express services for bus corridor with capacity restrictions. Transportation Research Record, 2197, pp. 63–70, 2010.

[25] Wang, D. Z., Nayan, A. & Szeto, W. Y., Optimal bus service design with limited stop services in a travel corridor. Transportation Research Part E: Logistics and Transportation Review, 111, pp. 70–86, 2018.

[26] Sun, C., Zhou, W. & Wang, Y., Scheduling combination and headway optimization of bus rapid transit. Journal of Transportation Systems Engineering and Information Technology, 8(5), pp. 61–67, 2008.

[27] Niu, H., Determination of the skip-stop scheduling for a congested transit line by bilevel genetic algorithm. International Journal of Computational Intelligence Science, 4(6), pp. 1158–1167, 2011.

[28] Liu, Z., Yan, Y., Qu, X. & Zhang, Y., Bus stop-skipping scheme with random travel time. Transportation Research Part C, 35, pp. 46–56, 2013.

[29] Lin, D. & Ku, Y., Using genetic algorithms to optimize stopping patterns for passenger rail transportation. Computer-Aided Civil and Infrastructure Engineering, 29, pp. 264–278, 2014.

[30] Chen, X., Hellinga, B., Chang, C. & Fu, L., Optimization of headways with stop-skipping control: A case study of bus rapid transit system. Journal of Advance Transportation, 49, pp. 385–401, 2015.

[31] Cao, Z., Yuan, Z. & Li, D. Estimation method for a skip-stop operation strategy for urban rail transit in China. Journal of Modern Transportation, 22(3), pp. 174–182, 2014.

[32]  Boschetti M.A., Maniezzo V., Roffilli M. & Bolufé Röhler A., Matheuristics: Optimization, Simulation and Control. In: Blesa M.J., Blum C., Di Gaspero L., Roli A., Sampels M., Schaerf A. (eds) Hybrid Metaheuristics. HM 2009. Lecture Notes in Computer Science, 5818, 2009. Springer, Berlin, Heidelberg.

[33] Maniezzo, V., Stützle, T. & Voss, S. (eds.), Matheuristics: Hybridizing metaheuristics and mathematical programming. Annals of Information Systems, 10. Springer, Heidelberg, 2009.

[34] Maniezzo, V., Voss, S. & Hansen, P., Special issue on mathematical contributions to metaheuristics editorial. Journal of Heuristics, 15(3), 2009.

[35] Hall, K.M., An r-Dimensional quadratic placement algorithm. Management Science, 17, pp. 219–229, 1970.

[36] Martello, S. & Toth, P., Solution of the zero-one multiple knapsack problem. European Journal of Operational Research, 4, pp. 276–283, 1980.

[37] Kellerer, H., Pisinger, D. & Pferschy, U., Knapsack Problems, Springer-Verlag Berlin Heidelberg: Germany, 2004.