1 Introduction

Two objective functions are frequently used in location models. The first, called a median objective, minimizes the total access cost of the users to facilities. The second, called a covering objective, minimizes the number of facilities needed to serve all users within a covering radiusr of a facility, or maximizes the number of users covered by a fixed number of facilities. The first of the two problems is called the full covering problem, while the second is called the maximal covering problem. These two objectives have given rise to several variants depending on whether the number of facilities is given or is a decision variable, in which case fixed operating costs are often introduced. Several models also contain capacitated facilities, but we will not consider this extension. For recent surveys on median objectives, we refer the reader to Daskin and Maass (2015) and to Fernández and Landete (2015); covering location problems have been surveyed by Kolen and Tamir (1990) and García and Marín (2015).

When the spatial distribution of the users is more or less uniform, the median and covering objective functions tend to yield sensible and similar solutions. However, there exist several contexts where the users are not uniformly distributed. For example, population density tends to decrease when moving away from city centers to the suburbs, and in many cases there exist isolated pockets of users. In such contexts, the solution of a median problem may be overly influenced by excentric users located too far from a facility. On the other hand, a full covering solution may result in locating too many facilities in outlying areas, while a maximal covering solution will leave excentric users uncovered.

An interesting study exemplifying these issues in a humanitarian setting was conducted by Rancourt et al. (2015). It concerned the distribution of food to rural populations in Kenya. The food was first shipped to a depot (called the main warehouse) and thence to intermediate facilities (called distribution centers) to which the users would walk to receive their food rations. Since the food is packed in heavy bags (close to 25 kg), the users often rent a donkey to carry it on the way home. Most of the users could be served within a reasonable walking distance from a potential facility site, but some would have to walk up to 55 km. The authors of the study solved a median location problem without considering the users living more than r km from a potential site and generated several solutions by letting r vary between five and 55. In effect they actually solved a covering-median problem. It is important to observe that even if some users were not included in the solution of the covering-median problem, they nevertheless had access to a facility at the cost of walking more than r km. In that study, when r was equal to 25, \(3.62\%\) of the users lived beyond that range.

The scientific contribution of this paper is to introduce an alternative methodology to deal with the situation just described. It involves selecting some cooperative users who can act as intermediate facilities which can more easily be reached by the excentric users. More specifically, in the Kenya example, a cooperative user will walk back and forth to a facility in order to collect his food and that of other users that he will later serve. Users living far from an open facility have the option of walking to a facility or to a cooperative user located closer to them. At the second distribution level, a median or coverage objective can be used. In fact, considering that such a cooperative system operates at two levels, four variants can be considered by a planner: (1) cooperative median-median (CMM), (2) cooperative covering-covering (CCC), (3) cooperative median-covering (CMC) and (4) cooperative covering-median (CCM).

In all these variants, the goal is to decide where to locate facilities and cooperative users in such a way that the total cost is minimized and some constraints are satisfied. In the CMM problem, the total cost is the installation cost of the facilities and of the cooperative users, plus the total access cost of the users to facilities and of the non-cooperative users to cooperative users. The constraints are that all users must be connected to a facility or to a cooperative user, and all cooperative users are connected to a facility. In the CCC problem, the total cost is the installation cost of the facilities and of the cooperative users. The constraints are that all cooperative users are within the covering radius of the facilities, and all non-cooperative users are within the covering radius of a facility or of a cooperative user. In the CMC problem, the objective is the installation cost of the facilities and of the cooperative users, plus the access cost of the users to the facilities. The constraints state that all cooperative users must be connected to facilities and all non-cooperative users are either connected to a facility or lie within the covering radius of a cooperative user. In the CCM problem, the objective is the installation cost of the facilities and of the cooperative users, plus the access cost of the non-cooperative users to cooperative users. The constraints are that all cooperative users must lie within the covering radius of a facility, and all non-cooperative users are either connected to a non-cooperative users or lie within the covering radius of a facility. Figure 1a–h illustrates all variants. In Fig. 1, the square node represents a depot, empty stars represent closed facilities, full stars are open facilities, small circles represent non-cooperative users, and medium circles are cooperative users. Figure 1a shows the network common to all cases and Fig. 1b, c depicts solutions when median or coverage objective are considered, respectively. Figure 1d shows a covering-median solution where users are served both if they are within the covering radius of a facility or if they pay the access cost to a facility. Finally, Fig. 1e–h illustrates solutions for the four considered variants when a cooperative system operates at two levels.

Fig. 1
figure 1

Locations of the depot, of the potential facilities and of the users

Full size image

To our knowledge, this paper is the first to formally introduce user cooperation in a location context, although cooperation among already located facilities is common in the public sector (e.g., Walker et al. 1979; Hagtvedt et al. 2009) and in the private sector (e.g., Mercer and Tao 1996; Paterson et al. 2011; Fiestras-Janeiro et al. 2015). Problems possessing a similar structure, but no cooperation in an strict sense, also exist in some two-level commercial applications (e.g., Aardal et al. 1996; Marín and Pelegrín 1999; Marín 2007; Cuda et al. 2015; Gendron et al. 2016, 2017). Note that in most two-level problems end-users are exclusively served by facilities located at the second level whereas we allow them to be served at either level, and we also handle a covering objective. An example arises in firms that produce photo albums. Here, the users send their photos electronically to a company which then offers the users to receive their album by direct home delivery or to collect it from a designated store in their neighbourhood. In such a context, the store acts as a cooperative user. The location structure used in the example is median-covering since direct delivery costs are incurred by the firm at the first level but the user access costs to the stores are not considered. At the second level, the firm only ensures that all end-users can access a store within a reasonable radius. Another application of cooperative users arises in crowd-shipping where individuals accept to perform deliveries for a fee from a distribution center to the homes of on-line shoppers (Archetti et al. 2016; Buldeo et al. 2017; Savelsbergh and Van Woensel 2016). In our models, cooperative users act in a location-allocation context as crowd-shippers do in delivery routing problems. In both cases, the goal is reduce the total cost by modifying the role of the users, and the cooperative users may be compensated for their service.

