1 Introduction

The \((r|p)\)-centroid problem (RPCP) is a competitive facility location problem, in which two decision makers compete for market share. They both want to serve customers from a given market. There are several variants of this problem which differ in the way facilities are opened, in the elasticity of the demand and especially in the behaviour of the customers. In our work we consider a discrete basic variant with the following assumptions:

  • Facilities can be opened at a given finite set of possible positions. At one position at most one facility can be located.

  • Both competitors open facilities sequentially, i.e., the first decision maker, called the leader, opens \(p\) facilities and is followed by the other decision maker, the follower, who successively places all of his \(r\) facilities.

  • Customer decision is based on distance solely, i.e., customers always choose their serving facility to be the closest.

  • Customers have a binary preference, i.e., they fulfill all of their demand by choosing the nearest facility only.

Competitive facility location problems are known since the late 20s and were first mentioned by Hotelling (1929). Hakimi (1983) introduced the name \((r|p)\)-centroid and also published the first complexity results for it.

An application of this problem is when two entrepreneurs want to start selling the same products for the same price in a new market. The first one, the leader, who opens her selling facilities wants to keep as much of her market share as possible even when a competitor, the follower, enters the market. Since the leader cannot know where her competitor will place his facilities she assumes that he places them optimally. Considering that, the leader can determine her guaranteed (minimum) market share.

The discrete RPCP on not further constrained bipartite graphs is \(\Sigma _2^P\)-hard (Noltemeier et al. 2007). In short this means that under the assumption that the polynomial hierarchy does not collapse this problem is substantially harder to solve than any problem in NP.

In Sect. 2 we give a formal problem definition. After discussing the related work in Sect. 3, we present different candidate solution evaluation methods in Sect. 4. A novel hybrid genetic algorithm (GA), which incorporates a solution archive in order to store and transform already visited solutions, as well as a local improvement component is introduced in Sect. 5. Different concepts of how the local search method can benefit from the solution archive are investigated in Sect. 6. An extension to the GA which intends to lower the effort for solution evaluation by applying a multi-level strategy is presented in Sect. 7. Finally, we discuss computational results and compare the new method to other state-of-the-art approaches from literature in Sect. 8.

2 Problem definition

The discrete RPCP is defined on a weighted complete bipartite graph \(G=(I,J,E)\) where \(I=\{1,\ldots , m\}\) represents the set of potential facility locations, \(J=\{ 1,\ldots , n\}\) the set of customers, and \(E=I\times J\) is the set of edges. Let \(w_j>0, \forall j\in J\) be the weight of each customer, which corresponds to the turnover to be earned by the serving decision maker and \(d_{ij}, \forall (i,j)\in E\), be the distances between customers and potential facility locations. The goal for the leader is to choose exactly \(p\) locations from \(I\) in order to maximize her turnover under the assumption that the follower in turn chooses \(r\) facilities from different locations maximizing his turnover.

Each customer \(j\in J\) chooses the closest facility, hence the owner of this closest facility gains all of the turnover \(w_j\); in case of equal distances the leader is preferred. In the following we give a formal definition of a candidate solution and the turnover computation. Let \((X,Y)\) be a solution to the RPCP, where \(X\subseteq I,\ |X|=p\) is the set of locations chosen by the leader and \(Y\subseteq I \setminus X,\ |Y|=r\) is the associated set of follower locations. Further, let \(D(j, V)=\min \{d_{ji} \mid i \in V \},\ \forall j\in J, V\subseteq I\) be the minimum distance from customer \(j\) to all facility locations in set \(V\). Then the set of customers which are served by one of the follower’s facilities is \(U^\mathrm {f}=\{j\in J \mid D(j,Y) < D(j, X) \}\) and the customers served by the leader is given by \(U^\mathrm {l}=J\setminus U^\mathrm {f}\). The turnover of the follower is \(p^\mathrm {f}=\sum _{j\in U^\mathrm {f}}w_j\) and the turnover of the leader \(p^\mathrm {l} = \sum _{j\in J}{w_j} - p^\mathrm {f}\).

The problem of finding the optimal set of locations \(Y\) for the follower when \(X\) is given is also called the \((r|X_p)\)-medianoid problem and is proven to be NP-hard (Hakimi 1983). Noltemeier et al. (2007) showed in their work that the \((r|p)\)-centroid problem is \(\Sigma _2^P\)-hard. This result is strenghtened by Davydov et al. (2014b) who proved that the problem we consider here remains \(\Sigma _2^P\)-hard even for planar graphs with Euclidean distances.

3 Related work

Competitive facility location models, to which the discrete RPCP belongs, are a quite old and well-studied type of problem originally introduced by Hotelling (1929). A recent review about several kinds of competitive location models can be found in the work by Kress and Pesch (2012). They also mention the discrete RPCP, which was originally introduced by Hakimi (1983) along with some first complexity results.

Laporte and Benati (1994) developed a tabu search heuristic for the RPCP. They use an embedded second-level tabu search for solving the \((r|X_p)\)-medianoid problem. The final solution quality is thus only approximated as the \((r|X_p)\)-medianoid problem is not solved exactly.

Alekseeva et al. (2010) present several approaches for the discrete RPCP including an exact procedure. The first method is a hybrid memetic algorithm (HMA) which uses a probabilistic tabu search as local improvement procedure. It employs rather simple genetic operators and the tabu search utilizes a probabilistic swap neighborhood structure, which is well known from the \(p\)-median problem; see the review article by Mladenović et al. (2007) for an overview of this problem. A neighborhood of this structure contains elements only with a given probability to speed up the search. They use the linear programming relaxation of a mixed integer linear programming (MIP) model for the solution evaluation which will be described here in Sect. 4.1. The authors observe that this approach outperforms several simpler heuristics including an alternating heuristic originally proposed for a continuous variant of the problem (Bhadury et al. 2003). In Alekseeva and Kochetov (2013) results for the tabu search alone are presented which are similar to the results of the HMA. They further describe an exact method based on a single level binary integer program with exponentially many constraints and variables. For solving this model they present an algorithm similar to a column generation approach where new sets of locations for the follower are iteratively added to the model which is then solved again. The optimal value of this model defines an upper bound and by solving the follower’s problem using solutions of the model a lower bound is obtained. If the bounds coincide the optimum has been found. The HMA is applied for finding the initial family of follower solutions. Using this method the authors are able to optimally solve instances with up to 100 customers and \(p=r=5\).

Campos-Rodríguez et al. (2009) studied particle swarm optimization methods for the continuous RPCP, where the facilities can be placed anywhere on the Euclidean plane, as well as for the discrete variant (Campos-Rodríguez et al. 2012). A jumping particle swarm optimization is used with two swarms, one for the leader and one for the follower. The particles jump from one solution to another in dependence of its own best position so far, the best position of its neighborhood and the best position obtained by all particles so far, i.e, the best global position. In the experiments this algorithm was able to solve instances with 25 customers, \(p=3\) and \(r=2\) to optimality.

