Resumen

Se presenta un algoritmo estocástico para obtener poblaciones iniciales factibles para el Problema de Rutas de Vehículos con Ventanas de Tiempo. Se explica la formulación teórica del problema de rutas de vehículos con ventanas de tiempo. El método propuesto se divide principalmente en un algoritmo de agrupación y un algoritmo de dos fases. El primer paso es la aplicación de un algoritmo de clustering k -means modificado que se propone en este trabajo. El algoritmo de dos fases evalúa una solución parcial para transformarla en un individuo factible. El algoritmo de dos fases consiste en una hibridación de cuatro tipos de inserciones que interactúan aleatoriamente para obtener individuos factibles. Se ha demostrado que los distintos tipos de inserciones influyen en la diversidad entre los individuos de las poblaciones iniciales, lo que es crucial para el comportamiento de los algoritmos basados en poblaciones. Se aplica una modificación del método de la distancia de Hamming a las poblaciones generadas para el Problema de Enrutamiento de Vehículos con Ventanas Temporales para evaluar su diversidad. Se realizaron pruebas experimentales basadas en la evaluación comparativa de Solomon. Los resultados experimentales muestran que el método propuesto facilita la generación de poblaciones muy diversas, que varían en función del tipo y distribución de las instancias.

• Materias:Análisis Matemático Matemáticas Algebra Ingeniería Lógica matemática
• Subjects:Mathematical Analysis mathematics Algebra Engineering Mathematical logic
• Palabras claves:Algoritmo estocástico; poblaciones iniciales; problema de rutas de vehículos con ventanas de tiempo; algoritmo de agrupación; algoritmo bifásico; diversidad.
• Keywords:Stochastic algorithm; initial populations; Vehicle Routing Problem with Time Windows; clustering algorithm; two-phase algorithm; diversity