DOI:

https://doi.org/10.14483/23448393.15835

Publicado:

2021-05-30

Número:

Vol. 26 Núm. 2 (2021): Mayo-Agosto

Sección:

Ingeniería de Sistemas

Una solución metaheurística al problema de planificación de rutas de auto-buses escolares con flota homogénea y selección de paradas

A Metaheuristic Solution for School Bus Routing Problem with Homogeneous Fleet and Bus Stop Selection

Autores/as

Palabras clave:

metaheurísticas, modelo de optimización, planificación de rutas de autobuses escolares, SBRP (es).

Palabras clave:

metaheuristics, optimization model, SBRP, school bus routing problem (en).

Descargas

Resumen (es)

Contexto: Los problemas de optimización permiten representar situaciones de la vida real, y con un método apropiado se puede llegar a una buena solución del problema. Conceptualmente, este problema se conoce como el problema de planificación de ruta de autobuses escolares. El presente trabajo puede ser tomado como punto de partida para la creación de herramientas para este problema.

Método: En el trabajo se diseñó e implementó un modelo matemático del problema que se basa en uno de la literatura y que se adapta para su solución usando algoritmos metaheurísticos. Se implementaron tres operadores de mutación y un mecanismo de selección entre ellos basado en pesos según las mejoras que brindaba cada uno a la solución. Para evaluar los resultados se realizó una comparación estadística con otra solución de la literatura a partir de la evaluación de 112 instancias del problema.

Resultados: En la solución de las 112 instancias del problema fueron utilizados los algoritmos: Búsqueda Tabú, variantes del Escalador de Colinas, Recocido Simulado y un Portafolio de Algoritmos que incluye a los anteriores. Los resultados reflejaron que el mejor comportamiento lo obtuvo el Portafolio con resultados comparables a los de la literatura. Sin embargo, a medida que crecen las instancias los resultados tienden a empeorar.

Conclusiones: Con el trabajo realizado, se obtuvo un modelo que permite representar el problema inicial. Así como, dos algoritmos para la búsqueda de soluciones utilizando metaheurísticas. Según los resultados obtenidos, los trabajos futuros deben encaminarse hacia nuevas formas de construcción de la solución inicial, y la implementación de nuevos operadores de asignación y mutación.

Resumen (en)

Context: Optimization problems allow real-life situations to be represented, and with a proper method a good solution to the problem can be reached. Conceptually, this problem is known as the School Bus Routing Problem. This work can be taken as a starting point for the creation of tools for this problem.

Method: In the work, a mathematical model was designed and implemented based on one of the literature which is adapted to be solved by using metaheuristics. Three mutation operators and a selection mechanism among them based on weights were implemented according to the improvements each offered to the solution. To evaluate the results, a statistical comparison was made with another solution in the literature based on the evaluation of 112 instances of the problem.

Results: In the solution of the 112 instances of the problem, the Tabu Search, Hill Climbing variants, Simulated Annealing and Algorithm Portfolio that includes the previous ones were used. The results showed that the best behavior was obtained by the Portfolio with results comparable to those of the literature. However, as the instances grow the results tend to get worse.

Conclusions: With the work done, it was possible to obtain a model that represents the problem of planning school bus routes. As well as, obtaining two algorithms for finding solutions using metaheuristics. When carrying out an analysis of the results obtained, it is appreciated that future work should be directed towards new ways of building the initial solution, and the implementation of new assignment operators.

Referencias

R. Newton and W. Thomas, "Design of school bus routes by computer," Socio-Econ. Plan. Sci. , vol. 3, pp. 75-85, 1969. doi: https://doi.org/10.1016/0038-0121(69)90051-2.

L. Li and Z. Fu, "The school bus routing problem: a case study," Journal of the Operational Research Society, vol. 53, no. 5, pp. 552–558 2002. doi: https://doi.org/10.1057/palgrave.jors.2601341.

F. M. Lima, "A mixed load capacitated rural school bus routing problem with heterogeneous fleet: Algorithms for the Brazilian context.," 56 Tesis de Diploma, Expert Systems with Applications, 2016, doi: https://doi.org/10.1016/j.eswa.2016.03.005.

M. Fonseca, J. Machry, C. Silva, M. Porto, and N. Ramos, "A real geographical application for the school bus routing problem," presented at the 17th International Conference on Intelligent Transportation Systems (ITSC), 2014. doi: https://doi.org/10.1109/ITSC.2014.6958132.

E. López and R. J., "A hybrid column generation and clustering approach to the school bus routing problem with time windows," Ingeniería, vol. 20, no. 1, pp. 111-127, 2015. doi: http://dx.doi.org/10.14483/udistrital.jour.reving.2015.1.a07.

A. Bock, E. Grant, J. Könemann, and L. Sanità, "The school bus problem on trees," in International Symposium on Algorithms and Computation, 2011, pp. 10–19: Springer, doi: https://doi.org/10.1007/s00453-012-9711-x.

