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

#### 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2021
978-3-030-86840-6
978-3-030-86841-3
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]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11588/867097`
• ND
• 1
• ND