An exact bidirectional pulse algorithm for the constrained shortest path

"Una ruta más corta restringida es una secuencia de arcos de costo mínimo en una red dirigida que satisface las restricciones de tipo knapsack en el consumo de recursos sobre los arcos. Nosotros proponemos un método exacto basado en un procedimiento de búsqueda recursiva en profundidad, conocid...

Full description

Autores:
Cabrera Malik, Nicolás
Tipo de recurso:
Fecha de publicación:
2019
Institución:
Universidad de los Andes
Repositorio:
Séneca: repositorio Uniandes
Idioma:
eng
OAI Identifier:
oai:repositorio.uniandes.edu.co:1992/44083
Acceso en línea:
http://hdl.handle.net/1992/44083
Palabra clave:
Problema de rutas de vehículos - Investigaciones
Análisis de ruta crítica - Investigaciones
Sistemas inteligentes de transporte - Investigaciones
Programación heurística - Investigaciones
Carreteras - Análisis de redes - Investigaciones
Sistemas de grandes dimensiones - Investigaciones
Investigación operacional - Investigaciones
Optimización matemática - Investigaciones
Ingeniería
Rights
openAccess
License
https://repositorio.uniandes.edu.co/static/pdf/aceptacion_uso_es.pdf
Description
Summary:"Una ruta más corta restringida es una secuencia de arcos de costo mínimo en una red dirigida que satisface las restricciones de tipo knapsack en el consumo de recursos sobre los arcos. Nosotros proponemos un método exacto basado en un procedimiento de búsqueda recursiva en profundidad, conocido como el algoritmo del pulso. Una de las novedades clave de la propuesta radica en una estrategia de etiquetado bidireccional soportada en el paralelismo. Además, desarrollamos una heurística basada en el pulso que rápidamente encuentra soluciones casi óptimas y muestra un gran potencial para esquemas de generación de columnas. Nosotros presentamos experimentos computacionales en grandes redes de carreteras con hasta 6 millones de nodos y 15 millones de arcos." -- Tomado del Formato de Documento de Grado.