A Problem-Specific Branch-and-Bound Algorithm for the Protected Shortest Simple Path Problem with Must-Pass Nodes. Issue 10 (2022)

• Record Type: Journal Article
• Authors: Ogorodnikov, Yuri; Rudakov, Roman; Khachai, Daniil; Khachay, Michael
• Is Part Of: IFAC-PapersOnLine. Volume 55:Issue 10(2022)
• Page Start: 572
• Page End: 577
• Publication Date: 2022
• Subjects: Protected Shortest Simple Path Problem with Must-Pass Nodes -- Branch -- Bound algorithm -- MILP models; Automatic control -- Periodicals; 629.805
• DOI: 10.1016/j.ifacol.2022.09.455
• Languages: English
• ISSNs: 2405-8963

Abstract

Abstract: An instance of the Protected Shortest Simple Path Problem with Must-Pass Nodes (PSSPP-MPN) is specified by an edge-weighted directed graph with dedicated source, destination, and additional must-pass nodes. The goal is to find two vertex-disjoint paths, such that the former one is simple, visits all the must-pass nodes, and has the minimum transportation cost. In this paper, we show that the PSSPP-MPN is strongly NP-hard even for subsets of must-pass nodes of arbitrary fixed size and propose a novel problem-specific branch-and-bound algorithm for this problem. Results of competitive numerical evaluation against the public dataset 'Rome99' from the 9th DIMACS Implementation Challenge show that the proposed algorithm notably outperforms the state-of-the-art MIP-optimizer Gurobi both by accuracy and execution time.