We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A tabu search for the design of capacitated rooted survivable planar networks.
- Authors
Hertz, Alain; Ridremont, Thomas
- Abstract
Consider a rooted directed graph G with a subset of vertices called terminals, where each arc has a positive integer capacity and a non-negative cost. For a given positive integer k, we say that G is k-survivable if every of its subgraphs obtained by removing at most k arcs admits a feasible flow that routes one unit of flow from the root to every terminal. We aim at determining a k-survivable subgraph of G of minimum total cost. 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. In particular, we prove that it is possible to test the k-survivability of a planar graph by solving a series of shortest path problems. Experiments indicate that the proposed tabu search algorithm produces optimal solutions in a very short computing time, when these are known.
- Subjects
TABU search algorithm; PLANAR graphs; TABOO; DIRECTED graphs
- Publication
Journal of Heuristics, 2020, Vol 26, Issue 6, p829
- ISSN
1381-1231
- Publication type
Article
- DOI
10.1007/s10732-020-09453-x