In this paper, since products can be transshipped between facilities and cooperative users, between cooperative users and non-cooperative users, and also between facilities and non-cooperative users, our model corresponds to a multi-echelon network. We refer the reader to Gendron and Semet (2009) for a review of different formulations for multi-echelon problems, and to Ortiz-Astorquiza et al. (2018) for a recent comprehensive review on multi-level facility location problems as well as for a recent literature review of multi-echelon facility location and routing problems.

The remainder of this paper is organized as follows. In Sect. 2, we model the various cases depicted in Fig. 1. In Sect. 3, we discuss the value of user cooperation. This will be followed in Sect. 4 by an extensive numerical analysis showing the difference between the solutions produced by the various models and illustrating the benefit of user cooperation in a location context. Conclusions follow in Sect. 5.

2 Mathematical models

The first two location problems depicted in Fig. 1b, c are the classical median and covering problem which are well known. The covering-median problem shown in Fig. 1d has been modeled by Rancourt et al. (2015). Here, we provide models for the four cooperation problems of Fig. 1e–h, all of which are NP-hard. We will first present the models in Sects. 2.1–2.4, followed by valid inequalities in Sect. 2.5.

We use the following notation in the models of this section. Denote by I,  J and \(K\subseteq J\) the set of potential location facilities, the set of users and the set of potential cooperative users, respectively. Note that not all users can always act as potential cooperative users either because they do not wish to do so or they are not deemed to be sufficiently reliable. The cost parameters are as follows: \(g_i\) is the cost of operating a facility; \(h_k\) is the price set by user k to act as a cooperative user; \(c_{ji}\) is the positive allocation cost of \(j\in J\) to \(i\in I\cup K.\) As usual, all costs are assumed to be borne by the planner and relate to the same planning horizon. Also note that \(g_i\) includes the travel cost from the depot (not explicitly used in the models) to the potential facility i. Alternatively, if there is no depot, then \(g_i\) is the cost of building a service facility at site i. Although depots are more commonly related to routing problems than to location problems, we consider that it is relevant to consider them in our models. The demand of user j is denoted by \(d_j.\) Let the binary parameters \(a_{ji}\) and \(b_{jk}\) be equal to one if and only if user j is located within a distance r of potential facility i and user j is located within a distance s of potential cooperative user k,  respectively. The variables are as follows: The variable \(x_{ji}\) is equal to one if and only if user j is allocated to potential facility i;  \(y_i\) is equal to one if and only if a facility is opened at site i;  \(w_{jk}\) is equal to one if and only if user j is allocated to potential cooperative user k;  \(z_k\) is equal to one if and only if user k is selected as a cooperative user.

The models of Sects. 2.1–2.4 can be adapted to situations in which facilities or cooperative users are subject to capacity constraints, and also to situations in which their capacities are limited by those of their facilities.

2.1 The cooperative median-median (CMM) model

The cooperative median-median (CMM) model is as follows:

$$\begin{aligned}&\displaystyle \hbox {(CMM)} \hbox { minimize} \sum _{i\in I}g_iy_i+ \sum _{k\in K}h_kz_k +\sum _{j\in J}\sum _{i\in I}d_jc_{ji}x_{ji}+ \sum _{j\in J}\sum _{k\in K}d_jc_{jk}w_{jk} \qquad \end{aligned}$$
(1)
$$\begin{aligned}&\displaystyle {\text {subject to}} \, \sum _{i\in I}x_{ji}+\sum _{k\in K}w_{jk}=1 \quad j\in J\end{aligned}$$
(2)
$$\begin{aligned}&\displaystyle x_{ji}\le y_i \quad i\in I,j\in J\end{aligned}$$
(3)
$$\begin{aligned}&\displaystyle w_{jk}\le z_k \quad j\in J,k\in K\end{aligned}$$
(4)
$$\begin{aligned}&\displaystyle \sum _{i\in I}x_{ki}\ge z_k \quad k\in K\end{aligned}$$
(5)
$$\begin{aligned}&\displaystyle y_i,z_k,x_{ji}, w_{jk}\in \{ 0,1\} \quad i\in I,j\in J,k\in K. \end{aligned}$$
(6)

In this model, the objective function minimizes the sum of the facility opening costs, of the cooperative user selection costs and of the allocation costs. Constraints (2) state that a user j must either be allocated to a facility or to a cooperative user. Constraints (3) and (4) restrict the allocation of users to open facilities and to selected cooperative users, respectively. Constraints (5) ensure that cooperative users are allocated to open facilities. Constraints (6) define the domains of the variables. Note that the \(x_{ji}\) and \(w_{jk}\) variables could be declared as continuous in the interval [0, 1].

