A solution method for the shared resource-constrained multi-shortest path problem. (15th November 2021)

• Record Type: Journal Article
• Authors: García-Heredia, David; Molina, Elisenda; Laguna, Manuel; Alonso-Ayuso, Antonio
• Is Part Of: Expert systems with applications. Volume 182(2021)
• Publication Date: 2021-11-15
• Subjects: Matheuristics -- Shortest Path Problem -- Shortest Path with Constrained Resources -- Air Traffic Flow Management; 00-01 -- 99-00; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2021.115193
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: Definition of the Shared Resource-Constrained Multi-Shortest Path Problem, SRMSPP. A parallelizable matheuristic to solve the SRMSPP. Instances with thousands of networks and millions of arcs are solved. The SRMSPP can be applied to some Scheduling Problems. Abstract: We tackle the problem of finding, for each network within a collection, the shortest path between two 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 consisting of 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 some type of scheduling problems such as the Air Traffic Flow Management (ATFM) problem. 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.