Please use this identifier to cite or link to this item:
https://rinacional.tecnm.mx/jspui/handle/TecNM/3219| Title: | Impacto de la búsqueda local aplicada al problema de rutas de vehículos con ventanas de tiempo |
| Authors: | Camara Covarrubias, Jose Ricardo. |
| Issue Date: | 2012-01-01 |
| Publisher: | Tecnológico Nacional de México |
| metadata.dc.publisher.tecnm: | Instituto Tecnológico de Ciudad Madero |
| Description: | En el área de las Ciencias Computacionales, el Problema de Rutas de Vehículos con Ventanas de Tiempo (VRPTW, por sus siglas en inglés) se define como el problema de diseñar rutas con el menor costo de viaje desde un almacén central, a un conjunto de clientes geográficamente dispersos, con demandas conocidas y con horario de atención establecido (ventanas de tiempo). Debido a su relevancia en los ámbitos científicos y sectores productivos y de servicio, el VRPTW ha recibido atención en las ultimas décadas. En este trabajo se aborda un algoritmo de Sistema de Colonia de Hormigas (ACS, por sus siglas en inglés) para resolver el VRPTW (ACS-VRPTW). El ACS se basa en el comportamiento real de las hormigas, las cuales encuentran el camino de su colonia a la fuente de comida mediante el uso de una sustancia química llamada “feromona”. La feromona es utilizada por las hormigas para registrar la información de los caminos recorridos durante la búsqueda de comida; los mejores caminos son favorecidos con mayor cantidad de feromona. De esta forma, el algoritmo ACS-VRPTW hace uso de hormigas artificiales que parten de un almacén central a un conjunto de clientes a visitar, mientras se cumplan con las restricciones de capacidad de vehículos y de ventanas de tiempo. Para mejorar el desempeño del algoritmo ACS-VRPTW propuesto, se diseño una estrategia de caracterización del ambiente que proporciona información adicional a la hormiga en la construcción de rutas. Esta estrategia caracteriza la duración de las ventanas de tiempo de los clientes para modificar la información de la feromona en el ambiente. De esta manera, se busca que la hormiga le sea mas deseable visitar aquellos clientes que tengan una duración corta de ventana de tiempo, para reducir los tiempos de espera que se generarían al no visitarlos. La estrategia de caracterización del ambiente propuesta, muestra que es factible resolver de manera eficiente el VRPTW. El algoritmo ACS-VRPTW propuesto al ser comparado con los algoritmos de la línea de investigación que se sigue, ha obtenido una mejora significativa del 1.4% en la reducción de la cantidad de vehículos utilizados para resolver el VRPTW. |
| metadata.dc.type: | info:eu-repo/semantics/masterThesis |
| Appears in Collections: | Maestría en Ciencias de la Computación |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 346003-JOSE R. CAMARA COVARRUBIAS_donacion_tesis_bib.pdf | 5.67 MB | Adobe PDF | View/Open |
This item is protected by original copyright |
This item is licensed under a Creative Commons License
