Escudo de la República de Colombia
Sistema Nacional de Biliotecas - Repositorio Institucional Universidad Nacional de Colombia Biblioteca Digital - Repositorio Institucional UN Sistema Nacional de Bibliotecas UN

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á

Barajas Mora, Wilson Nicolás (2010) 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á. Maestría thesis, Universidad Nacional de Colombia.

Texto completo

[img] PDF - Versión Aceptada
Available under License Creative Commons Attribution Non-commercial No Derivatives.

12MB

Resumen

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.

Tipo de documento:Tesis/trabajos de grado - Thesis (Maestría)
Colaborador / Asesor:Pinzón, Yoan
Información adicional:Magister en Ingeniería de Sistemas y Computación.
Palabras clave:Algoritmo; Heurística; Optimización combinatoria; Ruteo escolar / Algorithm; Heuristic; Combinatorial optimization; Scholar routing
Temática:6 Tecnología (ciencias aplicadas) / Technology > 62 Ingeniería y operaciones afines / Engineering
Unidad administrativa:Sede Bogotá > Facultad de Ingeniería > Departamento de Ingeniería de Sistemas e Industrial > Ingeniería de Sistemas
Código ID:8520
Enviado por : Universidad Nacional de Colombia Biblioteca Digital - Sede Bogotá
Enviado el día :26 Dec 2012 15:57
Ultima modificación:26 Dec 2012 15:57
Ultima modificación:26 Dec 2012 15:57
Exportar:Clic aquí
Estadísticas:Clic aquí
Compartir:

Solamente administradores del repositorio: página de control del ítem

Vicerrectoría de Investigación: Número uno en investigación
Indexado por:
Indexado por Scholar Google WorldCat DRIVER Registry of Open Access Repositories OpenDOAR Metabiblioteca BDCOL OAIster Red de repositorios latinoamericanos DSpace BASE Open archives La referencia Colombiae Open Access Theses and Dissertations Tesis latinoamericanas CLACSO
Este sitio web se ve mejor en Firefox