A tabu search for the design of capacitated rooted survivable planar networks
- PDF / 460,944 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 17 Downloads / 158 Views
A tabu search for the design of capacitated rooted survivable planar networks Alain Hertz1
· Thomas Ridremont1,2
Received: 12 July 2018 / Revised: 14 July 2020 / Accepted: 20 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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. Keywords Capacitated rooted survivable networks · Planar graphs · Tabu search
1 Introduction The design of efficient networks is crucial in many fields such as transport, telecommunications or energy. In this paper, we focus on the design of networks which are resilient to one or several breakdowns. The main motivation for this work is the design of a survivable wind farm collection network. One of the nodes of the network is the sub-station where the energy produced by the turbines must be transported. By defining each turbine as a terminal, the sub-station as the root, and reversing the direction of each arc, we get a delivery problem of a given quantity of flow from the root to the terminals. For a set A of potential arcs with non-negative costs and positive capacities, and for a given positive integer k, the objective is then to select a minimum cost subset
B
Alain Hertz [email protected]
1
Polytechnique and GERAD, Montréal, Canada
2
ENSTA ParisTech and CEDRIC-CNAM, Paris, France
123
A. Hertz, T. Ridremont Table 1 Main notation T:
Set of terminal vertices in the input graph G = (V , A);
r:
Root vertex in the input graph G = (V , A);
G + t:
Graph obtained from a subgraph G of G by adding a sink t to which all terminals are linked with an arc of capacity 1;
G:
Graph obtained from a subgraph G of G such that G has a feasible flow if and only if G has a feasible circulation; Arcs added to G to obtain G;
AR: ci j : c(A ): ui j : ui j : li j : DG :
Non-negative cost of the arc (i, j) in G; Total cost of the arcs in A ⊆ A; Positive integer capacity of the arc (i, j) in G; Positive integer capacity of the arc (i, j) in G; Integer non-negative imposed flow on the arc (i, j) in G; Extended dual graph of G;
aidj :
Standard dual arc in DG associated with the arc (i, j) in G;
(k + 1)DG :
Graph obtained by making (k + 1) copies of D
Data Loading...
