Desarrollo de un algoritmo heurístico para establecer las rutas de transporte escolar de la secretaría de educación de Bogotá / Development of a heuristic algorithm to establish the school bus routes of the secretary of education of Bogotá

Abstract

En este trabajo se presenta un nuevo algoritmo para resolver el Problema de Ruteo de Vehículos con Capacidades (CVRP), después se realiza una adaptación de éste para resolver el problema de ruteo escolar de la Secretaría de Educación de Bogotá (SED), para el cual se tiene una información de demandas, paraderos y colegios obtenida de las bases de datos y geográficas del proyecto de 'INTERVENTORÍA DE LOS CONTRATOS DEL SERVICIO DE TRANSPORTE ESCOLAR, DE LOS ESTABLECIMIENTOS EDUCATIVOS DEL DISTRITO' el cual fue un convenio interadministrativo entre la Universidad Nacional de Colombia y la Secretaría de Educación de Bogotá. Mediante una serie de análisis de resultados del algoritmo planteado se concluye que a partir éste se obtienen soluciones competitivas con el uso razonable de recursos. A través de la aplicación de este algoritmo al problema de ruteo de la Secretaría se obtienen mejoramientos en distancia de aproximadamente el 22% sobre las rutas actuales que son definidas intuitivamente por algunos de los actores del sistema, teniendo en cuenta ciertas situaciones como las diferentes zonas de vivienda de los estudiantes y la demanda asociada. Primero, se generan soluciones factibles iniciales basadas en algoritmos de barrido existentes para resolver el Problema de Ruteo de Vehículos (VRP) y en algoritmos de inserción existentes para resolver el Problema del Agente Viajero (TSP). Después se aplica un algoritmo de mejoramiento teniendo como base ciertos operadores definidos en la literatura para esta clase de algoritmos. En seguida el algoritmo es modificado e implementado para resolver el problema de rutas escolares de la SED y finalmente se muestran los resultados obtenidos para los colegios pertenecientes a una de las localidades de la ciudad dando algunas pautas de factibilidad de implementación para todo el sistema de rutas de la Secretaría. / Abstract. This works presents a new algorithm for solving the Capacitated Vehicle Routing Problem (CVRP), then presents an adaptation of this algorithm for solving the Secretary of Education of Bogotá (SED) scholar routing problem, for which information is available on demands, stops and schools, these data were obtained from databases of project “INTERVENTORÍA DE LOS CONTRATOS DEL SERVICIO DE TRANSPORTE ESCOLAR, DE LOS ESTABLECIMIENTOS EDUCATIVOS DEL DISTRITO”, which was an agreement between the National University of Colombia and the SED. Through a series of algorithm analysis results it is concluded that raised it from competitive solutions are obtained with the reasonable use of resources. Through the application of this algorithm to the problem of routing of the SED are obtained improvements in distance from approximately 22% on existing routes that are defined intuitively by some of the key players, taking into account certain situations such as different areas live to the students and the associated demand. First, we generate initial feasible solutions based on existing sweep algorithms to solve the Vehicle Routing Problem (VRP) and insertion algorithms exist to solve the traveling salesman problem (TSP). After implementing an improvement algorithm based taking certain operators defined in the literature for this class of algorithms. Then the algorithm is modified and implemented to solve the problem of school routes of the SED and finally we show the results obtained for the schools from one of the locations of town with some guidelines for implementation feasibility of the entire system of routes of the SED.