Davydov et al. (2012) describe another tabu search for the RPCP. They use a probabilistic swap neighborhood structure similar to the one developed by Alekseeva et al. (2010). For the solution evaluation the follower problem is approximately solved by Lagrangian relaxation. The method is tested on the instances from Alekseeva et al. (2010) and additionally on some non-Euclidean instances. For many of the instances optimal solutions are obtained.

A recent article by Davydov et al. (2014a) proposes two metaheuristics which are both based on the swap neighborhood structure. The first one uses a variable neighborhood search (VNS) with a disjoint partitioning of the swap neighborhood structure into three sub-neighborhoods Fswap, Nswap, and Cswap. A neighbor from the Fswap neighborhood is determined by closing one leader facility and opening a facility at a location chosen by the follower. The Nswap neighborhood consists of solution candidates that are generated by closing one leader facility and opening a facility at a location in its vicinity. Cswap consists of all solutions that are in the swap neighborhood but not already in Fswap or Nswap. The second method, which is called STS, uses the probabilistic swap neighborhood which has been proposed by Alekseeva et al. (2010). The STS uses the same neighborhood partioning as the VNS. Additionally, a tabu list is maintained to remove elements of the neighborhood which consist of pairs for leader facilities that have been closed and opened during the last few iterations. Both methods use the same model for the solution evaluation as Alekseeva et al. (2010). The authors were able to find good solutions for many instances faster than the tabu search by Davydov et al. (2012). Moreover, they tested their algorithms on non-euclidean instances, on which both methods, VNS and STS, showed similar performance.

Roboredo and Pessoa (2013) developed an exact branch-and-cut algorithm for the discrete RPCP. They use a single-level integer programming model which is similar to the model by Alekseeva et al. (2010) but with only a polynomial number of variables. It consists of exponentially many constraints, one for each follower strategy, i.e., for each set of possible facility locations of the follower. An important reason for the success of their method is the introduction of strengthening inequalities by lifting the exponentially many constraints. Due to the assumption that the customers are conservative the lower bound on the leader’s solution becomes zero if the follower chooses the same facility location. Therefore, for each facility location an alternative location is given which is chosen if the position has already been used by the leader. These cuts are separated either by a greedy heuristic or by solving a mixed integer programming model. For most of the benchmark instances the authors report better results than Alekseeva et al. (2010), i.e., they found optimal solutions in less time. Instances with 100 customers and up to \(r=p=15\) facilities could be solved to optimality. The authors also present promising results for \(r=p=20\) but are not able to prove their optimality within the given time limit of 10 hours.

Alekseeva and Kochetov (2013) give an overview of recent research regarding the discrete RPCP. They also improve their iterative exact method by using a model with only a polynomial number of variables and by using the strengthening inequalities introduced by Roboredo and Pessoa. This improved iterative approach is able to find optimal solutions for instances with up to 100 customers and \(r=p=15\). Especially for the instances with \(r=p\in \{5,10\}\) optimal solutions are found significantly faster than by the branch-and-cut algorithm from Roboredo and Pessoa (2013).

As mentioned before there are several other variants of the problem. Kochetov et al. (2013) describe an algorithm for the RPCP with fixed costs for opening a facility and customers splitting their demand over all facilities proportional to attraction factors. The algorithm’s principle is similar to the alternating heuristic for the RPCP (Bhadury et al. 2003). Another work which assumes proportional splitting of the demands is done by Biesinger et al. (2014). There the authors employ a GA in combination with a solution archive similar to this work to solve the problem.

Ghosh and Craig (1984) work on a competitive location model for choosing good positions for retail convenience stores. They do not specify the number of stores to open beforehand but determine the optimal number as part of the process and additionally assume elastic demands, i.e., the customers may not want to fulfill their whole demand if the store is too far away. The authors develop a heuristic enumerative search algorithm for solving this problem.

Serra and Revelle (1994) propose a heuristic approach for a variant of the discrete RPCP which is based on repeatedly solving a maximum capture (MAXCAP) problem. The MAXCAP problem is similar to the \((r|X_p)\)-medianoid problem with the difference that it is possible to place a facility on one of the leader’s locations with the result that the captured demand is equally shared between the two players. The algorithm is basically a local search using the swap neighborhood structure and candidate solutions are evaluated by solving the MAXCAP problem by means of integer programming or by using a local search heuristic for larger instances.

Drezner (1994, 1998) and Drezner et al. (2002) use a gravity model for solving a continuous competitive facility location problem. The gravity model assumes that customers prefer being served by facilities proportional to an attraction factor and inversely proportional to their distances. The authors suggest several heuristics and metaheuristics including simulated annealing for solving the problem and compare them to each other.

4 Solution evaluation

We extend the problem definition of Sect. 2 by the following further definitions which are adopted from Alekseeva and Kochetov (2013).

Definition 1

Semi-feasible Solution

The tuple \((X,Y)\) is called a semi-feasible solution to the discrete RPCP iff \(X\subseteq I\) with \(|X|=p, Y\subseteq I\) with \(|Y|=r\) and \(X\cap Y =\emptyset \).

Let \(p^\mathrm {l}(X,Y)\) be the turnover of the leader and \(p^\mathrm {f}(X,Y)\) be the turnover of the follower where \(X\) is the set of facility locations chosen by the leader and \(Y\) is the set of facility locations chosen by the follower. Then we define a feasible solution and an optimal solution as follows.

Definition 2

Feasible Solution

A semi-feasible solution \((X,Y^*)\) is called a feasible solution to the discrete RPCP iff \(p^\mathrm {f}(X,Y^*)\ge p^\mathrm {f}(X, Y)\) for each possible set of follower locations \(Y\).

Definition 3

Optimal Solution

A feasible solution \((X^*,Y^*)\) is called an optimal solution to the discrete RPCP iff \(p^\mathrm {l}(X^*,Y^*)\ge p^\mathrm {l}(X,Y)\) for each feasible solution \((X,Y)\).

It is easy to find a semi-feasible solution but already NP-hard to find a feasible solution because an optimal follower solution has to be found and the \((r|X_p)\)-medianoid problem is NP-hard. This means that the solution evaluation of an arbitrary leader solution might be quite time-consuming. For practice there are several possibilities how to evaluate such a leader solution \(X\). In the next section we will examine a mathematical model for the RPCP and derive different options.

4.1 Bi-Level MIP Formulation

The following bi-level MIP model has been introduced in Alekseeva et al. (2009). It uses three types of binary decision variables. Variables \(x_i, \forall i\in I,\) are set to one if facility \(i\) is opened by the leader and to zero otherwise. Variables \(y_i, \forall i\in I,\) are set to one iff facility \(i\) is opened by the follower. Finally, variables \(z_j, \forall j\in J,\) are set to one if customer \(j\) is served by the leader and set to zero if customer \(j\) is served by the follower.