D. M. Miranda, R. de Camargo, S. Conceiao, M. Porto, and N. Nunes, "A multi-loading school bus routing problem," Expert Systems With Applications, vol. 101, pp. 228–242, 2018. doi: https://doi.org/10.1016/j.eswa.2018.02.014.

E. Talbi, John Wiley & Sons, Ed. Metaheuristics: From design to implementation (no. Wiley Series on Parallel and Distributed Computing). John Wiley & Sons, Inc., 2009, p. 500.

J. Park and B. Kim, "The school bus routing problem. A review.," European Journal of Operational Research, vol. 202, pp. 311–319, 2010. doi: https://doi.org/10.1016/j.ejor.2009.05.017.

W. Ellegood, S. Solomon, J. North, and J. Campbell, "School bus routing problem: contemporary trends and research directions," Omega, 2019. doi: https://doi.org/10.1016/j.omega.2019.03.014.

J. Riera-Ledesma and J. Salazar-González., "A column generation approach for a school bus routing problem with resource constraints," Computers and Operations Research vol. 40, pp. 566–583, 2013. doi: https://doi.org/10.1016/j.cor.2012.08.011.

R. Bowerman, B. Hall, and P. Calamai, " A multi-objective optimization approach to urban school bus routing: Formulation and solution method," Transportation Research Part A: Policy and Practice, vol. 29A, no. 2, pp. 107-123, 1995. doi: https://doi.org/10.1016/0965-8564(94)E0006-U.

P. Schittekat, J. Kinable, K. Sörensen, M. Sevaux, F. Spieksma, and J. Springael, " A metaheuristic for the school bus routing problem with bus stop selection," European Journal of Operational Research, vol. 229, no. 2, pp. 518-528, 2013. doi: https://doi.org/10.1016/j.ejor.2013.02.025.

X. Chen, Y. Kong, L. Dang, Y. Hou, and X. Ye, "Exact and Metaheuristic Approaches for a Bi-Objective School Bus Scheduling Problem," PLoSONE, vol. 10, no. 7, 2015. doi: 10.1371/journal.pone.0132600.

M. Spada, M. Bierlaire, and M. Liebling, "Decision-Aiding methodology for the school bus routing and scheduling problem," Transportation Science, vol. 39, no. 4, pp. 477-490, 2005. doi: https://doi.org/10.1287/trsc.1040.0096.

D.-S. Chen, H. A. Kallsen, H.-C. Chen, and V.-C. Tseng, "A bus routing system for rural school districts," Computers & Industrial Engineering, vol. 19, no. 1-4, pp. 322-325, 1990. doi: https://doi.org/10.1016/0360-8352(90)90131-5.

J. Kinable, F. Spieksma, and G. Vanden, "School bus routing—a column generation approach," International Transactions in Operational Research, vol. 21, no. 3, pp. 453–478, 2014. doi: https://doi.org/10.1111/itor.12080.

S. Eguizába, J. Berodia, A. Portilla, and J. Ponce, "Optimization model for school transportation design based on economic and social efficiency," Transport policy, vol. 67, pp. 93-101, 2018. doi: https://doi.org/10.1016/j.tranpol.2018.01.015.

H. Caceres, R. Batta, and Q. He, "School bus routing with stochastic demand and duration constraints," Transportation Science, 2017. doi: https://doi.org/10.1287/trsc.2016.0721.

F. M. de Souza Lima, D. S. D. Pereira, S. V. da Conceição, and R. Camargo, "A multi-objective capacitated rural school bus routing problem with heterogeneous fleet and mixed loads," 4OR-A Quarterly Journal of Operations Research, vol. 15, pp. 359–386 2017. doi: https://doi.org/10.1007/s10288-017-0340-8.

J. Pacheco and R. Mart, "Tabu search for a multi-objective routing problem," Journal of the Operational Research Society vol. 57, 2006. doi: https://doi.org/10.1057/palgrave.jors.2601917.

A. Corbern, E. Fernndez, M. Laguna, and R. Mart, "Heuristic solutions to the problem of routing school buses with multiple objectives," Journal of Operational Research Society vol. 53, 2002. doi: https://doi.org/10.1057/palgrave.jors.2601324.

L. Sales, C. Sousa, T. Oliveira, and B. Athayde, "Memetic algorithm for the heterogeneous fleet school bus routing problem," Journal of Urban Planning Development, vol. 144, no. 2, p. 04018018, 2018.

J. Braca, J. Bramel, B. Posner, and D. Simchi-Levi, "A computerized approach to the new york city school bus routing problem," IIE Transactions vol. 29, 1997. doi: https://doi.org/10.1023/A:1018526202990.

