Solving bi-objective time-dependent shorted path problems
Cargando...
Archivos
Fecha
2021
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
Muchos problemas de búsqueda interesantes se pueden formular como ´
problemas de búsqueda bi-objetivos, es decir, problemas de búsqueda en los ´
que dos tipos de costos tienen que ser minimizados, por ejemplo, distancia y
costos para problemas de transporte. Últimamente esta área de investigación ha ´
ido en aumento, introduciendo una extensión, basándose en obtener los caminos ´
mínimos de vehículos con dependencia temporal. Para este estudio, se experimentan
aplicaciones en mapas de Estados Unidos. Para esta experimentación se cuenta con ´
un problema dependiente del tiempo, donde el día es divido en intervalos temporales
discretos proporcionales. Los costos asociados dependerán del intervalo temporal ´
inicial. Por ejemplo, un conjunto de soluciones optimas obtenidas entre dos puntos ´
en un grafo (nodos) A y B a las 12:00hrs puede varias a las obtenidas a las 19:00hrs.
En este trabajo se propone un estudio para el mapa de Estados Unidos proponiendo
la adapcion del algoritmo BOA* para afrontar la extensi ´ on del problema bi-objetivo ´
con dependencia temporal. BOA* ha demostrado su contribucion en tiempo de ´
ejecucion respecto a algoritmos de la literatura tales como NAMOA*, NAMOA*dr, ´
Bi-Objective Dijkstra, y Bidirectional Bi-Objective Dijkstra. Con esto, planteamos
que es posible resolver problemas mas grandes que los reportados y realizar análisis ´
exhaustivos en mapas de Estados Unidos, proponiendo un algoritmo de búsqueda de ´
caminos mínimos basado en el algoritmo BOA*.
Notas
Tesis (Magíster en Ciencias de la Computación)
Palabras clave
Transporte por Carreteras, Procesamiento de Datos, Estados Unidos, Algoritmos Computacionales