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

e-Archivo Repository

Show simple item record

dc.contributor.author García Heredia, David
dc.contributor.author Molina Ferragut, Elisenda
dc.contributor.author Laguna, Manuel
dc.contributor.author Alonso Ayuso, Antonio
dc.contributor.editor Universidad Carlos III de Madrid. Departamento de Estadística
dc.date.accessioned 2020-09-04T17:27:02Z
dc.date.available 2020-09-04T17:27:02Z
dc.date.issued 2020-09-04
dc.identifier.issn 2387-0303
dc.identifier.uri http://hdl.handle.net/10016/30793
dc.description.abstract We 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.
dc.language.iso eng
dc.relation.ispartofseries Working paper. Statistics and Econometrics
dc.relation.ispartofseries 20-06
dc.rights Atribución-NoComercial-SinDerivadas 3.0 España
dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.subject.other Matheuristics
dc.subject.other Shortest Path
dc.subject.other Resource-Constrained Multi-Project Scheduling Problem
dc.subject.other Air Traffic Flow Management
dc.title A solution method for the shared Resource Constrained Multi-Shortest Path Problem
dc.type workingPaper
dc.identifier.uxxi DT/0000001807
 Find Full text

Files in this item

*Click on file's image for preview. (Embargoed files's preview is not supported)


The following license files are associated with this item:

This item appears in the following Collection(s)

Show simple item record