A matheuristic for the Common Capacity Constrained Multi Shortest Path Problem

D. García Heredia, A. Alonso Ayuso, M. Laguna, E. Molina

In this work we propose a matheuristic algorithm to tackle the problem of finding, for each independent network within a collection, the shortest path between two points while respecting common capacity constraints that link all the nets together. These capacity constraints, which commonly represent the usage of limited resources (e.g.: train tracks), restrict the simultaneous use of arcs.

For real applications in which this problem structure arises (e.g.: Air Traffic Flow Management), the size of the problems might rapidly exceed the computational resources when solving them with MIP commercial software. That is why, jointly with the aim of obtaining competent results in short periods of time, that we develop this algorithm. To show its performance, an exhaustive computational experience is presented.

Keywords: Constrained Shortest Path, Matheuristics, Scheduling problems

HEU-1 Heuristics and Metaheuristics
September 6, 2019  3:30 PM
I3L10. Georgina Blanes building

I. Giménez Palacios, F. Parreño Torres, M. T. Alonso Martínez, R. Alvarez-Valdes

D. Rodríguez Penas, A. Gómez, B. B. Fraguela, M. J. Martín, S. Cerviño