Note that the price \(h_k\) includes the transportation costs of all the units of product that cooperative user k transships from his assigned facility to his location for other customers. The problem described in Rancourt et al. (2015) fits with this definition of price since the cooperative users set their price equal to that of hiring a donkey. In general, each customer k could charge a different price \(h_k\) for his service. Although \(h_k\) is known before the assignments are determined, its value may not depend on them. On the other hand, it may happen that a potential cooperative user will know in advance who are the non-cooperative users who will interact with him, which is the case when the facilities are located far from the customers. In any case, if the number of assignments is uncertain, cooperative users can always set an upper bound on \(h_k.\)

2.2 The cooperative covering-covering (CCC) model

The cooperative covering-covering (CCC) model is as follows:

$$\begin{aligned}&\hbox {(CCC)} \quad \hbox {minimize}\quad \sum _{i\in I}g_iy_i+ \sum _{k\in K}h_kz_k \nonumber \\&\quad \text {subject to} \quad \sum _{i\in I}a_{ji}y_{i}+\sum _{k\in K}b_{jk}z_k\ge 1 \qquad j\in J \end{aligned}$$
(7)
$$\begin{aligned}&\sum _{i\in I}a_{ki}y_{i}\ge z_k \quad k\in K\nonumber \\&\quad y_i,z_k\in \{ 0,1\} \quad i\in I,k\in K. \end{aligned}$$
(8)

In this model, there is no allocation cost since we only consider covering objectives. Constraints (7) state that user j must be covered within a radius r by at least one open facility or within a radius s by at least one selected cooperative user. Constraints (8) ensure that cooperative users are covered within a radius r by at least one open facility.

2.3 The cooperative median-covering (CMC) model

The cooperative median-covering (CMC) model is as follows:

$$\begin{aligned}&\hbox {(CMC) minimize}\quad \sum _{i\in I}g_iy_i+ \sum _{k\in K}h_kz_k +\sum _{j\in J}\sum _{i\in I}d_jc_{ji}x_{ji}\nonumber \\&\quad \text {subject to}\quad \sum _{i\in I}x_{ji}+\sum _{k\in K}b_{jk}z_k\ge 1 \quad j\in J\nonumber \\&\quad x_{ji}\le y_i \quad i\in I,j\in J\nonumber \\&\quad \sum _{i\in I}x_{ki}\ge z_k \quad k\in K\nonumber \\&\quad y_i,z_k,x_{ji}\in \{ 0,1\} \quad i\in I,j\in J,k\in K. \end{aligned}$$
(9)

In this model, constraints (9) state that a user j must either be allocated to an open facility or be covered within a radius s by at least one selected cooperative user. Note that it would be suboptimal to allocate a user to more than one facility.

2.4 The cooperative covering-median (CCM) model

The cooperative covering-median (CCM) model is as follows:

$$\begin{aligned}&\hbox {(CCM) minimize} \sum _{i\in I}g_iy_i+ \sum _{k\in K}h_kz_k +\sum _{j\in J}\sum _{k\in K}d_jc_{jk}w_{jk} \nonumber \\&\quad \text {subject to} \, \sum _{i\in I}a_{ji}y_i+\sum _{k\in K}w_{jk}\ge 1 \quad j\in J\nonumber \\&\quad w_{jk}\le z_k \quad j\in J, k\in K\nonumber \\&\quad \sum _{i\in I}a_{ki}y_{i}\ge z_k \quad k\in K\nonumber \\&\quad y_i,z_k, w_{jk}\in \{ 0,1\} \quad i\in I,j\in J,k\in K. \end{aligned}$$
(10)

In this model, constraints (10) state that a user must be covered within a radius r by at least one open facility or one selected cooperative user. It is suboptimal to allocate a user to two selected cooperative users.

2.5 Valid inequalities and fixed variables

From constraints (5), the cooperative users must be allocated to an open facility. Then, from constraints (2) and (4) it follows that

$$\begin{aligned} w_{kk}=0\quad k\in K. \end{aligned}$$
(11)

Valid inequalities can be used to strengthen the CMM, CMC and CCM models.

Proposition 1

Let \(R=\{ i_1,\ldots ,i_e\}\) be an ordered subset of K. If \(e\ge 4\) is even, then

$$\begin{aligned} w_{i_ei_1}+\sum _{t=1}^{e-1}w_{i_ti_{t+1}} +\sum _{t=1}^{e/2}w_{i_{2t}i_{2t-1}}\le e/2 \end{aligned}$$
(12)

is a valid inequality for CMM. If \(e\ge 3\) is odd, then

$$\begin{aligned} w_{i_ei_1}+\sum _{t=1}^{e-1}w_{i_ti_{t+1}}\le (e-1)/2 \end{aligned}$$
(13)

is a valid inequality for CMM.

Proof

In the following, t must be interpreted as \(t\mod e.\) Let e be an even number. Then, the left-hand side of (12) can be rearranged as:

$$\begin{aligned}&w_{i_ei_1}+\sum _{t=1}^{e-1}w_{i_ti_{t+1}}+\sum _{t=1}^{e/2}w_{i_{2t}i_{2t-1}}\nonumber \\&\quad =(w_{i_1i_2}+w_{i_2i_3}+w_{i_2i_1})+(w_{i_3i_4}+w_{i_4i_5}+w_{i_4i_3})+\cdots \nonumber \\&\qquad +(w_{i_{e-1}i_e}+w_{i_ei_1}+w_{i_ei_{e-1}}). \end{aligned}$$
(14)