We further define the set of facilities that allow the follower to capture customer \(j\) if the leader uses solution \(x (x=(x_i)_{i\in I})\):

$$\begin{aligned} I_j(x)=\left\{ i\in I \mid d_{ij} < \min _{l\in I\mid x_l=1} d_{lj}\right\} \quad \forall j\in J \end{aligned}$$

Then we can define the upper level problem, denoted as leader’s (or \((r|p)\)-centroid) problem, as follows:

$$\begin{aligned} \max _x~&\sum _{j\in J}{w_jz_j^*}&\end{aligned}$$
(1)
$$\begin{aligned} \text{ s.t. } \quad&\nonumber \\&\sum _{i\in I}{x_i}=p \end{aligned}$$
(2)
$$\begin{aligned}&{x_i}\in \{0,1\}\qquad&\forall i\in I \end{aligned}$$
(3)

where \(z^*\) is an optimal solution to the lower level problem, denoted as follower’s (or \((r|X_p)\)-medianoid) problem:

$$\begin{aligned} \max _{y,z}~&\sum _{j\in J}{w_j(1-z_j)} \end{aligned}$$
(4)
$$\begin{aligned} \text{ s.t. } \quad&\nonumber \\&\sum _{i\in I}{y_i}=r \end{aligned}$$
(5)
$$\begin{aligned}&1-z_j\le \sum _{i\in I_j(x)}y_i&\quad \forall j\in J \end{aligned}$$
(6)
$$\begin{aligned}&x_i+y_i\le 1&\quad \forall i\in I \end{aligned}$$
(7)
$$\begin{aligned}&z_j \ge 0&\quad \forall j\in J \end{aligned}$$
(8)
$$\begin{aligned}&{y_i}\in \{0,1\}&\quad \forall i\in I,\quad \forall j\in J \end{aligned}$$
(9)

The objective function for the leader’s problem (1) maximizes the leader’s turnover. Equation (2) ensures that the leader places exactly \(p\) facilities. The objective function for the follower’s problem (4) maximizes the follower’s turnover. Similarly as in the leader problem, (5) ensures that the follower places exactly \(r\) facilities. Inequalities (6) together with the objective function ensure the \(z_j\) variables to be set correctly, i.e., decide for each customer \(j\in J\) from which competitor he is served. Inequalities (7) guarantee that the follower does not choose a location where the leader has already opened a facility. Variables \(z_j\) are not restricted to binary values because in an optimal solution they will become \(0\) or \(1\) anyway.

For the simplicity of notation, we use in the remaining paper both, the set notation \(X\) and \(Y\) as well as the incidence vector notation \(x\) and \(y\), to refer to leader and follower solutions, respectively.

4.2 Solution evaluation methods

In our metaheuristic approach we consider the following natural ways of evaluating a leader solution \(x\); two of them use the model introduced before.

4.2.1 Exact evaluation

In the exact evaluation we solve the follower’s problem (4–9) exactly using a MIP solver. In our implementation we used the IBM ILOG CPLEX Optimizer in version 12.5.

4.2.2 Linear programming (LP) evaluation

In the LP evaluation we solve the LP relaxation of the follower’s problem exactly using CPLEX. This will in general yield not even semi-feasible solutions because of fractional values of some variables. For intermediate solution candidates we might, however, only be interested in an approximate objective value of a leader’s solution for which purpose this method may be sufficient. This approximation yields a lower bound of the real objective value of \(x\).

4.2.3 Greedy evaluation

In the greedy evaluation we use the following greedy algorithm for solving the follower’s problem, which will yield semi-feasible solutions and therefore an upper bound to the objective value of \(x\). Follower facilities are placed one after the other according to the following greedy criterion: For each facility every possible remaining location is checked how much turnover gain its selection would generate. The turnover gain is the sum of weights of all customers that would so far be served by the leader but are nearer to this location than to the nearest leader facility. Then the location with the maximum turnover gain is always selected. This process is iterated until \(r\) locations are chosen. Ties are broken randomly.

In Sect. 8.1 we will observe that among our evaluation algorithms LP evaluation usually offers the best compromise in terms of speed and evaluation precision. However, by applying the different solution evaluation methods in a joined way within a multi-level evaluation scheme described in Sect. 7, we will be able to significantly improve the performance.

5 Genetic algorithm with solution archive

This section describes our genetic algorithm. The framework is a rather standard steady-state GA with an embedded local improvement. It uses simple genetic operators, which are explained in Sect. 5.1. The local improvement procedure is based on the swap neighborhood structure and is addressed in Sect. 5.2. Most importantly, the GA utilizes a complete solution archive for duplicate detection and conversion, which is detailed in Sect. 5.3.

We use the leader’s incidence vector \(x\) as solution representation for the GA. The initial population is generated by choosing \(p\) locations uniformly at random to ensure high diversity in the beginning. Then, in each GA iteration one new solution is derived and always replaces the worst solution of the current population. Selecting parents for crossover is performed by binary tournament selection with replacement. Mutation is applied to offsprings with a certain probability in each iteration.

5.1 Variation operators

We use the following variation operators within the GA:

