Selecting Optimal Multi-species Corridor Networks with Travel-distance, Path-redundancy, and Budget Constraints

Abstract

The fragmentation of natural environments, generally a consequence of human activity, is one of the main threats to biodiversity. The conservation or creation of ecological corridors is essential in an attempt to remedy this fragmentation. We propose a multi-species model to help decision-makers select an optimal network of corridors from a very general potential network, within a budgetary constraint. The selected network must link a given set of biodiversity reservoirs both spatially and biologically. It must therefore be adapted to a given set of species, i.e. it must take account of the fact that certain corridors and reservoirs are more or less suitable for certain species. The quality of the selected network is measured against the quality of the potential network. This network must also take into account the distance certain species have to travel to connect reservoirs, as well as the possibility for certain species to connect reservoirs even when certain corridors have become impassable, thanks to redundant paths. The proposed model is formulated by a mixed-integer mathematical program. A small example illustrates the model and its resolution in detail. Experiments on larger examples using one of the efficient commercial solvers currently available demonstrate the model's practicability.

1 Introduction

1.1 Biological Corridors to Counter Landscape Fragmentation

Landscape fragmentation, mainly due to urbanization, agriculture and forest exploitation, is recognized as a major cause of biodiversity loss (see e.g. [1,2,3,4,5,6,7,8,9]). It prevents species from moving as they should because they would have to cross often inhospitable spaces. These areas may, for example, lack food resources or be home to numerous predators. The ability of species to move smoothly between different habitat areas is critical to their survival. For example, it can increase population sizes, allow species to relocate to certain areas, maintain genetic diversity, provide access to different habitats, and increase food sources. Thus, preserving and/or restoring habitat connectivity has been identified as a key conservation priority by government agencies and conservation organizations [10]. One way of ensuring this connectivity is the establishment of corridors (see e.g. [2, 9, 11,12,13,14,15,16]) and this issue is the theme of this study in which, for the sake of simplicity, a corridor network is made up of two main components called biodiversity reservoirs and corridors. Establishing such a network is a complex process that can be broken down into two phases (see e.g. [17, 18]): identifying a set of potential good-quality corridors linking the reservoirs, then selecting some of these corridors to link the reservoirs as best as possible, taking into account resource constraints. The first phase is crucial. It is based on various approaches such as species distribution modelling, least-cost path analysis, resistance surfaces, circuit theory, expert opinion and optimization techniques (see for example [19,20,21,22,23,24,25]). The second phase is the subject of this article.

1.2 Biodiversity Reservoirs, Biological Corridors and Target Species

The biodiversity reservoirs are territories with a particularly rich biodiversity, not connected to each other, in which certain species find favorable conditions for their development. The corridors are natural spaces – likely to be more or less developed – of different forms and nature linking biodiversity reservoirs. They must themselves be areas favorable to the life of the species concerned, to allow them to feed, rest and protect themselves from their predators during their movements. They are highly dependent on the species of interest. In addition, some authors have also emphasized the value of corridors in the context of climate change, as this will force many species to migrate in order to maintain favorable habitats [26]. The fact that biodiversity reservoirs are linked by a network of corridors may have certain disadvantages (see e.g. [27,28,29]). Indeed, this network facilitates the circulation between reservoirs and is also an entry point to these reservoirs. It can therefore facilitate the spread of diseases, parasites, invasive species and predators from one reservoir to another, but also facilitate their introduction into all the reservoirs. Moreover, the efforts to maintain the effectiveness of a corridor network which is often very extensive consume significant human and financial resources. Many references provide a thorough discussion of corridor design and evaluation, including consideration of the balance between the ecological benefits and economic costs of maintaining or implementing corridors [28]. It should be noted that in the literature on biological conservation, corridors have multiple definitions and functions (see e.g. [2, 9, 11, 30,31,32]). The reader is referred to [32] where an interesting literature review is carried out to better understand the terminology relating to landscape connectivity. The establishment or restoration of biological corridors has generally been considered for a single species. However, given that many species are threatened by landscape fragmentation, it is more effective, from a global biodiversity protection perspective, to meet the needs of as many species as possible (see e.g. [33, 34]). For example, it is shown in [35] that designing corridors for a single species on the basis of purely ecological criteria leads to extremely costly links that are suboptimal for multispecies connectivity objectives. Thus, connectivity modeling for multiple species has recently received increasing interest [22, 25, 35,36,37,38,39,40]. Our study falls within this framework. Of course, a corridor network developed for a set of species may be less effective for a given species than a corridor network developed specifically for that species [37].

1.3 Article Outline

In this study, we are interested in selecting under a budget limit a set of corridors from a set of potential corridors linking different biodiversity reservoirs. The selected network of corridors must meet certain criteria for a set of target species. It should be noted that while the costs of establishing and maintaining a network of corridors are relatively easy to evaluate, the evaluation of the benefits it provides is much more delicate. They are evaluated here, globally for all the species considered, by the following characteristics of the selected network: connectivity in the broad sense, path redundancy (to deal with the partial destruction of corridors), and ecological quality [41].

In what follows, we detail the notions of biodiversity reservoirs, potential corridors, target species and quality of a network of corridors that are relevant to our study. We then define more precisely the problem under consideration − necessarily simplified with respect to reality − and we show how to transform it into a mathematical optimization model. This model is then solved using Gurobi, a state-of-the-art commercial software package for this type of mathematical model.

Several studies have already used mathematical programming to model various aspects of the optimal design of a corridor or corridor network (see, e.g. [17, 24, 42] and references therein). The originality of our approach lies essentially in the simultaneous consideration of the following four aspects: generality of the potential network, consideration of several species and their different behaviors, distances to be covered by the species in the selected network and redundancy of certain paths in this network.

2 Natural Environment

Inspired by the checklist proposed in [30] for evaluating a corridor network we first define the habitat areas the corridor network is designed to connect. In a second step, we select several species of interest among the species present in the reservoirs. In a third step, we identify potential corridors linking pairs of biodiversity reservoirs and we deduce the routes likely to be taken by the different species.

2.1 Biodiversity Reservoirs

Biodiversity reservoirs are natural areas of a single block and of a significant size which present a remarkable biodiversity and in which live heritage species to be protected. These species find there the favorable conditions to carry out all or part of their life cycle (for example, feeding, reproduction, rest, wintering). We assume here that these reservoirs are habitats for many species, some of which are threatened, have some protected status, and will remain reservoirs in the future [30]. We denote ${\text{BR}} = \{ {\text{br}}_{1} ,{\text{br}}_{2} ,...,{\text{br}}_{n} \}$ the set of considered reservoirs. Figure 1 shows six hypothetical biodiversity reservoirs. It is assumed that among the species considered, some find a favorable habitat in certain reservoirs and an unfavorable habitat in other reservoirs. This aspect is detailed in the next section.

