We propose a branch and bound (B&B) and a dynamic programming algorithm for the Path Avoiding Forbidden Pairs Problem (PAFPP). Given a network and a set of forbidden node pairs, the problem consists in finding the shortest path from a source node s to a target node t, avoiding to traverse both nodes of any of the forbidden pairs. The problem has been shown to be NP-complete. In this work, we describe the problem, its mathematical model and we propose two exact algorithms. We compare their performances against those of a commercial solver solving instances for two different graph topologies: fully random graphs and grid graphs.
Branch and Bound and Dynamic Programming Approaches for the Path Avoiding Forbidden Pairs Problem / Ferone, D.; Festa, P.; Salani, M.. - 7:(2021), pp. 227-235. [10.1007/978-3-030-86841-3_19]
Branch and Bound and Dynamic Programming Approaches for the Path Avoiding Forbidden Pairs Problem
Ferone D.
;Festa P.;
2021
Abstract
We propose a branch and bound (B&B) and a dynamic programming algorithm for the Path Avoiding Forbidden Pairs Problem (PAFPP). Given a network and a set of forbidden node pairs, the problem consists in finding the shortest path from a source node s to a target node t, avoiding to traverse both nodes of any of the forbidden pairs. The problem has been shown to be NP-complete. In this work, we describe the problem, its mathematical model and we propose two exact algorithms. We compare their performances against those of a commercial solver solving instances for two different graph topologies: fully random graphs and grid graphs.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