Crossover operator Suppose that we have two candidate solutions \(X^1 \subset I\) and \(X^2 \subset I\). An offspring \(X'\) is derived from its parents \(X^1\) and \(X^2\) by adopting all locations that are opened in both, i.e., all locations from \(S = X^1 \cap X^2\) and then choosing the remaining \(p-|X^1 \cap X^2|\) locations from \((X^1 \cup X^2) \setminus S\), i.e., the set of locations that are opened in exactly one of the parents, uniformly at random.

Mutation operator Mutation is based on the swap neighborhood structure, which is also known from the \(p\)-median problem (Mladenović et al. 2007). A swap move closes a facility and re-opens it at a different, so far unoccupied position. Our mutation applies \(\mu \) random swap moves, where \(\mu \) is determined anew at each GA-iteration by a random sample from a Poisson distribution with mean value one so that each position is mutated independently with probability \(\frac{1}{p}\).

5.2 Local search

Each new candidate solution derived in the GA via recombination and mutation whose objective value is at most \(\alpha \%\) off the so far best solution value further undergoes a local improvement, with \(\alpha =5\) in our experiments presented here. Local search (LS) is applied with the swap neighborhood structure already used for mutation. The best improvement step function is used, so all neighbors of a solution that are reachable via one swap move are evaluated and a best one is selected for the next iteration. This procedure terminates with a local optimal solution when no superior neighbor can be found.

5.3 Solution archive

Solution archives for evolutionary algorithms as introduced by Raidl and Hu (2010) are data structures that efficiently store all generated solutions in order to be able to detect duplicate solution when they occur. Upon detecting a duplicate, an effective solution conversion is performed, which results in a guaranteed not yet considered solution typically in close proximity to the original (duplicate) solution. Especially when the solution evaluation is expensive, which is the case for the RPCP at least when performing an exact evaluation, costly and unnecessary re-evaluations are avoided supposedly resulting in an overall faster optimization. Additionally, diversity is maintained in the population and premature convergence is reduced or avoided as well. Successful applications of this concept on various test functions including NK landscapes and Royal Road functions and the generalized minimum spanning tree problem can be found in Raidl and Hu (2010) and Hu and Raidl (2012), respectively.

After each iteration of the genetic algorithm the newly created offspring is inserted into the archive. If this solution is already contained in the archive, the solution conversion is automatically performed and this adapted and guaranteed new solution is integrated in the population of the GA. The conversion operation can therefore also be considered as “intelligent mutation”. The data structure used for the solution archive must be carefully selected in order to allow efficient realizations of the essential insert, look-up and conversion operations and in particular depends on the solution representation. As suggested in Raidl and Hu (2010) a trie data structure, which is typically used for storing a large set of strings (Gusfield 1997) like in language dictionary applications, is particularly well suited for binary representations because all the essential operations can be performed in \(\mathcal {O}(h)\) time, where \(h\) is the maximum string length. In our case for the RPCP the insertion and the conversion procedure run both in \(\mathcal {O}(m)\) time and almost independent of the number of created / stored solutions. The next sections describe the trie data structure and the specific operations of the solution archive we use for the RPCP in detail.

5.4 Trie structure

Our trie is a binary tree \(T\) with maximum height \(m\), the number of possible facility locations, see Fig. 1. On each level \(l=1,\ldots ,m\) of the trie there exist at most \(2^{l-1}\) trie nodes, denoted by a rectangle in Fig. 1. Each trie node \(q\) at level \(l\) has the same structure consisting of two entries \(q.\mathrm {next}[0]\) and \(q.\mathrm next [1]\), denoted by the division of a rectangle into two parts. Each entry can be either a pointer to a subtree rooted at a successor node on level \(l+1\) (denoted by an arrow), a null-pointer (denoted by a slash), or a complete-pointer (denoted by a \(C\)).

Fig. 1
figure 1

Solution archive with some inserted solutions on the lefthand side and a conversion of \((0,0,1,1,0,0,1)\) into the new solution \((0,1,1,1,0,0,0)\) on the righthand side

Full size image

Let \(x=(x_1,\ldots ,x_m)\) be the binary vector representing a candidate leader solution. Then each node \(q\) at level \(l\) is related to variable \(x_l\) and the entries \(q.\mathrm {next}[0]\) and \(q.\mathrm next [1]\) split the solution space into two subspaces with \(x_l=0\) and \(x_l=1\), respectively. In both subspaces all elements from \(x_1\) to \(x_{l-1}\) are fixed according to the path from the root to node \(q\). For example, in Fig. 1 the node on level 2 separates the solution space into solution candidates starting with \((0,0)\) and \((0,1)\). A null-pointer represents a yet completely unexplored subspace, while a complete-pointer denotes that already all solutions of the corresponding subspace have been considered. Note that such a trie is somewhat related to an explicitly stored branch-and-bound tree.

5.5 Insertion

figure a

Algorithm 1 shows how to insert a new candidate solution \(x=(x_1,\ldots ,x_m)\) into the trie. Initially, the recursive insertion method is called with parameters \((x,1,root,0)\). We start at the root node at level 1 with the first element \(x_1\). At each level \(l=1,\ldots ,m\) of the trie we follow the pointer indexed by \(x_l\). When the \(p\)-th facility has been encountered, i.e., \( openFacs =p\), at some node \(q\) the procedure stops and we set \(q.\)next\([1]\) to complete. We further check at each insertion of a “one” at trie node \(q\) if enough facilities would still fit if instead a zero would be chosen. If this is not the case, \(q.\mathrm {next}[0]\) is set to complete to indicate that there is no valid candidate solution in this subtrie. A set of feasible deviation positions, \(devpoints\), is computed during the insertion and needed for the potentially following conversion. This set is cleared at the beginning of each solution insertion and contains all trie nodes visited during insertion where both entries are not complete. When we encounter a complete-pointer we know that this solution is already contained in the trie and it must be converted.

If we are finished with the insertion and the solution is not a duplicate, we prune the trie if possible to reduce its memory consumption. Pruning is performed by checking all trie nodes that have been visited during insertion bottom up if both entries of a trie node \(q\) are set to complete. If \(q.\hbox {next}[0]=q.\hbox {next}[1]= complete \) we prune this trie node by setting the corresponding entry of the preceding trie node to complete. On the left-hand side of Fig. 1 an example of a trie containing the three solutions \((0,0,1,1,0,0,1), (0,1,0,1,1,0,0)\), and \((0,0,1,0,1,1,0)\) is given. The “C” stands for a complete-pointer and the “/” for a null-pointer. The crossed out node at level 7 is a demonstration of setting a “zero” entry to complete because no more feasible solution fits in this subtrie and of the pruning that followed.

Note that no explicit look-up procedure is needed because the insertion method sketched in Algorithm 1 integrates the functionality to check whether or not a candidate solution is already contained.

5.6 Conversion

figure b

When the insertion procedure detects a solution which is already contained in the archive, a conversion into a new solution is performed. A pseudocode of this procedure is given in Algorithm 2. In order to modify a solution, we have to apply at least two changes: open a facility and close another one. For the first change, let \( devpoints \) denote the set of feasible deviation points computed during insertion. A trie node \(q\) at level \(l\) is chosen from this set uniformly at random. Should this set be empty, we know that the whole search space has been covered and we can stop the optimization process with the so far best solution being a proven optimum. Otherwise we set the \(l\)-th element of the solution vector to \(1-x_l\), which corresponds to opening or closing a facility at position \(l\). Now we have to apply a second (inverse) change at a later position in order to have exactly \(p\) facilities opened. We go down the subtrie level by level using the following strategy. For each trie node \(q'\) at level \(l'\) we prefer to follow the original solution, i.e., the pointer \(q'.\mathrm {next}[x_{l'}]\). If it is complete, we have no choice but to use the pointer \(q'.\mathrm {next}[1-x_{l'}]\) instead (which corresponds to adding further modifications to the solution vector). As soon as we reach a null-pointer at a trie node \(q'\) at level \(l'\), we know that the corresponding subspace has not been explored yet, i.e., any feasible solution from this point on is a new one. Therefore, we apply the remaining necessary changes to get a feasible solution. If the number of opened facilities in \(x\) exceeds \(p\), we close the appropriate number of facilities randomly among \(\{x_{l'+1},\ldots ,x_m\}\). Otherwise, if this number is smaller than \(p\), we open the appropriate number of facilities analogously. Finally, this new solution is inserted by applying Algorithm 1 starting from trie node \(q'\) at level \(l'\).

On the righthand side of Fig. 1 an example of a solution conversion is shown. The duplicate solution \(x=(0,0,1,1,0,0,1)\) is inserted into the trie and subsequently converted. Node \(q\) on level 2 is chosen as the deviation point for the first change and we set \(x_2=1\), resulting in solution \((0,1,1,1,0,0,1)\). Since the alternative entry at \(q.\mathrm {next}[1]\) points to another trie node, this path is followed until a null-pointer is reached at level 3. Then we close the facility at the randomly chosen position 7 to get the valid solution \((0,1,1,1,0,0,0)\).

5.7 Randomization of the trie

The above conversion procedure can only change values of solution elements with a greater index than the level of the deviation position. This induces an undesirable bias towards elements on positions with higher indices being changed more likely. In order to counter this problem, a technique called trie randomization is employed, which has first been suggested by Raidl and Hu (2010). For each search path of the trie we use a different ordering of the solution variables, i.e., a trie node on level \(l\) does not necessarily correspond to element \(x_l\) of the solution vector. Instead, the index of the element related to a trie node \(q\) is chosen randomly from the indices not already used in the path from the root to node \(q\). In our case this is achieved by additionally storing the corresponding variable index at each trie node. Another possibility is to compute the next index by a deterministic pseudo random function taking the path from the root to node \(q\) as input. This method saves memory but needs more computational effort and is applied in Raidl and Hu (2010). Figure 2 shows an example of a randomized trie. Although this technique cannot avoid biasing completely, the negative effect is substantially reduced.

Fig. 2
figure 2

Candidate solutions (0,1,1,0,0), (1,0,1,0,0), and (0,0,0,1,1) in a randomized trie, where the variables are randomly associated with the levels

Full size image

6 Local and tabu search with solution archive

There exist several options for possibly utilizing the archive not just within the GA but also the embedded LS, based on the original swap neighborhood structure.

6.1 Complete neighborhood

The simplest way to perform LS is just to use the complete neighborhood as introduced in Sect. 5.2 without considering the solution archive. This method will find the best solution within the swap neighborhood but there is no benefit from the solution archive. We have to re-evaluate already visited solutions within the LS. However, all generated solutions during the LS are inserted into the solution archive so that the variation operators of the GA are still guaranteed to produce only not yet considered solution candidates.

6.2 Reduced neighborhood

The second option is to skip already visited solutions in the neighborhood search. After each swap it is checked if the new solution is already contained in the solution archive. If this is the case the evaluation of this solution is skipped and the LS continues with the next swap. Otherwise this solution is inserted into the solution archive. The advantage of this method is that re-evaluations of already generated solutions are completely avoided and the neighborhoods are usually much smaller, resulting in a lower runtime. A downside is, however, that due to the reduced neighborhoods LS may terminate with worse solutions that are not local optimal anymore.

6.3 Conversion neighborhood

Another possibility for a combination of the local search and the solution archive is to perform a conversion whenever an already visited solution is generated by the local search. This implies that the size of this neighborhood is the same as the complete neighborhood but instead of re-evaluating duplicates, solutions that are farther away are considered to possibly find a better solution.

6.4 Tabu search

The fourth method we consider uses a tabu search instead of a local search where the tabu list is realized by the solution archive. This means in particular that the search is not stopped when a neighborhood does not contain a better solution but a best neighbor solution that has not been visited, even when worse than the current solution, is always accepted and the search continues. In this way, the algorithm might escape local optima. This strategy can be combined with either of the latter two methods. Unlike the LS, since there is no predefined end of the tabu search, an explicit termination criterion is needed, e.g., a time limit or a number of iterations without improvement. As final solution, the best one encountered during the whole tabu search is returned.

7 Multi-level solution evaluation scheme

In this section we want to exploit several relationships between the solution values of the different evaluation methods which are described in Sect. 4. Suppose that \(p^\mathrm {f}_{\mathrm {LP}}(x)\) is the objective value of the follower’s problem obtained by LP evaluation for a given leader solution \(x, p^\mathrm {f}_{\mathrm {exact}}(x)\) is the objective value obtained by exact (MIP-based) evaluation and \(p^\mathrm {f}_{\mathrm {greedy}}(x)\) is the objective value of the follower’s problem when using the greedy evaluation. Then \(p^\mathrm {f}_{\mathrm {LP}}(x)\) is obviously an upper bound and \(p^\mathrm {f}_{\mathrm {greedy}}(x)\) a lower bound to \(p^\mathrm {f}_{\mathrm {exact}}(x)\), i.e., the following relations hold:

$$\begin{aligned} p^\mathrm {f}_{\mathrm {greedy}}(x)\le p^\mathrm {f}_{\mathrm {exact}}(x)\le p^\mathrm {f}_{\mathrm {LP}}(x) \end{aligned}$$
(10)

Since we compute the turnover of the leader by subtracting the turnover of the follower from the total demand for all customers, i.e.,

$$\begin{aligned} p^\mathrm {l}_{\mathrm {LP}}(x)&= \sum _{j\in J}{w_j} - p^\mathrm {f}_{\mathrm {LP}}(x),\\ p^\mathrm {l}_{\mathrm {exact}}(x)&= \sum _{j\in J}{w_j} - p^\mathrm {f}_{\mathrm {exact}}(x),\\ p^\mathrm {l}_{\mathrm {greedy}}(x)&= \sum _{j\in J}{w_j} - p^\mathrm {f}_{\mathrm {greedy}}(x), \end{aligned}$$

we obtain:

$$\begin{aligned} p^\mathrm {l}_{\mathrm {LP}}(x)\le p^\mathrm {l}_{\mathrm {exact}}(x)\le p^\mathrm {l}_{\mathrm {greedy}}(x) \end{aligned}$$
(11)

7.1 Basic multi-level solution evaluation scheme

Based on inequalities (11) we devise a multi-level solution evaluation scheme. Suppose that \(p^\mathrm {l}_{\mathrm {LP}}(\hat{x})\) is the value of the leader’s turnover obtained by LP evaluation of the best solution found so far \(\hat{x}\). For each generated solution candidate \(x\) we evaluate it using greedy evaluation yielding a maximum achievable turnover of \(p^\mathrm {l}_\mathrm {greedy}(x)\). Then we distinguish two cases:

  • \(p^\mathrm {l}_\mathrm {greedy}(x)\le p^\mathrm {l}_{\mathrm {LP}}(\hat{x})\): This implies that \(p^l_\mathrm {exact}(x)\le p^l_\mathrm {exact}(\hat{x})\) and therefore \(x\) cannot be better than the so far best solution. So we do not put more effort in evaluating \(x\) more accurately.

  • \(p^\mathrm {l}_\mathrm {greedy}(x)> p^\mathrm {l}_{\mathrm {LP}}(\hat{x})\): We do not know if \(p^l_\mathrm {exact}(x)>p^l_\mathrm {exact}(\hat{x})\) and therefore have to evaluate \(x\) more accurately. We do this by performing a more accurate (i.e., LP or exact) evaluation after the initial greedy evaluation to get a better estimate of the quality of \(x\).

Preliminary tests showed that during an average run of our algorithm we can avoid the more accurate and thus more time-consuming solution evaluation for over 95 % of the solution candidates. Therefore it is likely that this method will reduce the overall optimization time of our algorithm in comparison to always performing an accurate evaluation. In Sect. 8.4 we will show that this multi-level solution evalution scheme is able to improve the results significantly in terms of running time and final solution quality.

7.2 Multi-level solution evaluation scheme and local search

For intermediate local search a modification of the multi-level evaluation scheme is needed. Suppose that \(\hat{x}\) is the so far best candidate solution with an objective value of \(p^\mathrm {l}_{\mathrm {LP}}(\hat{x})\) which is obtained by LP evaluation. Furthermore let \(x'\) be the starting solution of the local search which has an objective value of \(p^\mathrm {l}_{\mathrm {LP}}(x')\le p^\mathrm {l}_{\mathrm {LP}}(\hat{x})\) also obtained by LP evaluation. Then we encounter a problem if the objective value \(p^\mathrm {l}_{\mathrm {greedy}}(x)\) of a neighboring candidate solution \(x\), which initially is obtained by greedy evaluation lies between \(p^\mathrm {l}_{\mathrm {LP}}(x')\) and \(p^\mathrm {l}_{\mathrm {LP}}(\hat{x})\), i.e.,

$$\begin{aligned} p^\mathrm {l}_{\mathrm {LP}}(x') < p^\mathrm {l}_{\mathrm {greedy}}(x) \le p^\mathrm {l}_{\mathrm {LP}}(\hat{x}). \end{aligned}$$

Since \(p^\mathrm {l}_{\mathrm {greedy}}(x)\) is smaller than the best LP solution value found so far, \(x\) is not evaluated more accurately. It is, however, greater than the LP solution value of the starting solution of the LS so a move toward this solution is performed. This could lead to undesirable behavior because in fact we do not know if solution \(x\) is superior to solution \(x'\) and the LS would most likely perform moves towards a solution with a good greedy value instead of a solution with a good LP or exact value.

To avoid this problem we compare the solution value obtained by the initial greedy evaluation to the best LP solution value found so far in this local search call instead of the global best LP solution value for determining whether or not the solution shall be evaluated more accurately. This implies that in each iteration of the local search we start with a candidate solution that is evaluated using LP evaluation. This results in a local search towards the candidate solution with the best LP value at the cost of additional LP evaluations.

8 Computational results

In this section we present computational results of the developed methods. The instances used in all tests are partly taken from the benchmark library of Discrete Location Problems.Footnote 1 There are two types of instances: Euclidean, where the locations are chosen randomly on an Euclidean plane of size \(7{,}000\times 7{,}000\) and Uniform where all pairwise distances are chosen uniformly at random from the interval \([1,10000]\). Customer demands are randomly selected from 1 to 200 or set to 1 for all customers. They have in common that the customers and the possible facility locations are on the same sites (\(I=J\)), the number of customers is \(n=100\) and the number of facilities to be opened is \(r=p\in \{10,15,20\}\) for the Euclidean instances and \(r=p=\{7,25,30\}\) for the Uniform instances. In addition we generated larger Euclidean instancesFootnote 2 with \(150\) and \(200\) customers by using the same scheme. With a total of \(10\) instances per customer size and \(r=p=\{10,15,20\}\), the Euclidean test set consists of 90 instances. The Uniform test set only considers instances with \(100\) customers and contains 30 instances. All our tests were carried out on a single core of an Intel Xeon Quadcore with 2.53 GHz and 3GB RAM. The models for the solution evaluation are solved using the IBM ILOG CPLEX Optimizer in version 12.5.

If not stated otherwise, in all of the following tests we used the GA configuration from Sect. 5 with a population size of \(100\). Local search is performed for a solution whose objective value is within \(\alpha =5\,\%\) of the overall best solution’s value with the reduced swap neighborhood from Sect. 6 and a best improvement step function. After the algorithm terminates, the whole population is evaluated exactly to obtain the best feasible solution of the last population.

For all tables the following holds: Instances Code111 to Code1011 are the instances with \(n=100\) by Alekseeva et al. (2009) and instances Code123 to Code1023 are the uniform instances also with \(n=100\) by Davydov et al. (2014a). The other instance names contain either \(150\) or \(200\) which stands for the number of customers. The number right after rp corresponds to the number of facilities to place. In the first row the name of the algorithm is listed. The second row describes the columns, where \(\overline{ obj }\) stands for the average of the final leader objective value over \(30\) runs, \( sd \) is the corresponding standard deviation and \(t^*\) is the median time needed for finding the best solution in seconds. The highest (best) value for each instance out of the different configurations is marked in bold. All runs are terminated after \(600\) s to ensure comparability. First, we tested several configurations of the proposed algorithm on the Euclidean instances. Then, a comparison with different algorithms from the literature is presented. The results of computational tests on Uniform instances are described in Sect. 8.6. Due to space limitations Tables 1, 2, 3, 4, 5, 6 and 7 do not contain the numerical results of all of the 90 Euclidean instances but only a representative selection. The full result tables can be found online.\(^2\) In addition, the geometric mean, the number of best results and the number of unique best results are shown over all instances.

Table 1 Results of different solution evaluation methods using the standard configuration
Full size table
Table 2 Results of Wilcoxon rank sum tests with error levels of 5 % for the different solution evaluation methods
Full size table
Table 3 Results of different configurations for the GA: the pure genetic algorithm (GA), GA with local search (GA + LS), GA with solution archive (GA + solA) and GA with solution archive and local search (GA + LS + solA)
Full size table
Table 4 Results of Wilcoxon rank sum tests with error levels of 5 % for the different configurations of the GA
Full size table
Table 5 Results of using different neighborhood (NB) structures for intermediate local / tabu search (TS)
Full size table
Table 6 Results of Wilcoxon rank sum tests with error levels of 5 % for the different local search neighborhood structures and tabu search
Full size table
Table 7 Results for the multi-level evaluation scheme and the local/tabu search improvement compared to the standard LP solution evaluation
Full size table

In most of the following sections there is a second table after the main results table. These tables display the results of pairwise Wilcoxon rank sum tests of the different configurations with error levels of 5 %. The value in the cell at line \(i\) and row \(j\) gives the number of instances for which configuration \(i\) yields significantly better results than configuration \(j\). The rightmost column lists the sums over all numbers in the corresponding rows.

8.1 Solution evaluation on euclidean instances

In the following tests we compare three types of solution evaluation schemes according to Sect. 4: greedy evaluation, LP evaluation and exact evaluation. The aim of these tests is to find out which runtime/solution accuracy tradeoff is suitable for this problem.

Table 1 shows the results. As we can see, although each greedy evaluation is 4–5 times faster than the LP evaluation, the results for the greedy evaluation are rather poor because the solution with the highest greedy value often does not correspond to an optimal solution according to the exact evaluation. In contrast, the results for evaluating solutions using the LP evaluation are similiar to those obtained by using the exact evaluation. In many cases the root LP relaxation of the follower’s problem is already integral and no branching has to be performed, hence the similar results. Therefore, for the remaining tests we primarily use the LP evaluation method.

8.2 Genetic algorithm on Euclidean instances

Now, we analyze different configurations of the GA. The GA was tested with and without the local search and with and without the solution archive. The aim was to see the impact of using the different techniques on the average solution quality and speed. Table 3 shows the computational results. We can make several interesting observations: As expected, the GA alone performs not very well, neither regarding solution quality nor convergence speed, but its performance is substantially improved by executing intermediate local searches. By adding the solution archive (solA) to the pure GA we were also able to significantly improve the results. The benefit of the local search seems to be greater than the benefit of the solution archive because the relative difference of the geometric mean of GA + LS and the GA is about 5 % while the difference of GA + SA and GA is only about 0.7 %. Adding both, LS and solA, to the GA clearly further improves the performance. For this combined approval not only the solution quality is the best among the configurations but these solutions in most of the cases are also found faster.

8.3 Neighborhoods of the local search and tabu search on Euclidean instances

Table 5 shows the results of using the different strategies for utilizing the solA within LS and tabu search (TS), respectively (c.f. Sect. 6). As expected the complete neighborhood strategy performed worst because of the overhead of re-evaluating already visited solutions but on some of the smaller test instances it is able to produce equally good results. Among all tested LS neighborhoods, reduced neighborhood yields the best results, so it is chosen for all further tests. While on the smaller test instances with 100 customers the conversion and the complete neighborhood can keep up with the reduced neighborhood in terms of mean objective value, on larger instances the performance gap increases. The differences in the objective value of the conversion neighborhood and the reduced neighborhood are small and the conversion neighborhood even finds the best solution in less time for some instances, e.g., Code111w_rp10 and Code211w_rp10. However, this difference vanishes when considering larger instances, where the reduced neighborhood consistently finds better solutions. Apparently, for these instances conversion moves were too rarely able to improve the starting solution. The largest improvement of the overall results could be achieved by using a tabu search with the reduced neighborhood. In none of our benchmark instances any other configuration was able to find solutions with a statistical significant better mean objective value.

8.4 Multi-level evaluation scheme on Euclidean instances

The computational results for testing the multi-level evaluation scheme (ML-ES) confirms the hypothesis that it is able to speed up the algorithm significantly. We further tested if the local search using the local best LP solution (improved LS) as described in Sect. 7.2 actually improves the solution quality. Finally we investigated the tabu search approach (improved TS), which is explained in Sect. 6.4 in combination with the reduced NB. For the TS we also used the adaptation for the improved LS in a straightforward way and set a termination criterion of five iterations without improvement.

Table 7 shows the results of these tests. We observe that the multi-level evaluation scheme is able to improve the solution quality for some instances, especially the larger ones with 200 customers. The largest improvement could be made in the time needed for finding the best solution. It is in general much lower than when using only the simple LP evaluation, e.g., for instance Code111w_rp10 the time could be decreased by about 90 %. With the improved local search the mean solution quality gets better in 65 of the (mostly larger) instances, while it is equal on most of the other ones. Our best setup turned out to be GA + solA + ML-ES + improved TS, when we switched from a local search to a tabu search. We have a low standard deviation of the results and achieved a better mean objective value than the local search in 47 instances. The improvements are again mostly on the larger instances with 150 and 200 customers because, as we see in Sect. 8.5, we could find optimal solutions for many of the instances with 100 customers. In total, our best configurations of the multi-level evaluation scheme was able to produce statistically better results in 63 out of 90 instances (Table 8).

Table 8 Results of Wilcoxon rank sum tests with error levels of 5 % for the multi-level evaluation scheme configurations
Full size table

8.5 Comparison to results from the literature on Euclidean instances

In this section we compare the results of our best configuration to the state-of-the-art in the literature. Since the metaheuristic approaches of Alekseeva et al. (2010), Alekseeva and Kochetov (2013), and Davydov et al. (2014a) are the best heuristic approaches so far we compare with them. For this purpose both the probabilistic tabu search (\(\mathrm TS _\mathrm Al \)) (Alekseeva et al. 2010) and the hybrid memetic algorithm (\(\mathrm HMA \)) (Alekseeva and Kochetov 2013) were re-implemented in C++. Our re-implementations were verified to exhibit nearly equal performance as published in the respective original papers. The results of the STS are taken from Davydov et al. (2014a), where they presented the objective values of single runs (\(obj_1\)). Although they developed two metaheuristics here we only compare with STS because the other one, the VNS, performed worse on Euclidean instances.

Table 9 Comparison to results from the literature with a runtime of 600 s and \(n=100\)
Full size table
Table 10 Comparison to results from the literature with a runtime of 600 s and \(n=150\)
Full size table
Table 11 Comparison to results from the literature with a runtime of 600 s and \(n=200\)
Full size table
Table 12 Results of Wilcoxon rank sum tests with error levels of 5 % for the algorithms of the literature and the GA
Full size table

Table 9 shows the results of their approaches compared to our algorithm (GA + solA + ML-ES + imp. TS) with \(n=100\). Additionally, Tables 10 and 11 show the results of it compared to \(\mathrm {TS_{Al}}\) and HMA with \(n=150\) and \(n=200\). It can be seen that especially for larger instances our algorithm achieves the best results among all three tested algorithms (see Table 12). For the instances with 100 customers the algorithm described in this work gets better or equally good results than \(\mathrm {TS_{Al}}\) and HMA in all but one instances, although the differences in the mean objective value is rather small. Compared to STS both algorithms get better objective values on 3 instances and equally good solutions on the remaining 24 instances. However, the time needed to find these solutions is much lower for most instances when using our algorithm. The differences in the objective value become larger when considering larger instances. On all instances with \(n=200\) our algorithm obtains better results than \(\mathrm HMA \) and on 24 out of 30 instances it also gets better mean objective values than \(\mathrm TS _\mathrm Al \).

We observe that because of the time-consuming local searches in the creation of the initial population the HMA was not able to finish the initialization within the timelimit for some instances, so we made further tests with an increased timelimit of 1,800 s. The results of these tests can be found in Table 13 for \(n=100\) and Table 14 for \(n=150\) and \(n=200\). In Table 13 we also show the results of the modified iterative exact method (MEM) by Alekseeva and Kochetov (2013) and the results of the branch-and-cut by Roboredo and Pessoa (2013). For more than 100 customers no results of exact methods are published in the literature. From Table 13 we conclude that our algorithm is able to find optimal solutions to all but one instance, with \(n=100\) but in much less time than the exact algorithms. Tables 14 and 15 shows that the described approach is still superior and exceeds the HMA in most instances. The HMA can compete with the GA on some of the instances with \(n=150\) and even gets better mean objective values for 3 instances, e.g., Code5_150w_rp15. However, the differences are rather small and for \(n=200\) the GA is better in 28 out of 30 instances with a much lower standard deviation on most instances.

It is interesting that although our algorithm did not find the optimal solution for instance Code511 with \(r=p=15\) it always terminated with the same suboptimal solution. This is due to its solution evaluation method because even though the optimal value of the LP relaxation and the optimal value to the follower problem often coincide, it is not the case here. During our runs the algorithm might have visited the optimal solution but it was not able to identify it because its objective value is only approximated by the LP evaluation and was therefore discarded later.

Table 13 Comparison of the results from instances with \(n=100\) of the so far best exact methods MEM by Kochetov et al. (2013) and B&C by Roboredo and Pessoa (2013), the so far best heuristic methods HMA and STS by Alekseeva and Kochetov (2013) and Davydov et al. (2014a), respectively, and our GA \(+\) solA \(+\) ML-ES \(+\) imp
Full size table
Table 14 Comparison of the results from instances with \(n=150\) and \(n=200\) of HMA and our GA \(+\) solA \(+\) ML-ES \(+\) imp.TS with a runtime of 1,800 s
Full size table
Table 15 Results of Wilcoxon rank sum tests with error levels of 5 % for HMA and the GA with longer runtime for all 90 Euclidean test instances
Full size table

8.6 Uniform instances

Next, we tested our algorithm on the Uniform instances and compared the results with the VNS and STS by Davydov et al. (2014a), who tested their algorithms on a Pentium Intel Core Dual with 2.66 GHz. They published only the result of one single run (\(obj_1\)). Since we perform 30 runs, it is not straightforward to compare these approaches. Therefore we list for our algorithm the average objective value (\(\overline{obj}\)) and the objective value of the best run (\(obj^*\)).

When using the configuration that performed best in the Euclidean instances (GA + solA + ML-ES + imp. TS) we see in Table 16 that for the instances where \(r=p=7\) the algorithm quickly converges to a non-optimal solution. We observed that on Uniform instances the case occurs more frequently where a good LP value does not necessarily lead to a good (or optimal) solution. To further investigate this issue we modified the ML-ES to solve the follower’s problem exactly instead of only using the LP evaluation (GA + solA + ML-ES(EE) + imp. TS). Indeed, although the runtime increases, with this modification the GA was able to find the same solutions as STS for all but one instances with \(r=p=7\). Compared to the VNS, better solutions were found for five of ten instances but more time was required. STS performed excellent on these instances and was able to find equally good or better solutions in less time. However, the best of the 30 runs for GA + solA + ML-ES(EE) + imp. TS identifies a better or equally good solution for each instance.

When considering the instances where \(w_j=1,~\forall j\in J\) and \(r=p={25,30}\) the modification of ML-ES is apparently not beneficial because the runtime increases and the average objective value is often equal but sometimes even worse. The results in Table 16 confirm the observation of Davydov et al. (2014a) that when \(r\) and \(p\) increase at least for these instances the problem gets easier since GA + solA + ML-ES + imp. TS obtains equally good results as the VNS with a low standard deviation. For instances with \(r=p=25\) we observe the largest deviation of the objective values. While the results of the GA are often within 3 % of the VNS results in 9 out of 10 instances, they are generally worse and in one case it is equally good. However, also for these cases the best run for each instance found a solution that is equally good or better.

From these results we conclude that especially for the Uniform instances the search order of the neighborhoods is important to speed up the algorithm. It seems that it is often unnecessary to search through the whole swap neighborhood but to consider promising moves first. An interesting extension to the presented algorithm would be to incorporate the VNS into a hybrid GA, e.g., we could replace the swap neighborhood for the TS with the neighborhoods of the VNS. The combination of the strengths of both the special neighborhood structure of the VNS and STS with the hybrid GA could potentially lead to an algorithm that performs well on both Euclidean and Uniform instances.

Table 16 Comparison of results from Uniform instances of VNS and STS by Davydov et al. (2014a) with our algorithm GA \(+\) solA \(+\) ML-ES \(+\) imp. TS and our modification ML-ES(EE)
Full size table

8.7 Distribution of facilities

Finally, we want to investigate how solutions to the problem may look like and what properties they might have. Although we cannot make general statements that apply to all problem instances, we show in Fig. 3 the graphical representation of optimal solutions for one instance with 100 customers (Code311w) with different \(r\) and \(p\) values. The circles are customer locations, the filled points stand for locations chosen by the leader and the rectangles represent facilities of the follower. The size of the symbols depends on the demand of the corresponding location, i.e., the larger the symbol the higher the demand.

Fig. 3
figure 3

Optimal solutions for instance Code311w with different \(r\) and \(p\) values. a \(r=p=10\). b \(r=p=15\). c \(r=p=20\)

Full size image

In Fig. 3 it seems that the leader tends to choose locations that are more or less evenly spreaded across the whole region with a focus on the more crowded areas. The follower then appears to prefer locations in the vicinity of a leader’s facility. Another interesting observation is that while some locations are picked each time by the leader for different \(r\) and \(p\) values, some other locations are not always chosen. Visualizations on other instances reveal similar patterns, but as said before it is hard to draw precise general conclusions.

9 Conclusions

In this work we proposed a genetic algorithm for the discrete RPCP with several enhancements. First of all, a trie-based solution archive was used to reduce the number of unnecessary solution evaluations and to overcome premature convergence. This led to a significant efficiency gain. Another important part of the algorithm was the embedded local improvement procedure. Several ways of combining the local search with the solution archive were investigated, and the reduced neighborhood was identified to work best in practice. Different solution evaluation methods were considered and we found an effective way to combine them, which led to the multi-level evaluation scheme. Finally we improved the results of our algorithm by using a tabu search for local improvement.

Extensive tests showed that the performance on Euclidean instances is very good but for Uniform instances STS/VNS is better since they often obtain better results than our algorithm in average in less time. For many of the commonly used Euclidean instances GA + solA + ML-ES + improved TS is able to exceed previous state-of-the-art heuristic approaches and scales well to larger instances that cannot be solved with today’s exact methods anymore.

We considered here only one variant of a competitive facility location problem. For future work it would be interesting if our approach will also succeed when some problem parameters are changed, e.g., if the demand of the customers is proportional to the distance to the facilities or if it is inelastic. Further research also includes other applications of the solution archive, which is expected to improve the performance of algorithms for problems that have a compact solution representation and an expensive evaluation method. The tree structure of the solution archive might also be exploited further, e.g., by computing bounds on partial solution in order to cut off subspaces, that cannot contain better solutions.