Fig. 1

A set of 6 hypothetical biodiversity reservoirs linked by potential corridors

2.2 Species of Interest

Designing a network of corridors for a single species present in these reservoirs may not meet the different ecological requirements of coexisting species (see e.g. [33,34,35, 37]). In addition as highlighted for example in [22] it is more economical to design a corridor network suitable for multiple species than to address multiple species one after another. An important point in the design of a corridor network is therefore that the network be relevant to as many species as possible, hence the need for a multi-species approach (see e.g. [33,34,35, 43]). Of course, it will be more difficult to design a network of corridors that meets the needs of multiple species simultaneously, as each species may prefer a different type of environment for movement. Several recent or relatively recent references concern this aspect [22, 35, 37, 38]. As pointed out in [30] since, in practical terms, only a handful of species can be addressed rigorously it is necessary to select umbrella species [44] whose protection is expected to confer benefits on the greatest number of species and to include species that have the greatest need for a corridor (see e.g. [30] and references therein). We therefore assume here that we have selected a set of species meeting these criteria from among those present in the different biodiversity reservoirs. We denote $S = \{ s_{1} ,s_{2} ,...,s_{m} \}$ the set of considered species and $M = \{ 1,2,...,m\}$ the set of corresponding indices. We distinguish three types of reservoirs. Some reservoirs constitute a favorable habitat for certain species. For example, a woodland-type reservoir will be more or less suitable for different species, depending on the type and age of the trees, the shape and size of the reservoir, the management practiced, etc. [45]. It could be that all reservoirs are suitable for one or more species. Some reservoirs do not provide suitable habitat for some species, but it is assumed that these species may still pass through these reservoirs during their movement. Finally, some reservoirs may be hostile to certain species and we assume that the movements of these species in the corridor network are undesirable through these reservoirs. For example, certain urban or agricultural environments are hostile to many species, but some of them, particularly commensals, thrive in this environment. This is the case for certain rodents and birds, which find all the resources they need [46]. In Fig. 1, four species s₁, s₂, s₃, and s₄ are concerned, reservoirs br₂, br₄, br₅, and br₆ are favorable to species s₂, reservoir br₁ is not hostile to this species and reservoir br₃ is hostile to it.

2.3 Potential Corridors

Some pairs of reservoirs are connected by potential corridors and others are not. In fact, we are interested in all kinds of structures likely to be used by species − after possible development − to link reservoirs. To simplify the presentation, we call these structures potential corridors. A potential corridor linking two reservoirs is made up of one or more segments. If it consists of several segments, it passes through one or more intersection (or intermediate) points. We denote $I = \{ I_{1} ,I_{2} ,...,I_{p} \}$ the set of intersection points. A segment thus connects two reservoirs or a reservoir and an intersection point or two intersection points. Any two potential corridors may have one or more segments in common. Several potential corridors may connect the same two reservoirs and these corridors may or may not have common segments. Several parallel segments may connect the same two points on the landscape. This possible structure of the network of potential corridors is of interest in the context of a multi-species study, since, as explained below, the various segments may be suitable for some species but unsuitable for others. Regardless of the multi-species aspect, a certain amount of redundancy between segments can help maintain a functional network when, for various reasons, one of the segments becomes unusable (see Section 3.5). When $\beta$ segments ($\beta > 1$) connect the same two points p₁ and p₂ of the set ${\text{BR}} \cup I$, we designate these segments by [p₁,p₂]¹, [p₁,p₂]²,…,[p₁,p₂]^β. Each segment has a cost. It may represent land purchase costs, maintenance costs (depending in part on its length), ecological costs or social costs. The overall cost of a corridor network is equal to the sum of the costs of the segments that make up the network. As pointed out for example in [12, 39, 47], the potential corridor cannot be separated from the species under consideration. Thus, for various reasons, some of the segments may be considered inadequate for the movement of certain species even after some restoration [25]. Some segments may have obstacles such as roads, rivers or fences that are impassable for some species. Some segments may not have enough shelter and food to allow some species to use them for a sufficiently long time. All kinds of human activities can also prevent certain species from using certain potential corridors [48]. Of course, a corridor can be used by a given species only if all its segments can be used by that species. See, for example, [30] for an assessment of the suitability of each potential corridor to support movement of the species of interest. For example, Fig. 1 shows that there are 3 different corridors connecting reservoirs br₄ and br₅. The first one is formed by the only segment [br₄, br₅], the second one by segments [br₄,I₁], [I₁,I₂]¹ and [I₂,br₅], and the third one by segments [br₄,I₁], [I₁,I₂]², and [I₂,br₅]. The first corridor cannot be used by species s₄ and the last two corridors share the 2 sections [br₄,I₁] and [I₂,br₅].

3 Problem Description

The problem is to determine an optimal corridor network made up of potential corridors only, and satisfying both spatial properties (existence of links between two reservoirs, distances between reservoirs and redundancy of some paths) and biological properties (corridors and reservoirs suitable for some species but not others, corridor quality according to species). The way in which the network is assessed and its expected properties are described in detail below.

3.1 Objective

The goal is to obtain the best network of corridors that meets certain criteria. But measuring the quality of a corridor network is a challenge in reality, especially since what constitutes a good quality corridor is likely to vary according to the species [41, 49, 50]. Indeed, the sensitivity of a species to its habitat can largely determine the perceived quality of the corridor [50], and a corridor that is not of good quality for a given species may be rarely used by that species [41]. The quality of each segment may depend on its width, length and habitat type, the presence or absence of shelters, hiding places, food, obstacles that are more or less easy to overcome, predators, nearby dwellings, etc. In short determining the quality of a corridor network is a complex task requiring long and careful observation of species movements.

We associate to each potential segment a quality depending on the species considered. The quality of the selected network is equal, for each species to the sum of the qualities of the segments selected to form this network, provided they constitute a section of the corridors that can be used by this species to link directly (i.e. without passing through other reservoirs) two reservoirs whose habitat is favorable to it. We look for a network of corridors that maximizes, for each species, the ratio between the quality of the selected network and the quality of the network that could be selected in the absence of budget constraints. This ratio we call quality score ranges from 0 to 1. In other words, we aim to build a network of corridors using the most ecologically interesting potential segments for each species. Since several species are considered simultaneously, it is impossible to obtain a maximum quality score for each species. We have therefore chosen the weighted sum of the quality score of each species as the economic function to maximize. In a classical way, the weights allow to give more or less importance to the different species. We denote w_k the weight associated with species s_k. For example, let us calculate the quality score of the solution shown in Fig. 3 for species s₂ when the quality of each segment that can be used by this species is equal to 1. The quality of the selected network is equal to 6 and the quality of the network that could be selected in the absence of budget constraints is equal to 12 (see Section 6 for detailed calculations). The quality score is therefore equal to 0.5.