In the right-hand side of (14), the sum of the three terms in each of the parentheses can never exceed 1. Therefore, the left-hand side of (12) is the sum of e / 2 sums, each of which is at most 1.

Let e be an odd number. If all terms of the left-hand side are zero, then the inequality holds trivially. If \(w_{i_ti_{t+1}}\) is equal to 1 for a certain \(t\in \{ 1,\ldots ,e-1\},\) then as above \(w_{i_{t-1}i_{t}}+w_{i_ti_{t+1}}+w_{i_{t+1}i_{t+2}}\le 1\) and the remaining \(e-3\) terms of the left-hand side of (13) can be rearranged into \((e-3)/2\) sums of the type \(w_{i_{\ell }i_{\ell +1}}+w_{i_{\ell +1}i_{\ell +2}}\) which never exceed 1. Therefore, the left-hand side of (13) never exceeds \(1+(e-3)/2=(e-1)/2.\)\(\square \)

Remark 1

Constraints (2), (4) and (5) imply

$$\begin{aligned} w_{tj}+\sum _{k\in K}w_{jk}\le 1j\in J,t\in K \end{aligned}$$
(15)

which are set packing constraints. Let \(\mathcal {P}\) be the polyhedron defined by (15). The inequalities (13) are odd-hole inequalities of \(\mathcal {P}.\) The separation of odd-hole inequalities can be performed exactly by solving a shortest path problem (Grötschel et al. 1988). The first step is to build a bipartite graph such that one group of nodes is the set of w-variables, the second group of nodes are copies of the first nodes and an edge in the bipartite graph exists if and only if a node in the first set shares a constraint with a node in the second set. The weight of an edge in the bipartite graph is equal to one, minus the sum of fractional values of the variables associated with the end-nodes of the edge. The separation problem reduces to the problem of determining a shortest path between every node and its copy in this bipartite graph.

Proposition 2

Consider a user \(j\in J\) and let \(t_1,\ldots t_{|I\cup K|}\) be the elements of \(I\cup K\) ranked in non-increasing order of allocation costs with respect to j,  i.e., \(c_{jt_1}\ge \cdots \ge c_{jt_{|I\cup K|}}.\) Now consider \(t_p\in I\cup K\) with \(p\ge 2.\) Define \(T_p=\{ t_1,\ldots ,t_{p-1}\}.\) Then, the inequalities

$$\begin{aligned}&\displaystyle y_{t_p}+\sum _{i\in I\cap T_p}x_{ji}+\sum _{k\in K\cap T_p}w_{jk}\le 1\quad \hbox {if }t_p\in I \end{aligned}$$
(16)
$$\begin{aligned}&\displaystyle z_{t_p}+\sum _{i\in I\cap T_p}x_{ji}+\sum _{k\in K\cap T_p}w_{jk}\le 1+z_j\hbox {if }t_p\in K \end{aligned}$$
(17)

are valid for optimal CMM solutions.

Proof

Constraints (16) are valid for optimal CMM solutions since if \(y_{t_p}=1,\) then j cannot be allocated to a facility having a larger allocation cost. If \(y_{t_p}=0,\) then the inequality will not be violated because of (2). The validity of constraints (17) is proved in a similar fashion when user j does not act as a cooperative user. If user j acts as a cooperative user, constraints (17) trivially hold. \(\square \)

Similarly, the following two propositions can be stated without proof.

Proposition 3

Consider a user \(j\in J\) and let \(i_1,\ldots i_{|I|}\) be the elements of I ranked in non-increasing order of allocation costs with respect to j,  i.e., \(c_{ji_1}\ge \cdots \ge c_{ji_{|I|}}.\) Then, if \(|I|\ge 2,\) the inequalities

$$\begin{aligned} y_{i_p}+\sum _{q=1}^{p-1}x_{ji_q}\le 1p=2,\ldots ,|I| \end{aligned}$$
(18)

are valid for optimal CMC solutions.

Note that the inequalities (18) are also valid for the classical p-median and for the single plant location problems. Also observe that García et al. (2011) also derived a p-median formulation based on distance ranking, albeit in a different way.

Proposition 4

Consider a user \(j\in J\) and let \(k_1,\ldots ,k_{|K|}\) be the elements of K ranked in non-increasing order of allocation costs with respect to j,  i.e., \(c_{jk_1}\ge \cdots \ge c_{jk_{|K|}}.\) Then, if \(|K|\ge 2,\) the inequalities

$$\begin{aligned} z_{k_p}+\sum _{q=1}^{p-1}w_{jk_q}\le 1\quad p=2,\ldots ,|K| \end{aligned}$$
(19)

are valid for optimal CCM solutions.

The valid inequalities (16)–(19) generalize the closest assignment constraints of Wagner and Falkson (1975) to our models. The adequacy of these inequalities for discrete location models has been studied in Espejo et al. (2012).

Fig. 2
figure 2

Benefit of cooperation

Full size image

3 The price of cooperation

