Show simple item record

Professor Advisordc.contributor.advisorOrdóñez Pizarro, Fernando
Authordc.contributor.authorBahamonde Goldberg, Simón Andrés
Associate professordc.contributor.otherCortés Carrillo, Cristián
Associate professordc.contributor.otherGonzález Hasbún, Víctor
Admission datedc.date.accessioned2021-10-14T21:47:42Z
Available datedc.date.available2021-10-14T21:47:42Z
Publication datedc.date.issued2021
Identifierdc.identifier.urihttps://repositorio.uchile.cl/handle/2250/182287
Abstractdc.description.abstractEn la literatura, el problema de ruteo de vehículos (VRP) ha sido intensamente estudiado desde el año 1959, tras ser propuesto por George Dantzig y John Ramser en 1959. En la actualidad, existen muchas variaciones de dicho problema, con el objetivo de poder generar soluciones que se hagan cargo de las distintas restricciones que presenta el VRP en la realidad. De hecho, en los últimos años la investigación se ha basado en como poder adaptar heurísticas y algoritmos para instancias de gran tamaño, considerando miles de clientes y cientos de vehículos, en especial para su uso en aplicaciones logísticas. Esta tesis presenta una nueva forma de resolver el problema de ruteo de vehículos con ventanas horarias (tanto para los clientes como los vehículos) cuando se cuenta con una flota heterogénea (en cuanto a capacidad y ventana horaria de los vehículos) y con un número fijo de vehículos, así como también, agregando la posibilidad de poder realizar más de un viaje desde y hacia el depósito, si lo anterior es factible en términos del tiempo disponible y de esta manera pudiendo atender más clientes a lo largo del día. Todo lo mencionado anteriormente se realiza mediante una heurística basada en ahorros (savings) para la creación de rutas, una heurística similar al bin packing para la asignación de rutas a vehículos y finalmente una heurística de mejoramiento de rutas mediante movimientos de búsqueda local. Este problema será denotado como VRPTW con Flota Fija Heterogénea y Multi Viajes y dada la implementación escogida, la heurística desarrollada genera soluciones competentes en cuanto a distancia recorrida y utilización de vehículos, así como también una gran rapidez para la generación de dichas soluciones, pudiendo resolver instancias con aproximadamente 2.000 clientes en 4 minutos. Lo anterior significa generar ahorros en tiempo de ejecución de aproximadamente 80% al compararse con soluciones actuales entregadas por empresas como SimpliRoute (las cuales se demoran entre 20 a 30 minutos en resolver dichas instancias) y manteniendo la calidad de sus soluciones, es decir, obteniendo ahorros en los kilómetros recorridos a costa de un leve aumento en la utilización de los vehículos. Cabe mencionar que se generó una heurística que pudiera entregar soluciones de manera rápida, con el fin de atender las reglas de negocios de empresas del área logística, como por ejemplo SimplirRoute, en la que se busca entregar soluciones a todo tipo de instancia en menos de 15 minutos. No obstante, es posible generar modificaciones a la heurística de mejoramiento mencionada con el fin de obtener soluciones aún más competitivas y poder así generar nuevas "mejores soluciones conocidas"(best known solutions) a instancias estudiadas en la literatura.es_ES
Patrocinadordc.description.sponsorshipSimpliRoutees_ES
Lenguagedc.language.isoeses_ES
Publisherdc.publisherUniversidad de Chilees_ES
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 United States*
Link to Licensedc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/us/*
Keywordsdc.subjectAsignación de tráfico
Keywordsdc.subjectRutas comerciales
Keywordsdc.subjectLogística
Keywordsdc.subjectFlotas de vehículos
Keywordsdc.subjectMultiviajes
Keywordsdc.subjectVRP
Títulodc.titleUna nueva heurística de construcción y mejoramiento basada en ahorros para instancias grandes del problema de ruteo de vehículoses_ES
Document typedc.typeTesises_ES
dc.description.versiondc.description.versionVersión original del autores_ES
dcterms.accessRightsdcterms.accessRightsAcceso abiertoes_ES
Catalogueruchile.catalogadorgmmes_ES
Departmentuchile.departamentoDepartamento de Ingeniería Industriales_ES
Facultyuchile.facultadFacultad de Ciencias Físicas y Matemáticases_ES
uchile.titulacionuchile.titulacionDoble Titulaciónes_ES
uchile.gradoacademicouchile.gradoacademicoMagisteres_ES
uchile.notadetesisuchile.notadetesisTesis para optar al grado de Magíster en Gestión de Operacioneses_ES
uchile.notadetesisuchile.notadetesisMemoria para optar al título de Ingeniero Civil Industrial


Files in this item

Icon
Icon

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 United States
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 United States