3.2 Budget

The cost of the corridor network is equal to the sum of the costs of each segment composing the whole network. This cost must be less than the available budget, B. Of course, if the same segment belongs to more than one selected corridor, it is only counted once. Many models presented in the literature seek to minimize certain aspects of the cost associated with defining a corridor network. Here, we consider a budget limit that likely improves the relevance of the model for conservation planners, who generally operate in an environment with limited budgets [51]. The solution in Fig. 3 costs 25 units. Note that there is no feasible solution with a cost lower than 25 given the various criteria that the network must meet.

3.3 Network Functionality

The selected network must allow each of the considered species to move, from reservoir to reservoir, through all the reservoirs that are suitable for it, using only corridors where all the segments can be used by it and not passing through reservoirs that are hostile to it. Figure 3 shows a feasible solution. For example, species s₃ can move through reservoirs br₁, br₃, br₄, br₅, and br₆ without passing through reservoir br₂ and without using segment [br₃,I₂]¹.

3.4 Travel Distances

The network must respect constraints concerning the distances (or number of segments) that species must cover to move between the different reservoirs, taking into account the selected corridors [52, 53]. The smaller these distances, the easier it is for species to move within these reservoirs. This aspect, which is to some extent linked to network density, can be taken into account in several ways. The first requirement that can be taken into account in our model is that, for a given set of species, the reservoirs favorable to these species must not be too far apart. To this end, we require that, for each species s_k of the set, there must be a vertex called center (depending of k), such that the number of segments (usable by the species s_k) to be covered in the network to reach each all the reservoirs favorable to s_k from the center is less than or equal to a certain value. This value is called the radius of the network for the species s_k and is noted r_k. The center vertex is either a biodiversity reservoir or an intersection point.

We also allow for the possibility of introducing constraints on the distance certain species must travel to connect some pair of reservoirs. Thus, for some species, these distances − or number of segments − must be less than or equal to a specified value.

For example, the radius corresponding to the solution in Fig. 3, for species s₂, is equal to 3 and the center is the intersection point I₁. It can be checked on this figure that from the intersection point I₁ the species s₂ can reach the reservoirs br₂, br₄, br₅, and br₆ by going through at most 3 segments. This figure also shows a solution that ensures species s₁ can connect reservoir br₁ to reservoir br₅ through at most 3 segments, the segments [br₁,I₁], [I₁, I₂]¹, and [I₂,br₅].

A third way to control the distances to be travelled in the selected network could be to seek a compromise solution between network quality and the total number of segments − or total segment length − making up the network. One way of doing this would be to optimize an economic function including the two above-mentioned criteria with a certain weighting (see Section 5.5).

3.5 Path Redundancy

It may be of interest that the selected corridor network has some redundancy in that several of the selected corridors may allow the same species to move between two given reservoirs using a corridor or a succession of corridors. This can happen if the budget is not too limited or if different species can use common corridors. This redundancy is interesting in that it can reduce the impact of corridor loss. For example, we see in Fig. 3 that species s₃ can use to connect the two reservoirs br₁ and br₅ either the corridor formed by segments [br₁,I₁], [I₁,I₂]¹ and [I₂,br₅] or a succession of two corridors. The first one connects br₁ to br₃ and is formed by the segments [br₁,I₁], [I₁,I₂]¹ and [I₂,br₃]², the second one connects br₃ to br₅ and is formed by the segment [br₃,br₅] only. We introduce into our model the possibility of imposing even greater redundancy by requiring the selected corridor network to comprise two completely disjoint routes − using different segments − for given pairs of reservoirs and species. Thus, the unavailability of all or part of one route will not prevent the movement of certain species between certain reservoirs. This network property can be interesting to consider for example for a threatened species living in a small number of reservoirs. Thus we can impose, for certain indices k, b and e, that there are two different routes that can be taken by species s_k to connect reservoirs br_b and br_e. For example, in the solution shown in Fig. 3 the species s₃ can connect reservoir br₃ to reservoir br₆ by two disjoint routes. The first route is formed by segments [br₃,br₅], and [br₅,br₆]¹ and the second by segments [br₃,I₂]², [I₂,br₅], and [br₅,br₆]².

4 Graph Formulation

We associate the potential corridor network with the directed graph, $G = \left( {X,A} \right)$. The set of vertices, X, is formed by associating to each element of the set constituted by the reservoirs and the intersection points, ${\text{BR}} \cup I$, a vertex of this graph. We pose X = {1,2,…,N}. The vertices corresponding to the biodiversity reservoirs, ${\text{br}}_{1} ,{\text{br}}_{2} ,...,{\text{br}}_{n}$, are numbered from 1 to n and the vertices corresponding to the intersection points, $I_{1} ,I_{2} ,...,I_{p}$, are numbered from n+1 to N = n+p. The set of arcs A is constructed by associating to each potential corridor segment connecting two points of ${\text{BR}} \cup I$ two symmetrical arcs (i,j) and (j,i) where i and j are the two vertices associated with the two points of ${\text{BR}} \cup I$. Note that G is a multigraph since several corridor segments can connect two same points. If a single arc goes from vertex i to vertex j it is noted (i,j), if β arcs (β  > 1) go from i to j they are noted $(i,j)^{1}$,$(i,j)^{2}$,…,$(i,j)^{\beta }$. For example, in Fig. 1, two segments connect the intersection points I₁ and I₂ and two other segments connect the reservoirs br₅ and br₆. Figure 2 shows the graph associated with the hypothetical potential corridor network in Fig. 1. This figure also shows the cost associated with each segment. As a consequence of what we have seen in the previous paragraphs, we distinguish for each species different subsets of X and A.

Fig. 2

Graph associated with the potential corridor network of Fig. 1. Each edge connecting two vertices i and j (belonging to {1,…,10}) represents an arc from i to j and an arc from j to i. The cost associated with each corridor segment is indicated on the associated edge. For example, the cost of the segment connecting vertex 1 (which represents the reservoir br₁) to vertex 7 (which represents the intersection point I₁) is equal to 2

Notation:

• $V = \{ 1,...,n\}$: set of vertices associated with biodiversity reservoirs. 

• $Z = \{ n + 1,...,n + p\}$: set of vertices associated with intersection (or intermediate) points. 

• $V_{k} \subseteq V\;(k \in M)$: set of vertices associated with reservoirs suitable for the species s_k. 

• $\hat{V}_{k} \subseteq V\;(k \in M)$: set of vertices associated with reservoirs not hostile to the species s_k.