B. Crawford, R. Soto, E. Monfroy, G. Astorga, J. García, and E. Cortes, "A Meta-Optimization Approach to Solve the Set Covering Problem.," Ingeniería, vol. 23, no. 3, pp. 274-288, 2018. doi: https://doi.org/10.14483/23448393.13247.

J. Fajardo, "Soft Computing en problemas de optimización dinámicos.," Tesis Doctoral, Universidad de Granada, Granada, 2016, doi: http://hdl.handle.net/10481/42206.

R. Lewis, K. Smith-Miles, and K. Phillips, "The School Bus Routing Problem. An Analysis and Algorithm," vol. 10765, ed, 2018, pp. 287–298, doi: https://doi.org/10.1007/978-3-319-78825-8_24.

E. Toro, A. Escobar, and M. Granada, "Literature review on the vehicle routing problem in the green transportation context," Luna Azul, vol. 42, pp. 362-387, 2016. doi: http://dx.doi.org/10.17151/luaz.2016.42.21.

D. Wolpert and W. Macready, "No free lunch theorems for optimization," IEEE Transactions on evolutionary computation, vol. 1, no. 1, pp. 67 - 82, 1997. doi: https://doi.org/10.1109/4235.585893.

J. Derrac, S. García, D. Molina, and F. Herrera, "A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms," Swarm and Evolutionary Computation, vol. 1, pp. 3-18, 2011. doi: https://doi.org/10.1016/j.swevo.2011.02.002.

Cómo citar

APA

Pérez Pérez, A. C., Sánchez-Ansola, E., & Rosete, A. (2021). Una solución metaheurística al problema de planificación de rutas de auto-buses escolares con flota homogénea y selección de paradas. Ingeniería, 26(2). https://doi.org/10.14483/23448393.15835

ACM

[1]
Pérez Pérez, A.C., Sánchez-Ansola, E. y Rosete, A. 2021. Una solución metaheurística al problema de planificación de rutas de auto-buses escolares con flota homogénea y selección de paradas. Ingeniería. 26, 2 (may 2021). DOI:https://doi.org/10.14483/23448393.15835.

ACS

(1)
Pérez Pérez, A. C.; Sánchez-Ansola, E.; Rosete, A. Una solución metaheurística al problema de planificación de rutas de auto-buses escolares con flota homogénea y selección de paradas. Ing. 2021, 26.

ABNT

PÉREZ PÉREZ, A. C.; SÁNCHEZ-ANSOLA, E.; ROSETE, A. Una solución metaheurística al problema de planificación de rutas de auto-buses escolares con flota homogénea y selección de paradas. Ingeniería, [S. l.], v. 26, n. 2, 2021. DOI: 10.14483/23448393.15835. Disponível em: https://revistas.udistrital.edu.co/index.php/reving/article/view/15835. Acesso em: 26 sep. 2021.

Chicago

Pérez Pérez, Ana Camila, Eduardo Sánchez-Ansola, y Alejandro Rosete. 2021. «Una solución metaheurística al problema de planificación de rutas de auto-buses escolares con flota homogénea y selección de paradas». Ingeniería 26 (2). https://doi.org/10.14483/23448393.15835.

Harvard

Pérez Pérez, A. C., Sánchez-Ansola, E. y Rosete, A. (2021) «Una solución metaheurística al problema de planificación de rutas de auto-buses escolares con flota homogénea y selección de paradas», Ingeniería, 26(2). doi: 10.14483/23448393.15835.

IEEE

[1]
A. C. Pérez Pérez, E. Sánchez-Ansola, y A. Rosete, «Una solución metaheurística al problema de planificación de rutas de auto-buses escolares con flota homogénea y selección de paradas», Ing., vol. 26, n.º 2, may 2021.

MLA

Pérez Pérez, A. C., E. Sánchez-Ansola, y A. Rosete. «Una solución metaheurística al problema de planificación de rutas de auto-buses escolares con flota homogénea y selección de paradas». Ingeniería, vol. 26, n.º 2, mayo de 2021, doi:10.14483/23448393.15835.

Turabian

Pérez Pérez, Ana Camila, Eduardo Sánchez-Ansola, y Alejandro Rosete. «Una solución metaheurística al problema de planificación de rutas de auto-buses escolares con flota homogénea y selección de paradas». Ingeniería 26, no. 2 (mayo 30, 2021). Accedido septiembre 26, 2021. https://revistas.udistrital.edu.co/index.php/reving/article/view/15835.

Vancouver

1.
Pérez Pérez AC, Sánchez-Ansola E, Rosete A. Una solución metaheurística al problema de planificación de rutas de auto-buses escolares con flota homogénea y selección de paradas. Ing. [Internet]. 30 de mayo de 2021 [citado 26 de septiembre de 2021];26(2). Disponible en: https://revistas.udistrital.edu.co/index.php/reving/article/view/15835

Descargar cita

Visitas

93

Dimensions


PlumX


Descargas

Los datos de descargas todavía no están disponibles.