Publication:
A solution method for the shared Resource Constrained Multi-Shortest Path Problem

Simple item page
dc.affiliation.dptoUC3M. Departamento de EstadĂ­sticaes
dc.contributor.authorGarcĂ­a Heredia, David
dc.contributor.authorMolina Ferragut, Elisenda
dc.contributor.authorLaguna, Manuel
dc.contributor.authorAlonso Ayuso, Antonio
dc.contributor.editorUniversidad Carlos III de Madrid. Departamento de EstadĂ­sticaes
dc.date.accessioned2020-09-04T17:27:02Z
dc.date.available2020-09-04T17:27:02Z
dc.date.issued2020-09-04
dc.description.abstractWe tackle the problem of finding, for each network within a collection, the shortest path betweentwo given nodes, while not exceeding the limits of a set of shared resources. We present an integer programming (IP) formulation of this problem and propose a parallelizable matheuristic consistingof three phases: 1) generation of feasible solutions, 2) combination of solutions, and 3) solution improvement. We show that the shortest paths found with our procedure correspond to the solution of the Resource-Constrained Multi-Project Scheduling Problem (RCMPSP) and that a particular case of the RCMPSP occurs in Air Traffic Flow Management (ATFM). Our computational results include finding optimal solutions to small and medium-size ATFM instances by applying Gurobi to the IP formulation. We use those solutions to assess the quality of the output produced by our proposed matheuristic. For the largest instances, which correspond to actual flight plans in ATFM, exact methods fail and we assess the quality of our solutions by means of Lagrangian bounds. Computational results suggest that the proposed procedure is an effective approach to the family of shortest path problems that we discuss here.en
dc.identifier.issn2387-0303es
dc.identifier.urihttps://hdl.handle.net/10016/30793
dc.identifier.uxxiDT/0000001807es
dc.language.isoenges
dc.relation.ispartofseriesWorking paper. Statistics and Econometricsen
dc.relation.ispartofseries20-06es
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 España*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/es/*
dc.subject.otherMatheuristicsen
dc.subject.otherShortest Pathen
dc.subject.otherResource-Constrained Multi-Project Scheduling Problemen
dc.subject.otherAir Traffic Flow Managementen
dc.titleA solution method for the shared Resource Constrained Multi-Shortest Path Problemen
dc.typeworking paper*
dspace.entity.typePublication
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ws202006.pdf
Size:
1.75 MB
Format:
Adobe Portable Document Format
Download
Collections
DES - Working Papers. Statistics and Econometrics. WS