Fast solving multi-objective hazmat shortest path problem : a case study in Santiago of Chile
Cargando...
Archivos
Fecha
2020
Autores
Profesor/a Guía
Facultad/escuela
Idioma
es
Título de la revista
ISSN de la revista
Título del volumen
Editor
Universidad Andrés Bello
Nombre de Curso
Licencia CC
Licencia CC
Resumen
La búsqueda multi-objetivo, es un área de la Inteligencia Artificial que tiene como finalildad obtener un conjunto de caminos óptimos o frontera de Pareto desde un estado origen hacia un estado destino en un grafo. Existen varios algoritmos IA para esto. Los del estado del arte son BOA∗ que resuelve problemas con dos objetivos, NAMOA∗ y NAMOA∗dr, que resuelven
problemas con dos o más objetivos. En esta tesis, se aplican estos algoritmos para resolver el
problema de transporte sustancias peligrosas (HAZMAT) desde un origen a un destino. Este
problema hasta ahora sólo se ha resuelto mediante métodos del área de Investigación de Operaciones sin considerar algoritmos de inteligencia artificial. Nuestros experimentos muestran que
tres algoritmos antes mencionados son más eficientes para obtener la frontera de pareto-óptima
que los métodos de Investigación de Operaciones. En la comparación de los algortimos, utilizando dos objetivos, BOA*
logró mejores resultados que NAMOA∗, debido a que el primer
algoritmo poda los caminos dominados de forma más eficiente (comprobación de dominancia
la realiza en un tiempo constante), en cambio NAMOA∗
la realiza en un tiempo lineal. Para tres
objetivos NAMOA∗dr es mejor debido a su poda que usa reducción de dimensionalidad.
Notas
Tesis (Magíster en Ciencias de la Computación)
Palabras clave
Sustancias Peligrosas, Transporte, Modelos Matemáticos, Inteligencia Artificial