• $\overline{V}_{k} \subseteq V\;(k \in M)$: set of vertices associated with reservoirs hostile to the species s_k. 

• $A_{k} \subseteq A\;(k \in M)$: set of arcs associated with segments that can be used by species s_k. Note that arcs whose initial or terminal end belongs to $\overline{V}_{k}$ are not part of A_k.

• $\vec{A} \subset A$: set of arcs formed by the only arcs of A connecting two vertices i and j such that i < j. 

• $\vec{A}_{k} \subset A_{k} \;(k \in M)$: set of arcs formed by the only arcs of A connecting two vertices i and j such that i < j and associated with segments that can be used by species s_k. 

• $\underline{{\vec{A}}}_{k} \subseteq \vec{A}_{k} \;(k \in M)$: set of arcs associated with segments forming a potential corridor that can be used by the species s_k to link 2 reservoirs that are favorable to it. 

Given these notations, the problem consists of selecting an optimal subgraph of G that verifies the following property: for all $k \in M$ and for any pair of vertices {i,j}, i < j, belonging to $V_{k}$ this subgraph admits a path from i to j using only arcs of A_k and not passing through any vertices of $\overline{V}_{k}$. It is assumed that the graph G verifies this property.

5 Mixed Integer Programming (MIP) Formulation

In this section, we formulate the model as a mixed integer program, based on the graph associated with the problem and defined in the previous section. The economic function is linear, as are all the constraints, with the exception of those concerning network radii (Section 3.4), which are quadratic. An optimization problem that can be formulated directly by a mathematical program using only linear expressions is generally easier to solve than a problem requiring quadratic expressions.

5.1 Data and Notation

U: set of corridors. Each corridor is considered only once, from one of its ends, i, to its other end j with i < j. If a single corridor connects vertices i and j, it is denoted [i,j]; if γ corridors (γ> 1) connect i and j, they are denoted $[i,j]^{1}$,…,$[i,j]^{\gamma }$.

$U_{k} \;(k \in M)$: set of corridors that can be used by the species s_k.

$c_{a} \;(a \in \vec{A})$: cost of the arc a; it is equal to the cost of the segment associated with it.

$q_{k,a} \;(k \in M,a \in \vec{A}_{k} )$: quality of the segment associated with the arc a for the species s_k.

$Q_{k} \;(k \in M)$: quality of the selected network for the species s_k (see Section 3.1).

$\overline{Q}_{k} \;(k \in M)$: quality of the potential network for the species s_k ($= \sum\nolimits_{{a \in \underline{{\vec{A}}}_{k} }} {q_{k,a} }$).

$Q_{k} /\overline{Q}_{k} \;(k \in M)$: quality score for the species s_k.

${\text{Sec}} (u)\;(u \in U)$: set of arcs included in $\vec{A}$ and corresponding to the segments that constitute the corridor u.

5.2 Variables

$X_{a}$ $(a \in A)$: Boolean variable equal to 1 if and only if the arc a is selected. Recall that two symmetric arcs are associated with each corridor segment.

$\alpha_{k,a}$ $(k \in M,a \in \underline{{\vec{A}}}_{k} )$: Boolean variable equal to 1 if and only if at least one corridor that can be used by species s_k and contains the arc a is selected.

$y_{u}$ $(u \in U)$: Boolean variable equal to 1 if and only if the corridor u is selected.

$\varphi_{k,a}$ $(k \in M,a \in A_{k} )$: positive or zero variable representing the flow on the arc a and used to model the network functionality.

$t_{k,i,h}$ $(k \in M,i \in V,h \in \{ 0,...,r_{k} \} )$: Boolean variable that is equal to 1 if and only if the value h is assigned to vertex i for species s_k; it is used to model the upper limit of the radius imposed on the network for species s_k.

$\psi_{k,a}$ $(k \in M,a \in A_{k} )$: Boolean variable representing the flow on the arc a and used to model the limit on the maximum number of segments to travel to connect two given reservoirs.

$\mu_{k,a}$ $(k \in M,a \in A_{k} )$: Boolean variable representing the flow on the arc a and used to model the path redundancy criteria.

5.3 Economic Function and Budget Limit

The objective to be maximized given the available budget is described by the mathematical program