The four models of Sect. 2 all assume that the cooperation price \(h_k\) is given as an input by the potential cooperative user k. We now investigate what a fair value of \(h_k\) should be for user k and for the planner. To illustrate, consider the network depicted in Fig. 2a. The circles represent users with demand equal to 1, and the stars represent potential facility locations. All the distances are Euclidean. If the fixed cost of opening a facility is 5.5, then the optimal solution of the simple plant location problem consists of opening both facilities as indicated in Fig. 2b (full stars represent open facilities) and the total cost is \(2\times 5.5+10+2\sqrt{5}=25.47.\) The solution that only opens the facility on the left has a larger cost \(5.5+12+2\sqrt{17}=25.74.\) If cooperation is allowed and all the users are potential cooperative users, i.e., K is the set of the six circles, and the cost of having a cooperative user is zero, then the allocation is the one depicted in Fig. 2c (the two users shown by large circles are cooperative users) which has cost equal to 17.97 (\(=13.5+2\sqrt{5}\)) in the CMM model. Therefore, a fair value for cooperation, both for the planner and for the set of potential cooperative users, is \(7.5 =25.47-17.97,\) which is also the total saving realized by the non-cooperative users and an upper bound on the total price that the potential cooperative users should charge. The distribution of the total saving among cooperative users is a matter of the planner. For example, it could be constant or proportional to the number of non-cooperative users served. Alternatively, it could be based on the use of the Shapley value (for an application, see Krajewska et al. 2008).

This brings the question of the fair price \(h_k\) that potential cooperative user k should receive if it acts in this capacity. This price should depend on the travel cost from its allocated facility i to its location, and also on the demand of the non-cooperative users allocated to it. For example in the Kenya problem (Rancourt et al. 2015), a cooperative user k may have to hire extra donkeys to carry the load of non-cooperative users from facility i. Because of potential economies of scale, the transport cost \(c_{ki}\) will not necessarily be multiplied by the total demand of the non-cooperative users assigned to k,  but will be scaled down by a positive factor \(\alpha _k\le 1.\) The potential cooperative user k may also bear a fixed transaction cost \(\beta _k\ge 0\) to transfer the food to each of these users.

More specifically, in general \(h_k\) should satisfy

$$\begin{aligned} h_k\ge \left( \alpha _k\sum _{i\in I}c_{ki}x_{ki}+\beta _k\right) \sum _{j\in J}d_jw_{jk}, \end{aligned}$$
(20)

where \(0\le \alpha _k\le 1\) and \(\beta _k\ge 0.\) In the situation depicted in Fig. 2c if \(\alpha _k=0.75\) and \(\beta _k=0,\) then the total price of cooperation, i.e., \(\sum _{k\in K}h_k,\) is 6 (\(=(1\times 2+3\times 2)\times 0.75\)), which is smaller than 7.5. In the CMM problem (the other cases being similar) jointly solving the planner’s problem and determining the \(h_k\) prices are achieved by solving the following model, where \(h_k\) is now a continuous variable which replaces the product \(h_kz_k\) in (1):

$$\begin{aligned} \hbox {(CMM2)}\quad&\hbox {minimize}\quad&\sum _{i\in I}g_iy_i+ \sum _{k\in K}h_k +&\sum _{j\in J}\sum _{i\in I}d_jc_{ji}x_{ji}+ \sum _{j\in J}\sum _{k\in K}d_jc_{jk}w_{jk}&\nonumber \\&\text {subject to}&\hbox {(2)--(6), (20).}&\end{aligned}$$

This model is non-linear because of the presence of the product \(x_{ki}w_{jk}\) in (20). As usual, it can be linearized by introducing the binary variables \(u_{ijk}=x_{ki}w_{jk}\) and imposing additional constraints:

$$\begin{aligned} h_k\ge \alpha _k \sum _{i\in I}\sum _{j\in J}d_jc_{ki}u_{ijk}&+\beta _k\sum _{j\in J}d_jw_{jk} \qquad k\in K \qquad \end{aligned}$$
(21)
$$\begin{aligned} u_{ijk}\le x_{ki}&\qquad i\in I, j\in J, k\in K \qquad \end{aligned}$$
(22)
$$\begin{aligned} u_{ijk}\le w_{jk}&\qquad i\in I, j\in J, k\in K \qquad \end{aligned}$$
(23)
$$\begin{aligned} x_{ki}+w_{jk}\le u_{ijk}+1&\qquad i\in I, j\in J, k\in K \qquad \end{aligned}$$
(24)
$$\begin{aligned} u_{ijk}\in \{ 0,1\}&\qquad i\in I, j\in J, k\in K. \end{aligned}$$
(25)

Remark 2

All the valid inequalities of Sect. 2.5 for CMM are also valid inequalities for CMM2 since all the variables in CMM are also variables of CMM2 and all the constraints of CMM are also constraints of CMM2.

In the CCC, CMC and CCM models, we can apply the same approach in the same way: the continuous variable \(h_k\) replaces the product \(h_kz_k\) in (1) and constraints (21)–(25) are added to the model. All these models, called CMM2, CCC2, CMC2 and CCM2, benefit from the valid inequalities presented in Sect. 2.5.

Another way of linearizing constraints (20) is to rewrite them in terms of flow variables. To avoid using the family of variables \(u_{ijk},\) we introduce a flow-based formulation for the CMM problem with a fair price of cooperation. Let \(f_{ik}\) be the flow from facility i to site k (k can be a cooperative user or a non-cooperative user), and let \(v_{kj}\) be the flow going from the cooperative user k to non-cooperative user j. Let M be a sufficiently large number. Then, the CMM problem with fair price of cooperation can be modeled as follows:

