Un Algoritmo Genético para Resolver el Problema de Asignar y Secuenciar Entregas con Restricción de Ventanas de Tiempo-Edición Única

Hdl Handle:
http://hdl.handle.net/11285/572509
Title:
Un Algoritmo Genético para Resolver el Problema de Asignar y Secuenciar Entregas con Restricción de Ventanas de Tiempo-Edición Única
Authors:
Torres Matus, José R.
Issue Date:
2005-12-01
Abstract:
En la presente investigación se muestra la aplicación de una de las técnicas de la Computación Evolutiva conocida como Algoritmos Genéticos (AG), para resolver de manera eficiente una variante del problema de ruteo de vehículos con restricciones de ventanas de tiempo (VRPTW por sus siglas en ingles). Motivado por una problemática real se presenta el desarrollo de un algoritmo que logra llevar a cabo la programación de una flotilla de vehículos para atender la demanda diaria de doce centros de distribución ubicados en diversas zonas geográficas; cada centro de distribución cuenta con ventanas de tiempo predefinidas y demandas diarias conocidas. Los vehículos disponibles para realizar las entregas son considerados con capacidades de carga homogéneas y están disponibles las veinticuatro horas del día. En cada una de las entregas realizadas, que inician y terminan en un depósito central, se atiende específicamente a un centro de distribución. El objetivo central de este trabajo, es lograr minimizar el número de vehículos utilizados por día a través de una secuenciación eficiente que permita una mayor utilización de los vehículos y al mismo tiempo, disminuya el tiempo de espera para una nueva reasignación de viajes. En este estudio se construye una población inicial haciendo uso de un algoritmo mejorador de búsqueda local (glotón) para resolver el problema de asignar los viajes y secuenciar los vehículos con los cuales se atenderá la demanda. Posteriormente se ejecuta un algoritmo genético simple para desarrollar una exploración global dentro del conjunto de toda la población de soluciones encontradas. Con una distribución uniforme para representar la demanda de viajes de la planta a los 12 CDí y un diseño experimental completamente al azar con 5 replicas se generaron 12 instancias para evaluar el desempeño del algoritmo. Posteriormente los resultados obtenidos fueron comparados contra los resultados generados haciendo uso del algoritmo 1-RBH programado en CPlex 81 (González, 2005) en el cual fueron evaluadas las mismas instancias; los resultados obtenidos por este medio sirvieron para la definición de una cota inferior la cual facilitó el análisis del desempeño del algoritmo genético propuesto.
Keywords:
Computación Evolutiva; Secuenciar entregas eficientes; Algoritmo; Vehiculos
Degree Program:
Programa de Graduados en Administración
Advisors:
Dr. Juan Gaytán Iniestra
Degree Level:
Doctor en Administración
Campus Program:
Campus Ciudad de México
Discipline:
Negocios y Economía / Business & Economics
Appears in Collections:
Ciencias Sociales

Full metadata record

DC FieldValue Language
dc.contributor.advisorDr. Juan Gaytán Iniestraen
dc.contributor.authorTorres Matus, José R.en
dc.date.accessioned2015-08-17T11:34:02Zen
dc.date.available2015-08-17T11:34:02Zen
dc.date.issued2005-12-01-
dc.identifier.urihttp://hdl.handle.net/11285/572509en
dc.description.abstractEn la presente investigación se muestra la aplicación de una de las técnicas de la Computación Evolutiva conocida como Algoritmos Genéticos (AG), para resolver de manera eficiente una variante del problema de ruteo de vehículos con restricciones de ventanas de tiempo (VRPTW por sus siglas en ingles). Motivado por una problemática real se presenta el desarrollo de un algoritmo que logra llevar a cabo la programación de una flotilla de vehículos para atender la demanda diaria de doce centros de distribución ubicados en diversas zonas geográficas; cada centro de distribución cuenta con ventanas de tiempo predefinidas y demandas diarias conocidas. Los vehículos disponibles para realizar las entregas son considerados con capacidades de carga homogéneas y están disponibles las veinticuatro horas del día. En cada una de las entregas realizadas, que inician y terminan en un depósito central, se atiende específicamente a un centro de distribución. El objetivo central de este trabajo, es lograr minimizar el número de vehículos utilizados por día a través de una secuenciación eficiente que permita una mayor utilización de los vehículos y al mismo tiempo, disminuya el tiempo de espera para una nueva reasignación de viajes. En este estudio se construye una población inicial haciendo uso de un algoritmo mejorador de búsqueda local (glotón) para resolver el problema de asignar los viajes y secuenciar los vehículos con los cuales se atenderá la demanda. Posteriormente se ejecuta un algoritmo genético simple para desarrollar una exploración global dentro del conjunto de toda la población de soluciones encontradas. Con una distribución uniforme para representar la demanda de viajes de la planta a los 12 CDí y un diseño experimental completamente al azar con 5 replicas se generaron 12 instancias para evaluar el desempeño del algoritmo. Posteriormente los resultados obtenidos fueron comparados contra los resultados generados haciendo uso del algoritmo 1-RBH programado en CPlex 81 (González, 2005) en el cual fueron evaluadas las mismas instancias; los resultados obtenidos por este medio sirvieron para la definición de una cota inferior la cual facilitó el análisis del desempeño del algoritmo genético propuesto.en
dc.language.isoesen
dc.rightsOpen Accessen
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.titleUn Algoritmo Genético para Resolver el Problema de Asignar y Secuenciar Entregas con Restricción de Ventanas de Tiempo-Edición Únicaen
dc.typeTesis de Doctoradoes
thesis.degree.grantorInstituto Tecnológico y de Estudios Superiores de Monterreyes
thesis.degree.levelDoctor en Administraciónen
thesis.degree.namePrograma de Graduados en Administraciónen
dc.subject.keywordComputación Evolutivaen
dc.subject.keywordSecuenciar entregas eficientesen
dc.subject.keywordAlgoritmoen
dc.subject.keywordVehiculosen
thesis.degree.programCampus Ciudad de Méxicoen
dc.subject.disciplineNegocios y Economía / Business & Economicsen
All Items in REPOSITORIO DEL TECNOLOGICO DE MONTERREY are protected by copyright, with all rights reserved, unless otherwise indicated.