A Hybrid Column Generation and Clustering Approach to the School Bus Routing Problem with Time Windows

Un Aproximación Híbrida de Generación de Columnas y Agrupación para Resolver el Problema de Ruteo de Buses Escolares conVentanas de Tiempo</i>

  • Eduyn Ramiro Lopez Santana Universidad Distrital Francisco José de Caldas
  • Jose de Jesus Romero Carvajal Universidad Distrital Francisco José de Caldas
Keywords: clustering, column generation, optimization, school bus routing (en_US)

Abstract (en_US)

This paper attempts to solve the School Bus Routing Problem with Time Windows that consists of finding the best set of routes to pick up students distributed geographically with constraints as capacity, time windows and maximum travel time. We formulated the problem as a classic Vehicle Routing Problem with Time Windows and solved it using an approach based on a clustering algorithm and column generation method. A real world case from a school in Bogota, Colombia is presented including 600 students to pick up ´ in near 400 nodes located in urban and rural areas. The obtained results demonstrate a reduction as the problem’s complexity and an improvement on the performance measures of the proposed method.

Abstract (es_ES)

Este artículo intenta resolver el problema de ruteo de buses escolares con ventanas de tiempo el cual consiste en encontrar el mejor conjunto de rutas para recoger estudiantes geográficamente distribuidos con restricciones de ventanas de tiempo. El problema es formulado como un clásico problema de ruteo de vehículos con ventanas de tiempo y resuelto una aproximación basada en agrupación y generación de columnas. Se presenta un casode aplicación real en un colegio de Bogotá, Colombia con 600 estudiantes y 400 nodos localizados en área urbana y rural. Los resultados obtenidos muestran como la complejidad del problema es reducida y se mejoran las medidas de desempeño.

Downloads

Download data is not yet available.

Author Biographies

Eduyn Ramiro Lopez Santana, Universidad Distrital Francisco José de Caldas
Profesor Asistente de la Facultad de Ingenieria, Universidad Distrital Francisco José de Caldas
Jose de Jesus Romero Carvajal, Universidad Distrital Francisco José de Caldas
Ingeniero Industrial

References

J. Park y B.-I. Kim, “ The school bus routing problem: A review” , Eur. J. Oper. Res., vol. 202, n.o 2, pp. 311-319, abr. 2010.

G. K. Rand, “ The life and times of the Savings Method for Vehicle Routing Problems” , ORiON, vol. 25, n.o 2, dic. 2009.

A. Olivera, “ Heurísticas para problemas de Ruteos de Vehículos”. Universidad de la Republica, Montevideo, Uruguay, 2004.

G. B. Dantzig y J. H. Ramser, “ The truck dispatching problem” , Manag. Sci., vol. 6, n.o 1, pp. 80–91, 1959.

G. Laporte y Y. Nobert, “ Exact algorithms for the vehicle routing problem” , Surv. Comb. Optim., vol. 31, pp.147–184, 1987.

G. Laporte, “ The vehicle routing problem: An overview of exact and approximate algorithms” , Eur. J. Oper.Res., vol. 59, n.o 3, pp. 345–358, 1992.

P. Toth y D. Vigo, The vehicle routing problem. Philadelphia: Society for Industrial and Applied Mathematics,2002.

J. S. Arias-Rojas, J. F. Jimenez, y J. R. Montoya-Torres, “ Solving of school bus routing problem by ant colony optimization.” , Rev. EIA, n.o 17, 2012.

M. Spada, M. Bierlaire, y T. M. Liebling, “ Decision-aiding methodology for the school bus routing and scheduling problem” , Transp. Sci., vol. 39, n.o 4, pp. 477–490, 2005.

T. Bektas y S. Elmastas, “ Solving school bus routing problems through integer programming” , J. Oper. Res. Soc., vol. 58, n.o 12, pp. 1599–1604, 2006.

G. Desaulniers, J. Desrosiers, y M. M. Solomon, Column generation, vol. 5. Springer, 2005.

K. Shin y S. Han, “ A Centroid-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem” ,Comput. Inform., vol. 30, n.o 4, pp. 721-732, ene. 2012.

D. Simchi-Levi, X. Chen, y J. Bramel, “ A case study: School bus routing” , Log. Logist. Theory Algorithms Appl. Logist. Supply Chain Manag., pp. 319–335, 2005.

How to Cite
Lopez Santana, E. R., & Romero Carvajal, J. de J. (2015). A Hybrid Column Generation and Clustering Approach to the School Bus Routing Problem with Time Windows. Ingeniería, 20(1), 111-127. https://doi.org/10.14483/udistrital.jour.reving.2015.1.a07
Published: 2015-03-04
Section
Special Section: Best Works "VII Symposium on Optimization"