Por favor, use este identificador para citar o enlazar este ítem:
http://cimat.repositorioinstitucional.mx/jspui/handle/1008/1095| Metaheurísticas aplicadas a la Resolución de Problemas de Ruteo de Vehículos con Capacidad | |
| Oscar González | |
| Acceso Abierto | |
| Atribución-NoComercial | |
| COMPUTACIÓN MATEMÁTICAS INDUSTRIALES | |
| En esta tesis, se diseña un nuevo algoritmo evolutivo perteneciente a la familia de los algoritmos memeticos (Memetic Algorithms — MAs) para resolver algunas variantes del Problema del Ruteo de Vehículos. La primera variante que se aborda es el Problema del Ruteo de Vehículos con Capacidad y Ventanas de Tiempos (CVRPTW - Capacitated Vehicle Routing Problem with Time-Windows) en donde introducimos un nuevo operador de cruza que es comparado con el operador de cruza basado en secuencia (Sequence-Based Crossover - SBX) que fue diseñado para el CVRPTW. El operador de cruza propuesto es el operador de cruza de un punto en común de ruptura basado en secuencia (Single Breaking-Point Sequence Based-Crossover - SBSBX) y su principal ventaja es reducir el comportamiento destructivo que el operador SBX presentaba. La reducción del comportamiento destructivo facilita el control de la diversidad a través de la modificación de la presión de selección en la etapa de la selección de padres, de hecho, se muestra que con el operador SBX la diversidad no puede ser controlada mediante la modificación del operador de selección de padres. Sin embargo, este no es el caso con el operador SBSBX propuesto. El MA propuesto usa el recocido simulado (Simulated Annealing - SA) como método de trayectoria para mejorar los individuos generados por el operador de cruza. Se muestra que modificar exclusivamente la etapa de selección de padres no es suficiente para controlar de forma adecuada el balance entre la exploración y la explotación y, por esta razón, algunos de los métodos del estado del arte tienen problemáticas relacionadas con el control de diversidad. Debido a esto, una contribución adicional de esta tesis consistió en incorporar estrategias de control de diversidad más recientes y mostrar que las propuestas contribuyen significativamente al alcance de soluciones de alta calidad. Específicamente, la estrategia de control de diversidad dinámica basada en conceptos multi-objetivo (Replacement with Multi-objective based Dynamic Diversity Control strategy - RMDDC) es utilizada para administrar la diversidad de forma explícita. La propuesta es validada usando las pruebas de desempeño de Solomon con 100 clientes y las pruebas de desempeño de Homberger con 200, 400 y 600 clientes pudiéndose generar nuevas mejores soluciones para 14 instancias. Teniendo en cuenta que estas instancias han sido abordadas mediante una gran cantidad de métodos, se considera que este es un logro importante de | |
| 01-06-2018 | |
| Trabajo de grado, maestría | |
| OTRAS | |
| Versión aceptada | |
| acceptedVersion - Versión aceptada | |
| Aparece en las colecciones: | Tesis del CIMAT |
Cargar archivos:
| Fichero | Descripción | Tamaño | Formato | |
|---|---|---|---|---|
| TE 799.pdf | 1.63 MB | Adobe PDF | Visualizar/Abrir |