$$\begin{aligned}&\displaystyle \hbox {(CMM3)} \, \hbox { minimize} \sum _{i\in I}g_iy_i+ \sum _{k\in K}h_k +\sum _{i\in I}\sum _{j\in J}c_{ij}d_jx_{ij}+ \sum _{k\in K}\sum _{j\in J}c_{kj}v_{kj} \qquad \end{aligned}$$
(26)
$$\begin{aligned}&\displaystyle \quad \text {subject to} \, \sum _{i\in I}f_{ij}+\sum _{k\in K}v_{kj}\ge d_j \quad j\in J\end{aligned}$$
(27)
$$\begin{aligned}&\displaystyle \quad \sum _{i\in I}f_{ik}+\sum _{t\in K}v_{tk}-\sum _{j\in J}v_{kj} = d_k \quad k\in K\end{aligned}$$
(28)
$$\begin{aligned}&\displaystyle \quad \sum _{i\in I}\sum _{j\in J}f_{ij} = \sum _{j\in J}d_j\end{aligned}$$
(29)
$$\begin{aligned}&\displaystyle \quad {x_{ji}}\le y_i \quad i\in I,j\in J\end{aligned}$$
(30)
$$\begin{aligned}&\displaystyle \quad f_{ij}\le M {x_{ji}} \quad i\in I,j\in J\end{aligned}$$
(31)
$$\begin{aligned}&\displaystyle \quad h_k\ge \alpha _k\sum _{i\in I}c_{ik}(f_{ik}-d_k{x_{ki}})+\beta _k\sum _{j\in J}v_{kj}\quad k\in K\end{aligned}$$
(32)
$$\begin{aligned}&\displaystyle \quad y_i,{x_{ji}}\in \{ 0,1\} \quad i\in I,j\in J,k\in K\end{aligned}$$
(33)
$$\begin{aligned}&\displaystyle \quad h_k,f_{ij},v_{kj}\ge 0 \quad i\in I,j\in J,k\in K. \end{aligned}$$
(34)

Constraints (27) state that the demand of each user j is satisfied. Constraints (28) mean that all the potential cooperative users keep their own demand, and Constraint (29) that all the flow demand originates at the facilities. Constraints (30) and (31) ensure that there is no flow if the facility is closed or if the user is not allocated the potential facility. Constraints (32) guarantee that cooperative users receive a fair price for their service. The first term of the right-hand side is the cost incurred by k to carry to its site the demand of other users, while the second term is the cost of delivering the demand of other users. Two families of variables are binary while the remaining ones are continuous. The problems CCC3, CMC3 and CCM3 can be modeled in a similar way.

4 Computational results

The four models of Sect. 2 and the model of Sect. 3 were implemented in C\(^{++}\) and experiments were conducted on a PC with a 2.33 GHz Intel Xeon dual core processor, 8.5 GB of RAM, and operating system LINUX Debian 4.0. We used the optimization engine CPLEX v11.0.

Since these models follow a classical pattern and our contribution is not algorithmic we have not attempted to solve them on large instances in order to push an algorithm to its limit. Our purpose by carrying out numerical experiments is to gain insights on various aspects of the models. To keep the number of tests within a reasonable limit, we only present results on the CMM model. Our tests are made up of three parts. First, we wish to study the effect of point distribution on the number of open facilities and cooperative users in the solution, as well as on the various cost components. Second, we investigate the effect of \(h_k\) parameters with respect to the \(g_i\) parameters on the same solution attributes. We also compute solutions in which the \(h_k\) values are optimized as in the CMM2 model of Sect. 3. Third, we assess the effect of the valid inequalities on the solution time and on the LP relaxation value. The first tests are performed on randomly generated networks while the last two make use of 30 benchmark instances for the simple plant location problem in the web page http://www.math.nsc.ru/AP/benchmarks/UFLP/Engl/uflp_eucl_eng.html. All instances in the web page have 100 nodes which act both as users and as potential location of plants. Finally, demands are fixed to one in all tests. The results are presented in Tables 1, 2, 3, 4, 5, and 6 having the following column headings:

OF::

Number of open facilities.

CU::

Number of selected cooperative users.

f::

Total facility cost in the solution.

h::

Total cooperative user cost in the solution.

c(x)::

Total allocation cost to facilities in the solution.

c(w)::

Total allocation cost to cooperative users in the solution.

Total::

Total solution cost.

CPU (s)::

CPU time in seconds.

Gap (%)::

(optimal cost − LP relaxation cost)/ (optimal cost).

4.1 Effect of the point distribution

To study the effect of the point distribution on solution characteristics, we have generated 120 random instances, 30 of each of four instance types, in circles of radius 30 with a depot 0 located at the center. In each there are 90 users, nine potential facilities and 45 potential cooperative users. We define \(c_{ij}\) as the Euclidean distance between i and j,  where \(i,j\in \{ 0\}\cup I\cup J.\) We set \(g_i=2c_{0i}\)\((i\in I)\) and \(h_k=0\)\((k\in K).\)

Fig. 3
figure 3

Three concentric circles with varying user densities