$$\pi\!\!:\left\{\begin{array}{l}max\;f={\sum }_{k\in M}{w}_{k}({\sum }_{a\in {\underline{\overrightarrow{A}}}_{k}}{q}_{k,a}{\alpha }_{k,a}/{\sum }_{a\in {\underline{\overrightarrow{A}}}_{k}}{q}_{k,a})\\ {\text{s}}.{\text{t}}.\left|\begin{array}{lll}{\alpha }_{k,a}\le {\sum }_{u\in {U}_{k}:a\in \text{Sec}(u)}{y}_{u}& k\in M,a\in {\underline{\overrightarrow{A}}}_{k}& (1)\\ {y}_{u}{\le x}_{a}& u\in U,a\in \text{Sec}(u)& (2)\\ {\sum }_{a\in \overrightarrow{A}}{c}_{a}{x}_{a}\le B& & (3)\end{array}\right.\end{array}\right.$$

The expressions $\sum\nolimits_{{a \in \underline{{\vec{A}}}_{k} }} {q_{k,a} \,\alpha_{k,a} }$ and $\sum\nolimits_{{a \in \underline{{\vec{A}}}_{k} }} {q_{k,a} }$ represents the quantities $Q_{k}$ and $\overline{Q}_{k}$ defined previously, respectively. The economic function f thus represents the weighted sum over all species of the quantities $Q_{k} /\overline{Q}_{k}$. Because of constraints (1) and the function f to be maximized, the Boolean variable $\alpha_{k,a}$ takes the value 1 if and only if at least one of the corridors that can be used by $s_{k}$ and that includes the segment associated with arc a is selected. According to constraints (2), if a corridor u is selected (y_u = 1), then all the segments making up this corridor must be selected. Note that, for each species s_k, the working variables α_k,a must be used in addition to the x_a variables associated with the segments that can be used by species s_k, in order to avoid selecting in the optimal solution a segment that would improve the economic function but which could not be used by species s_k to link two vertices of V_k (as it does not belong to a selected corridor linking two reservoirs of V_k). According to constraint (3) the sum of the costs of all selected segments must be equal to or less than the available budget B. Note that a simple modification of the economic function allows us to select, from all the solutions that maximize this function, the one with the lowest cost. To do this, we simply subtract from f the cost of the solution affected by a sufficiently small coefficient ε, i.e. the expression $\varepsilon \sum\nolimits_{{a \in \vec{A}}} {\,c_{a} x_{a} }$.

In expressing our objective the quality of a segment varies according to the species likely to use it, but we make the assumption that this quality is the same for all the corridors comprising this segment and likely to be used by this species, which may be restrictive. Indeed, the interest of a segment in the course of a corridor may depend on the characteristics of other segments of the same corridor. One way of overcoming this restriction is to assign a quality to each segment, depending on both the species and the corridor. We note $q_{k,a,u} \;(k \in M,a \in \underline{{\vec{A}}}_{k} ,u \in U_{k} )$ this quality for species s_k, the segment associated with arc a and corridor u. For species s_k, the quality of the selected (or potential) network is then equal to the sum, over all the corridors of the selected (or potential) network that can be used by s_k, of the quality of the segments making up these corridors. With this modification, the economic function becomes $\sum\nolimits_{k \in M} {w_{k} [(\sum\nolimits_{{u \in U_{k} \,}} {y_{u} \sum\nolimits_{{a \in {\text{Sec}} (u)}} {q_{k,a,u} } )/(\sum\nolimits_{{u \in U_{k} \,}} {\sum\nolimits_{{a \in {\text{Sec}} (u)}} {q_{k,a,u} )]} } } }$ under constraints (2) and (3).

5.4 Network Functionality

In order to allow the various species to move into the reservoirs that are favorable to them, the selected subgraph of G must verify the following property: for all $k \in M$, this subgraph admits a connected subgraph whose set of vertices includes all the vertices of V_k and possibly some vertices of $\hat{V}_{k} \cup \{ n + 1,...,N\}$ and whose edges belong to A_k. This problem (for a given species) is known as the Steiner tree problem [54,55,56,57]. Several mixed-integer linear programming formulations have been formulated for this problem. We retain here a relatively simple formulation, based on the notion of flow in a graph [9, 58,59,60,61] and given by

$$\mathrm F\!\!:\left\{\begin{array}{lll}{\sum }_{a\in {\Omega }_{k}^{+}(i)}{\varphi }_{k,a}-{\sum }_{a\in {\Omega }_{k}^{-}(i)}{\varphi }_{k,a}=-1& k\in M,i\in {V}_{k},i\ne {i}_{k,0}& (4)\\ {\sum }_{a\in {\Omega }_{k}^{+}(i)}{\varphi }_{k,a}-{\sum }_{a\in {\Omega }_{k}^{-}(i)}{\varphi }_{k,a}=0& k\in M,i\in {\widehat{V}}_{k}\cup {\text{Z}}& (5)\\ {\varphi }_{k,a}\le (n-1){x}_{a}& k\in M,a\in {A}_{k}& (6)\\ {x}_{a}={x}_{\widetilde{a}}& a\in \overrightarrow{A}& (7)\end{array}\right.$$

For each vertex i of V and for each species s_k of S, $\Omega_{k}^{ + } (i)$ (resp. $\Omega_{k}^{ - } (i)$) denotes the set of arcs of A whose initial (resp. terminal) end is i and which can be used by s_k. According to constraints (4), for each species s_k and each vertex of V_k (mandatory vertex in the searched subgraph), except vertex i_k,0, the sum of the flows arriving on this vertex by arcs suitable for s_k minus the sum of the flows leaving from this vertex on arcs suitable for s_k must be equal to -1. Vertex i_k,0 is any vertex of V_k. According to constraints (5), for each species s_k and each vertex of $\hat{V}_{k} \cup Z$ (authorized crossing points), the sum of the flows arriving on this vertex by arcs suitable for s_k minus the sum of the flows leaving from this vertex by arcs suitable for s_k must be equal to 0. Constraints (6) express the fact that if the flow $\varphi_{k,a}$ is positive then the arc a is retained. Constraints (7) force the equality of the two variables $x_{a}$ and $x_{{\tilde{a}}}$ corresponding to the two symmetrical arcs, a and $\tilde{a}$ associated to the same segment. The arcs $a \in \vec{A}$ such that x_a = 1 and their extremities form the searched connected subgraph.

5.5 Travel Distances in the Network

For some species $s_{k} \in S$, the first requirement defined in Section 3.4 (radii that must not exceed certain values for some species) is reflected in the set of following constraints:

$$\mathrm{Rad}({s_k})\!\!: \left\{\begin{array}{lll}{\sum }_{i\in {V}_{k}\cup {\widehat{V}}_{k}\cup Z}{t}_{k,i,0}=1& & (8)\\ {\sum }_{h\in {H}_{k}}{t}_{k,i,h}=1& i\in {V}_{k}& (9)\\ {t}_{k,i,h}\le {\sum }_{a\in {\Omega }_{k}^{-}(i)}\,{x}_{a}{t}_{k,{\text{init}}(a),h-1}& i\in {V}_{k}\cup {\widehat{V}}_{k}\cup Z,h\in {H}_{k},h\ge 1 & (10)\end{array}\right.$$

We obtain a family of constraints by considering different values of k, possibly all. Constraint (8) expresses that, for the species $s_{k}$, one and only one of the vertices of $V_{k} \cup \hat{V}_{k} \cup Z$ must be chosen as center (value or level 0 assigned to this vertex). Constraints (9) express that, for the species s_k, one and only one value (belonging to H_k = {0,1,…,r_k}) must be assigned to each vertex of $V_{k}$. Constraints (10) express that the Boolean variable t_k,i,h can take the value 1 if and only if an arc $a \in A_{k}$ whose terminal extremity is i and whose initial extremity (init(a)) has the value h-1 has been selected. In other words, the value h can only be assigned to vertex i if the value h-1 is assigned to one of its predecessors, j, (j,i) being an arc that can be used by s_k. Similar constraints, based on a recursive definition of some variables, are used in [62] for finding, in a graph, a clique with the minimum distance to the outside nodes and in [63] for determining a spanning tree with a given height but here constraints (10) are quadratic since they involve the product of the Boolean variables x and t. If the mathematical program solver at our disposal is unable to handle this type of constraint, there are simple and classic linearizations of the product of two Boolean variables, but at the cost of a substantial increase in the number of variables and constraints. One way to linearize the product of two Boolean variables v₁ and v₂ is to replace the product v₁v₂ by the variable v₁₂ and add the following four constraints to force the variable v₁₂ to be equal to the product v₁v₂: $v_{12} \le v_{1} ,v_{12} \le v_{2} ,1 - v{}_{1} - v_{2} + v_{12} \ge 0,v_{12} \ge 0$. Thus, if we want to use a linear formulation of these constraints on the radii of the network, we replace constraints (10) by the set of following constraints:

$$(10')\!\!: \left\{\begin{array}{l}{t}_{k,i,h}\le {\sum }_{a\in {\Omega }_{k}^{-}(i)}{\lambda }_{a,k,h-1} \qquad\qquad i\in {V}_{k}\cup {\widehat{V}}_{k}\cup {\text{Z}},h\in {H}_{k},h\ge 1\\ \left.\begin{array}{ll}{\lambda }_{a,k,h-1}\le {t}_{k,{\text{init}}(a),h-1}& \\ {\lambda }_{a,k,h-1}\le {x}_{a}& \\ 1-{t}_{k,{\text{init}}(a),h-1}-{x}_{a}+{\lambda }_{a,k,h-1}\ge 0& \\ {\lambda }_{a,k,h-1}\ge 0& \end{array}\right\}a\in {A}_{k},h\in {H}_{k},h\ge 1\end{array}\right.$$

where the variable $\lambda_{a,k,h - 1}$ represents the product $x_{a} t_{{k,{\text{init}}(a),h - 1}}.$

The second requirement defined in Section 3.4 concerns certain species and pairs of reservoirs. Remember that it imposes the existence, in the selected subgraph, of a path suitable for species s_k connecting both vertices b and e of $V_{k}$ and comprising a number of arcs less than or equal to a given value L. For a given quadruplet (s_k,br_b,br_e,L), this requirement is reflected in the set of following constraints:

$$\mathrm {Dist}\left({\mathrm{s}_k},\mathrm{b}\mathrm{r}_b,\mathrm{b}\mathrm{r}_e,{L}\right)\!\!:\;\left\{\begin{array}{lll}{\sum }_{a\in {\Omega }_{k}^{+}(b)}{\psi }_{k,a}=1& & (11)\\ {\sum }_{a\in {\Omega }_{k}^{-}(b)}{\psi }_{k,a}=0& & (12)\\ {\sum }_{a\in {\Omega }_{k}^{-}(e)}{\psi }_{k,a}=1& & (13)\\ {\sum }_{a\in {\Omega }_{k}^{-}(i)}{\psi }_{k,a}={\sum }_{a\in {\Omega }_{k}^{+}(i)}{\psi }_{k,a}& i\in V,i\ne b,i\ne e & (14)\\ {\sum }_{a\in {A}_{k}}{\psi }_{k,a}\le L& & (15)\\ {\psi }_{k,a}\le {x}_{a}& a\in {A}_{k}& (16)\end{array}\right.$$

We obtain a family of constraints by considering different quadruplets. Constraint (11) imposes that a flow of value 1 circulates on one and only one of the arcs of A_k whose initial extremity is b. Constraint (12) imposes that no flow circulates on the arcs of A_k whose terminal extremity is b. Constraint (13) imposes that a flow of value 1 circulates on one and only one of the arcs of A_k whose terminal end is e. Constraints (14) impose the conservation of the flow at each vertex different from b and e on the arcs of A_k. Constraint (15) expresses that the number of arcs of A_k to be traversed by the species s_k to connect b to e must be less than or equal to L. Constraints (16) force to retain the arc a (x_a = 1) if the flow on the arc a is equal to 1 ($\psi_{k,a} = 1$). Note that it is easy to replace the limit on the number of arcs, L, by a limit on the total path length between b and e.

As discussed in Section 3.4, it is possible to control the distances to be covered in the selected network by considering two weighted criteria in the economic function, network quality on the one hand and total length on the other. The economic function to be maximized then becomes $f^{\prime} = \theta_{1} f - \theta_{2} \sum\nolimits_{{a \in \vec{A}}} {l_{a} x_{a} }$ where $\theta_{1}$ and $\theta_{2}$ are the weighting coefficients (positive or zero) of the criteria and where l_a designates the length of segment a.

5.6 Path Redundancy in the Network

This property also concerns certain species and certain pairs of reservoirs. Remember that the path redundancy requirement defined in Section 3.5 imposes the existence, in the selected subgraph, of two paths that can be used by species s_k, disjoint in the sense of arcs and connecting both vertices, b and e, of V_k. We also impose that the total number of arcs making up the two routes must be less than or equal to a given value L. Note that if this limit on the number of arcs is not appropriate, it suffices to give L a sufficiently large value. The search for disjoint paths connecting two given vertices of a graph is a classic application of flow theory (see e.g. [64]). Formulate this problem using linear programming in Boolean variables: for a given quadruplet (s_k,br_b,br_e,L), the path redundancy requirement is reflected by the set of following constraints:

$$\mathrm {Re} (s_k, \mathrm{br}_b,\mathrm{br}_e,L)\!\!:\left\{\begin{array}{lll}{\sum }_{a\in {\Omega}_{k}^{+}(b)}{\mu }_{k,a}=2& & (17)\\ {\sum }_{a\in {\Omega }_{k}^{-}(b)}{\mu }_{k,a}=0& & (18)\\ {\sum }_{a\in {\Omega }_{k}^{-}(e)}{\mu}_{k,a}=2& & (19)\\ {\sum }_{a\in {\Omega }_{k}^{-}(i)}{\mu }_{k,a}={\sum }_{a\in {\Omega }_{k}^{+}(i)}{\mu }_{k,a}& i\in V,i\ne b,i\ne e & (20)\\ {\sum }_{a\in {A}_{k}}{\mu }_{k,a}\le L& & (21)\\ {\mu }_{k,a}\le {x}_{a}& a\in {A}_{k}& (22)\end{array}\right.$$

We obtain a family of constraints by considering different quadruplets. Constraint (17) imposes that a flow of value 1 circulates on exactly two arcs of A_k starting from b. Constraint (18) imposes that no flow circulates on the arcs of A_k arriving on b. Constraint (19) imposes that a flow of value 1 circulates on exactly two arcs of A_k arriving on e. Constraints (20) impose the conservation of the flow at each vertex of V different from b and e for the arcs of A_k. Constraint (21) expresses that the total number of arcs of A_k to be traversed by the species s_k to connect b to e by two distinct paths must be less than or equal to L. Constraints (22) force to retain the arc a (x_a = 1) if the flow on the arc a is equal to 1 ($\mu_{k,a} = 1$).

5.7 Summary of the Mathematical Program for the Problem

In summary, the following mathematical program is associated with the considered problem:

$$(\mathrm P)\!\!:\left\{\begin{array}{ll} max\,f\\ {\text{s}}.{\text{t}}.\left|\begin{array}{ll} (1)-(7)& \\ {\text{Rad}}\left({s}_{k}\right)& k\in {K}_{1}\\ {\text{Dist}}\left({s}_{k},\mathrm{br}_b,\mathrm{br}_e,L\right)& (k,b,e,L)\in D\\ {\text{Re}}\left({s}_{k},\mathrm{br}_b,\mathrm{br}_e,L\right)& (k,b,e,L)\in R\\ {x}_{a}\in \{0,1\}& a\in A\\ {\alpha }_{k,a}\in \{0,1\}& k\in M,a\in {\underline{\overrightarrow{A}}}_{k}\\ {\psi }_{k,a},{\mu }_{k,a}\in \{0,1\},{\varphi }_{k,a}\ge 0& k\in M,a\in {A}_{k}\\ {y}_{u}\in \{0,1\}& u\in U\\ {t}_{k,i,h}\in \{0,1\}& k\in M,i\in V,h\in \{0,...,{r}_{k}\}\end{array}\right.\end{array}\right.$$

where K₁ is a given subset of M, and both D and R are given sets of quadruplets included in $M \times V \times V \times {\mathbb{N}}$ (${\mathbb{N}}$ is the set of positive integers). In the quadruplets $(k,b,e,L)$ of D and R, $b \in V_{k}$ and $e \in V_{k}$.

6 Illustrative Example

We consider the hypothetical potential network of corridors presented in Fig. 1. It links 6 biodiversity reservoirs and 4 species are considered. The habitat of some of the reservoirs is unfavorable to some species. There are 19 corridor segments in the network, but some of these segments cannot be used by certain species.

Figure 2 shows the graph – drawn with Graph Online software (https://graphonline.ru/fr) – associated with the considered network with the cost of each segment. In order to facilitate both the reading of the problem and the interpretation of the solutions, we consider that for any species s_k the ecological qualities of all the segments (that can be used by species s_k) are equal to 1. In this case, the economic function measures the ratio of the number of segments that the species s_k can use in the proposed solution to the number of segments that this species could have used if the entire potential network had been selected. An optimal solution, i.e. an optimal selection of corridors satisfying a set of constraints, detailed in the legend to Fig. 3, was obtained in a few seconds by solving the program (P) with the mathematical programming solver Gurobi [65]. All the experiments presented in this article were carried out using the ampl language (version 2022-10-13) [66] to model the program (P) and Gurobi (version 10.0.1), a solver based on the most efficient algorithms available today, to solve it. The experiments have been performed on a PC with an Intel Core i7 1.90 GHz processor with 16 Go RAM. Figure 3 presents this optimal solution. The cost is equal to 25. The centers for species s₁, s₂, s₃, and s₄ are points br₁, I₁, I₁, and br₁, respectively. The two disjoint routes with no more than 5 segments in total that allow species s₃ to connect br₃ and br₆ are formed, on the one hand, by segments [br₃,br₅], [br₅,br₆]¹ and, on the other hand, by segments [br₃,I₂]², [I₂,br₅], [br₅,br₆]². The route with at most 3 segments allowing species s₁ to connect br₁ to br₅ is formed by segments [br₁,I₁], [I₁,I₂]¹, [I₂,br₅]. The route with at most 3 segments allowing species s₃ to connect br₃ to br₆ is formed by segments [br₃,br₅] [br₅,br₆]¹.

Fig. 3

An optimal corridor network selected from the potential network in Fig. 1, when the weight assigned to each species is equal to 1, when the available budget is equal to 25 and when the following characteristics must be respected: the radius imposed for species s₁, s₂, s₃, and s₄ are equal to 4, 3, 3, and 4 respectively, species s₃ must have two disjointed routes with a maximum of 5 segments in total to link br₃ and br₆, species s₁ must have a route with at most 3 segments to connect br₁ and br₅, and species s₃ must have a route with at most 3 segments to connect br₃ and br₆

Let us calculate as an example the part of the economic function corresponding to the species s₂, i.e. $Q_{2} /\overline{Q}_{2}$. In the potential network, all segments except [br₁,br₃], [br₁,I₁], [br₁,I₃], [br₃,I₂]¹, [br₃,I₂]², [br₃,br₅], and [br₅,br₆] can be used by species s₂ to connect two reservoirs whose habitat is favorable to it, i.e. 12 segments. Among the segments retained in the proposed solution, only segments [br₂,I₄], [br₄,I₄], [br₅,br₆]², [br₄,I₁], [I₁,I₂], and [br₅,I₂] can be used by species s₂ to connect two reservoirs whose habitat is favorable to it. The quantity $Q_{2} /\overline{Q}_{2}$ is thus equal to 6/12 = 0.5. By calculating $Q_{k} /\overline{Q}_{k}$ for all other values of k we obtain an overall value of the economic function equal to 2.20.

We observed that introducing a second criterion corresponding to the number of selected segments (see Sections 3.4 and 5.5) did not alter the optimal solution for this (highly constrained) instance, even if we put a lot of emphasis on this second criterion. We then considered exactly the same instance, but increased the budget from 25 to 30 units. The solution obtained with the single quality criterion is that shown in Fig. 3, to which we add the 3 segments [br₁,I₃], [br₂,I₃], [I₃,I₄] and remove the segment [br₂,I₄]. It costs 30 units. The solution obtained with both criteria, giving three times more importance to the first criterion ($\theta_{1} = 3,\theta_{2} = 1$, see Section 5.5), is exactly the one shown in Fig. 3, and therefore costs 25 units. In this case, we can see that taking both criteria into account leads to not using the entire budget, so as not to select segments that could be considered useless in a certain sense.

7 Experiments on Large-sized Instances

We have formulated an optimization problem related to the selection of a network of biological corridors by a mixed integer mathematical program in which all constraints are linear except for one family of constraints which are quadratic. These constraints are easy to linearize if the available solver cannot handle them (see constraint (10’) in Section 5.5). As we can see the linear formulation makes the program somewhat heavier, since it requires many additional variables and constraints. On the other hand, we found that the formulation (quadratic or linear) has little influence on the computation times required to solve (P). This is illustrated on the second instance of this section, which we solved using both formulations.

We also tested this program on a small network with 10 vertices and 19 arcs. In this case the solution is obtained instantaneously using an efficient commercial solver like Gurobi. But, as it is well known to optimization specialists, it is not because one succeeds in formulating an optimization problem by a mathematical program, even if it is a mixed integer linear program, that one is sure to be able to solve this problem. Indeed, a combinatorial explosion can prevent from obtaining the solution in a reasonable time. We therefore tested the program (P) on a hypothetical network with 50 vertices (40 biodiversity reservoirs plus 10 intersection crossing points) and 81 segments, resulting in 100 different corridors connecting pairs of biodiversity reservoirs. In the first instance, we consider that 10 species are concerned. The graph associated with this network and the costs for each segment are shown in the Appendix (Fig. 4). The description of this first instance (biodiversity reservoirs and corridor segments suitable or unsuitable for different specie) and the various criteria to be met (radii, distances separating certain pairs of reservoirs and redundancy of certain paths) are summarized in Table 1. The available budget is equal to 245 (60% of total potential network costs) and for any k of M, the weight, w_k is equal to 1. The optimal solution to this problem (presented in Fig. 4) is obtained in just a few seconds whatever the formulation used (linear or quadratic) to express the values imposed on the radii. We have also tested the resolution of the program (P) on a second instance: the network of potential corridors is that shown in Fig. 4, the number of species involved is equal to 20, a maximum radius is imposed for each species (equal to 8 for the first ten and 10 for the next ten) and all reservoirs offer favorable habitat for all 20 species. In addition, certain species cannot use certain segments of potential corridors, and certain distance and path redundancy constraints must be respected. This information is summarized in Appendix, Table 2. In order to test the model in its entirety, we introduced in this second instance the ecological quality of each potential segment by arbitrarily assigning these segments and for each species a score between 1 and 4. We tested the resolution of (P), as well as the resolution of the linearization of (P) obtained by replacing constraints (10) with constraints (10'), for different values of the available budget. Noting C as the sum of the costs of each potential segment, we considered budget values equal to $\rho \,C$ for different values of ρ between 0.5 and 0.9. The computation times required to solve either the quadratic or the linear formulation of the problem are shown in Table 3 in the Appendix. Not surprisingly, resolution is very fast when the budget is far from sufficient to obtain a solution, or when, on the contrary, it is more than sufficient. Intermediate cases require considerably more computing time. This is true for both formulations. Note that, at least under our experimental conditions, the quadratic formulation is slightly more efficient than the linear one.

8 Discussion

Given the recognized importance of biological corridors in combating landscape fragmentation, the problem of identifying potential corridors suitable for a given species has been widely studied. The same cannot be said for the problem of selecting an optimal network of corridors from a potential network, the subject of this article. To the best of our knowledge, publications concerning this problem consider a relatively simple potential network (e.g. a set of pairs of patches linked by a corridor) and the properties that the selected network must verify are essentially connectivity properties, independent of species except possibly through the definition of potential corridors. The objective is generally cost minimization.

One of the major originalities of this study is that the potential network considered is very general, both in terms of its structure (it admits parallel sections and intersections between sections) and its functionality with regard to all the species considered (the properties of biodiversity reservoirs and sections can be species-dependent). This potential network is therefore likely to well represent a concrete potential network.

The connectivity of a corridor network, i.e. the ability of a given species to link a set of patches (or biodiversity reservoirs), is often considered in biological conservation literature. The connectivity of the network is then equivalent to the connectivity of the associated graph. The simultaneous consideration of several species complicates matters. The originality of our study lies in the fact that although only one network is selected, it must satisfy connectivity properties specific to each species considered. This means taking into account the fact that certain sections of corridors and certain reservoirs are not suitable for certain species. The same applies to limits on the distances that species must cover to access all the reservoirs that are favorable to them. This constraint on distances may differ from one species to another. In the same vein, our model also allows for more precise distance constraints: the minimum distance between two reservoirs must be less than or equal to a given value. This notion of path length and its modeling by mathematical programming is not new to graph theory. The advantage here is that it can be easily integrated into the model.

A certain amount of redundancy in the network is interesting for reducing the impact of corridor loss. Redundancy means that a species can use different corridors to link two reservoirs. This property translates into the existence of disjoint paths between two given vertices of a graph, which is a classic application of flow theory. It is then not difficult to formulate this problem using linear programming in Boolean variables and integrate it into the general model. The interest here lies in its transposition to the corridor selection problem, which to our knowledge has not been done.

Many studies in the literature seek to select minimum-cost corridors respecting certain properties. In this article, we have chosen to select a maximum-value corridor network within a budget constraint, which we feel is more likely to help conservation planners make decisions. However, measuring the value of a corridor network designed for the movement of several species is a difficult task. We propose a new measure of this value: for each species the value of the selected network is equal to the ratio between the quality of the selected network and the quality of the network that could be selected in the absence of budget constraints. Here, the quality of a network is equal to the sum of the species-dependent qualities of its component parts.

To the best of our knowledge, this is the first time that a method has been proposed for selecting an optimal network of corridors, simultaneously integrating all the aspects mentioned above and thus enabling a situation close to reality to be described. As a general rule, the more global the optimization problem, the more difficult it is. So it is often necessary to decompose the problem into successive sub-problems, but the final solution obtained is then sub-optimal. Experiments have shown that the efficiency of currently available mathematical programming solvers - linear or quadratic - allows a very general problem of selecting multi-species corridor networks to be solved. It should be noted that the use of such solvers (like Gurobi) coupled with a modeling language (like ampl) makes computer implementation much easier than the implementation of a specific algorithm.

9 Perspective

In our approach, a potential corridor is either selected or not, and a cost is associated with this selection. A more nuanced strategy might be to consider the possibility of investing more or less resources in potential corridors to improve their quality. Of course, what constitutes an improvement may vary from one species to another. As suggested in [41], these improvements may include, for example increased three-dimensional structure for species which require cover to avoid predation, places to safely rest for species which cannot pass through the entire length of a corridor in a single dispersal event, the presence of food for species which disperse very slowly. Tree planting and the installation of wildlife crossings − adapted to the widest possible range of species − on transport infrastructures are other examples of corridor enhancement. In an extension of our model, the decisions for each potential corridor segment would then be twofold: 1) either the segment is retained or not, and 2) if the segment is retained, a certain level of investment is made. A cost depending on the level of investment would be associated with case 2). For example, it could be envisaged that the ecological quality of a segment for a given species would depend on the level of investment in that segment, and that a species would only be able to use a segment if the quality of that segment for the species in question is greater than or equal to a certain threshold value [41]. We could envisage that different levels of development, with an associated cost, are also possible in biodiversity reservoirs. In the model we have considered, there are 3 possible habitat statuses in a reservoir for a given species: favorable, non-hostile and hostile. In an extension of the model, the status of a reservoir could evolve according to the investments made in it. It could also be envisaged that the selection of corridors and their eventual development be spread over several years, which would raise the question of optimal planning. Finally, it would be interesting to try and take into account in the model the uncertainty that inevitably affects certain parameters [67,68,69].

Appendix

Fig. 4

Graph associated with an hypothetic potential corridor network. Each edge (in bold or not) connecting two vertices i and j (belonging to {1,…,50}) is associated with a corridor segment and represents an arc from i to j and an arc from j to i. The cost associated with each corridor segment is indicated on the associated edge. Edges in bold correspond to an optimal solution for the first instance described in Section 7 and Table 1

Table 1 Description and required criteria for the first instance considered in Section 7 (associated with the network of potential corridors shown in Fig. 4)

Table 2 Description and required criteria for the second instance considered in Section 7 (associated with the network of potential corridors shown in Fig. 4)

Table 3 Resolution by the quadratic formulation and by the linear formulation of the second instance presented in Section 7 and Table 2 (associated with the network of potential corridors shown in Fig. 4)