Binary file ./template_functions.inc.php matches
Reducing the complexity of implementing the vehicle routing problem using evolutionary strategies and fuzzy logic - RIIIT
Reducing the complexity of implementing the vehicle routing problem using evolutionary strategies and fuzzy logic
El problema de ruteo de vehículos (VRP) clásico, también llamado problema del agente viajero (TSP) es uno de los casos más estudiados de problemas polinomiales no determinísticos (NP) - completos. Para resolver un problema NP-completo en un escenario del mundo real (problema práctico), es necesario generar una solución inicial seguida de una optimización para reducir el costo en el consumo de recursos. En este trabajo se propone un algoritmo híbrido que combina una estrategia evolutiva (ES) para la generación de rutas que representan la entrada para un sistema difuso (FLS) que posteriormente es optimizado por la misma ES una vez resuelto por el sistema difuso. Esta técnica de optimización heurística resuelve el VRP encontrando la ruta que minimiza los costos como objetivo. La unión de las ES con la lógica difusa reduce la complejidad de un sistema difuso puro ya que sólo necesita la distancia en las conexiones entre los vértices para obtener la solución de una función que define el sistema, en comparación con la combinación factorial utilizada en algunas de las metaheurísticas. Esa propuesta pone a prueba el cómputo suave (SC) y su capacidad para resolver problemas combinatorios con mejor precisión que un enfoque metaheurístico como el recocido simulado (SA) y el problema del camino más corto (SP) o modelo de Dijkstra. Los resultados muestran una precisión mayor al 80% que es habitual en las redes neuronales artificiales (ANN), adicionalmente este enfoque dedica sólo el 10% del tiempo computacional requerido por el SA y el SP para obtener una solución factible.
Palabras clave: Cómputo evolutivo, estrategias evolutivas, lógica difusa tipo 1, modelo híbrido, problema de ruteo de vehículos.
;)