Full size image

  • Type A: Uniform distribution for the users and the facilities. Randomly generate 90 users in the circle, 45 of which are potential cooperative users, and nine potential facilities

  • Type B: Non-uniform distribution for the users and uniform distribution for the facilities. The circle is partitioned into three concentric circles of radii 10, 20 and 30. Randomly generate 50 users in the large circle, then 30 in the intermediate circle and then 10 in the inner circle, half of which are potential cooperative users. This process results in three user densities: high (H) in the inner circle; medium (M) in the first ring; low (L) in the outer ring (Fig. 3). Randomly generate nine potential facilities in the large circle.

  • Type C: Uniform distribution for the users and non-uniform distribution for the facilities. Proceed as in Type B by first generating five, three and one potential facilities on the three circles, and then 90 users in the large circle.

  • Type D: Non-uniform distribution for the users and for the facilities. Proceed as in Type B to generate the users and as in Type C to generate the potential facilities.

Table 1 shows average results over the 30 instances of each type.

Table 1 Effect of the point distribution on the number of open facilities and cooperative users and on the cost
Full size table

Table 1 shows that on average the total cooperative allocation cost (c(w)) is always larger than the total facility allocation cost (c(x)). The number of selected cooperative users (CU) is also always larger than the number of open facilities (OF). However, the largest ratio CU/OF corresponds to Type B, which suggests that the value of having cooperative users is more important when the facilities are uniformly distributed but the users are not. Conversely, the smallest ratio CU/OF corresponds to Type C: cooperative users are less relevant when users are uniformly distributed but facilities are not. Finally, in terms of total cost the cheapest option corresponds to the case in which neither the users nor the facilities are uniformly distributed.

4.2 Effect of the \(h_k\) parameters

In Sect. 4.2 and 4.3, we consider the 100-node instances of the mentioned web page. We set \(|K|=0.5 |J|\) and we randomly select the potential cooperative users from J. To study the effect of the \(h_k\) parameters, we assume that all of them are equal to a common value \(\bar{h},\) and we successively set \(\bar{h}= 0, 0.25\bar{f}, 0.50\bar{f}, \bar{f}\) and \(\infty ,\) where \(\bar{f}\) is the average value of the potential facility operating costs defined in the benchmark library, and \(\infty \) means that the option of having cooperatives users is not activated, as in the simple plant location problem (Fernández and Landete 2015). The reason for defining values of \(\bar{h}\) as a function of \(\bar{f}\) is that cooperative users act as small facilities and then they should receive a consistent compensation. The results of these experiments are reported in Table 2. All entries are average values over the 30 instances.

Table 2 Effect of the \(h_k\) parameters on the number of open facilities and cooperative users and on the cost
Full size table

From Table 2, we see that the number of open facilities varies from 13.6 to 6.4 depending on the price set by the users to act as cooperative users. When \(\bar{h}=0.25\bar{f}\) or \(0.50\bar{f}\), the installation cost of facilities is by far larger than that of cooperative users, namely f / h is equal to 1.9 and 3.8, respectively. Trivially, in terms of total cost, the cheaper is the price of cooperative users, the smaller is the total cost.

Fig. 4
figure 4

Percentage increase of the total solution cost and the total allocation costs to facilities when the \(h_k\) values are optimized: \(\alpha _k=0.25\) and \(\bar{h}=0.12\bar{f}\)

Full size image
Fig. 5
figure 5

Percentage increase of the total solution cost and the total allocation costs to facilities when the \(h_k\) values are optimized: \(\alpha _k=0.50\) and \(\bar{h}=0.16\bar{f}\)

Full size image
Fig. 6
figure 6

Percentage increase of the total solution cost and the total allocation costs to facilities when the \(h_k\) values are optimized: \(\alpha _k=0.75\) and \(\bar{h}=0.22\bar{f}\)

Full size image

In order to gain an insight into the change in the total solution cost produced by optimizing the price of cooperation, we have performed a second set of experiments. First, the CMM2 model was solved by setting \(\alpha _k=0.25, 0.50, 0.75\) and \(\beta _k=0\) for all \(k\in K.\) Then, \(\bar{h}\) was computed as the average of h divided by the average of CU (for the 30 benchmark instances), and the CMM model was solved for this \(\bar{h}.\) Since the CMM2 model has too many variables, the first 30 nodes of each benchmark instance were chosen. In particular, \(\bar{h}\) was set equal to \(0.12\bar{f}, 0.16\bar{f}\) and \(0.22\bar{f}\) for \(\alpha _k=0.25, 0.50, 0.75,\) respectively. Figures 4, 5 and 6 show both the percentage increase in the total solution cost and in the total facility allocation cost that the planner would incur if each cooperative user had an individual price holding constraint (20) instead of a common cooperation cost equal to \(\bar{h}.\) In Figs. 4, 5 and 6, the horizontal axis shows the labels of the instances sorted in non-decreasing order of total increase of the solution cost. The vertical axis is for the percentage increase. Figure 4 shows that when \(\alpha _k=0.25,\) the increase in the total solution cost (blue line) can be positive or negative but it is always small, it varies from \(-0.387\) to 3.54%. Figures 5 and 6 show that when \(\alpha _k=0.15\) and \(\alpha _k=0.05\) the increase in the total cost is always positive and still small, it goes from 1.28% to 7.51% or to 0.84% to 5.52\(\%,\) respectively, i.e., paying a common price is generally cheaper for the planner than paying individual prices. In fact, if the increase is negative it is because \(\alpha _k\) is small. In contrast, the increase in total facility allocation cost (orange line) can be large, positive or negative. In conclusion, although the decision of which facilities to open and which potential cooperative users to select can strongly differ between optimizing the price of cooperation or not, the total solution cost moderately increases.

