Groupe d’études et de recherche en analyse des décisions

G-2018-64

A tabu search for the design of capacitated rooted survivable planar networks

et

Given a directed graph \(G=(V,A)\), capacity and cost functions on \(A\), a root \(r\), a subset \(T \subset V\) of terminals, and an integer \(k\), we aim at selecting a minimum cost subset \(A'\subseteq A\) such that for every subgraph of \(G'=(V,A')\) obtained by removing \(k\) arcs from \(A'\) it is possible to route one unit of flow from \(r\) to each terminal while respecting the capacity constraints. We focus on the case where the input graph \(G\) is planar and propose a tabu search algorithm whose main procedure takes advantage of planar graph duality properties.

, 18 pages