Journées de l'optimisation 2014

                             Incluant une Journée industrielle de l'optimisation

                                              HEC Montréal, 5 - 7 mai 2014


HEC Montréal, 5 — 7 mai 2014

Horaire Auteurs Mon horaire

MA1 Séance plénière 1 / Plenary Session 1

5 mai 2014 09h00 – 10h00

Salle: Amphithéâtre Banque Nationale

Présidée par Louis-Martin Rousseau

1 présentation

  • 09h00 - 10h00

    The Pulse Algorithm: A Modular Framework for Hard Shortest Path Variants

    • Andrès Medaglia, prés., Universidad de los Andes

    Solving practical applications arising on transportation and logistics often involves the solution of underlying large-scale network problems with shortest path structures. Initially, we proposed the pulse algorithm as an exact method for solving shortest paths with side constraints. Later on, we identified other shortest path variants where the same principle behind the pulse algorithm applied. In this talk, we present the pulse algorithm as a framework based on the idea of performing an implicit enumeration of the entire solution space supported by pruning strategies that efficiently discard a vast number of suboptimal solutions. The framework relies on general components that can be easily extended to different routing problems and problem-specific components that can be used as modules. We show our experience on several shortest path variants such as the constrained shortest path, the biobjective shortest path, the elementary shortest path with resource constraints, the orienteering problem with time windows, and the weight-constrained shortest path with replenishment.