Table 3 Effect of individual prices
Full size table

Table 3 summarizes the results of Figs. 4, 5 and 6. Since \(\bar{f}=3000\) in the data benchmark, the coefficients 0.12, 0.16 and 0.22 in \(h_k\) follow from \(2363.9/(6.3\times 3000),\)\(1931.9/(4.1\times 3000),\) and \(1214.7/1.9\times 3000),\) respectively.

4.3 Effect of the valid inequalities

Finally, we test the impact of the valid inequalities on the CPU time and on the optimality gap yielded by the LP relaxation of CMM and CMM2. We also report the CPU time and the optimality gap of the CMM3 model. And as in Sect. 4.2, we set \(|K|=0.50|J|.\) For the purpose of these experiments, we classify the valid inequalities of Sect. 2.5 into two types.

  • Type V1: Inequalities (12) and (13) of Proposition 2. We introduce in the model a limited number of these inequalities for \(e=3\) and \(e=4.\) For \(e=4,\) we set \(R=\{ i_1=j, i_2=j_1,i_3=j_2, i_4=j_3\}\) where \(j\in K,\) and \(j_1, j_2, j_3\) are the first, second and third neighbours of j. For \(e=3\) we set \(R=\{ i_1=j, i_2=j_1,i_3=j_2\} .\)

  • Type V2: Inequalities (16) and (17) of Proposition 3. We introduce in the model a limited number of these inequalities. For each \(j\in J,\) we define \(T_p\) as the set of the five closest neighbors of j in \(I\cup K.\)

The effect of the two types of inequalities was tested for the CMM and CMM2 models. For the CMM model, we successively set all \(h_k\) values equal to \(0.50\bar{f}\) and \(0.25\bar{f},\) and for the CMM2 model we successively set all \(\alpha _k\) values to 0.25, 0.50 and 0.75. For CMM2, we only considered the 30 first nodes of each benchmark instance, as in Sect. 4.2.

Equalities (11) are added to any combination and all entries in Tables 4, 5 and 6 are average values over the 30 instances.

We did no implement an exact separation for constraints (13) since our main aim was to determine whether it is worth integrating these valid inequalities within a branch-and-cut algorithm. The heuristic separation of inequalities of Types V1 and V2 is based on the idea that the sites in the neighbourhood of a user have more influence on the role of this user than the sites that are further away.

Table 4 Effect of the valid inequalities on the CPU time and on the optimality gap yielded by the LP relaxation of CMM
Full size table

Table 4 summarizes the results obtained by adding valid inequalities to the CMM model. We have tested the three combinations of Types V1 and V2. Table 4 shows that the instances with \(h_k=0.50\bar{f}\) are very easy in terms of gap and CPU time, and do not benefit from the introduction of valid inequalities. In fact, since all instances require less than 12 s of CPU time and have less than 2% of LP gap, adding more constraints slows down the solver and yields the same LP gap. When \(h_k=0.25\bar{f}\), the instances require more CPU time and the valid inequalities yield a small reduction in CPU time. The best option is to only add inequalities of Type V2.

It is interesting to point out that the saving in time due to the inclusion of inequalities of Type V2 results from the time saving on the difficult instances, as Fig. 7 shows. In Fig. 7, the horizontal axis is for the instance (there are 30 in total) and the vertical axis is for the CPU time in seconds. If the instances are ordered in non-decreasing order of CPU time, the blue line represents the CPU time when no inequality is added and the orange line represents the CPU time when inequalities of Type V2 are added. The orange line increases slower than the blue line.

Table 5 Effect of the valid inequalities on the CPU time and on the optimality gap yielded by the LP relaxation of CMM2
Full size table
Table 6 CMM2 with valid inequalities versus CMM3
Full size table
Fig. 7
figure 7

CPU time in seconds for solving the 30 benchmark instances

Full size image

Table 5 summarizes the results obtained by adding valid inequalities to the CMM2 model. We only report the optimality gap yielded by the LP relaxation because none of the inequalities reduces that gap. The effect on CPU time varies depending on the value of \(\alpha _k.\) For \(\alpha _k=0.25\) the smallest CPU time corresponds to the addition of inequalities of Type V1 exclusively. For \(\alpha _k=0.50\) and \(\alpha _k=0.75\), the best option is to add all the valid inequalities or none of them, respectively. Bold figures indicate the best option in terms of CPU time for the different values of \(\alpha _k\).

Table 6 compares the CPU time and the LP gap of the best implementation of the CMM2 and CMM3 models. It shows that the CMM3 model requires by far less CPU time although it yields larger gaps.

5 Conclusions

We have introduced the concept of cooperative users in facility location problems with a median or a covering objective. We have modeled four classes of problems and we have developed several families of valid inequalities. We have shown how the fair price of cooperation can be determined through the solution of a non-linear mathematical model. We have conducted several computational experiments on randomly generated and benchmark instances in order to study the effect of point distribution on the number of open facilities and cooperative users, the effect of the price set by cooperative users, and the effect of the valid inequalities. Our results have shown that depending on the values taken by the instance parameters, resorting to cooperative users can help decrease the fixed costs and the allocation cost. In addition, one class of valid inequalities helps reduce the CPU time, especially for the more difficult instances, and all the valid inequalities are useful in a branch-and-cut algorithm.