Show simple item record

dc.rights.licenseAtribución-NoComercial 4.0 Internacional
dc.contributorPinzón, Yoan
dc.contributor.authorBarajas Mora, Wilson Nicolás
dc.date.accessioned2019-06-24T23:52:27Z
dc.date.available2019-06-24T23:52:27Z
dc.date.issued2010
dc.identifier.urihttps://repositorio.unal.edu.co/handle/unal/11126
dc.description.abstractEn 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.
dc.format.mimetypeapplication/pdf
dc.language.isospa
dc.relation.ispartofUniversidad Nacional de Colombia Sede Bogotá Facultad de Ingeniería Departamento de Ingeniería de Sistemas e Industrial Ingeniería de Sistemas
dc.relation.ispartofIngeniería de Sistemas
dc.rightsDerechos reservados - Universidad Nacional de Colombia
dc.rights.urihttp://creativecommons.org/licenses/by-nc/4.0/
dc.subject.ddc62 Ingeniería y operaciones afines / Engineering
dc.titleDesarrollo de un algoritmo heurístico para establecer las rutas de transporte escolar de la secretaría de educación de Bogotá
dc.typeTrabajo de grado - Maestría
dc.type.driverinfo:eu-repo/semantics/masterThesis
dc.type.versioninfo:eu-repo/semantics/acceptedVersion
dc.identifier.eprintshttp://bdigital.unal.edu.co/8520/
dc.description.degreelevelMaestría
dc.relation.referencesBarajas 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.
dc.rights.accessrightsinfo:eu-repo/semantics/openAccess
dc.subject.proposalAlgoritmo
dc.subject.proposalHeurística
dc.subject.proposalOptimización combinatoria
dc.subject.proposalRuteo escolar / Algorithm
dc.subject.proposalHeuristic
dc.subject.proposalCombinatorial optimization
dc.subject.proposalScholar routing
dc.title.translatedDevelopment of a heuristic algorithm to establish the school bus routes of the secretary of education of Bogotá
dc.type.coarhttp://purl.org/coar/resource_type/c_bdcc
dc.type.coarversionhttp://purl.org/coar/version/c_ab4af688f83e57aa
dc.type.contentText
dc.type.redcolhttp://purl.org/redcol/resource_type/TM
oaire.accessrightshttp://purl.org/coar/access_right/c_abf2


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Atribución-NoComercial 4.0 InternacionalThis work is licensed under a Creative Commons Reconocimiento-NoComercial 4.0.This document has been deposited by the author (s) under the following certificate of deposit