An exact bidirectional pulse algorithm for the constrained shortest path

Abstract

"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.

"A constrained shortest path is a minimum-cost sequence of arcs on a directed network that satisfies knapsack-type constraints on the resource consumption over the arcs. We propose an exact method based on a recursive depth-first search procedure known as the pulse algorithm. One of the key novelties of the proposal lies in a bidirectional labeling strategy leveraged on parallelism. In addition, we developed a pulse-based heuristic that quickly finds near-optimal solutions and shows great potential for column generation schemes. We present computational experiments over large real-road networks with up to 6 million nodes and 15 million arcs." -- Tomado del Formato de Documento de Grado.