Keywords

1 Introduction

A lot of economic situations are described with a help of mathematical models of discrete location problems. Often they are quite hard both from theoretical and practical points of view. Obtaining optimal solutions to such problems with the help of exact algorithms, including software packages, may require significant time and computer resources. In recent years, methods for the approximate solution of various applied problems have been actively developed. They include the local search algorithms [1]. In this article we develop Variable Neighborhood Search Approach for the location and design problem. Two versions of the algorithm proposed for the problem are under consideration. Some numerical experiments have been carried out on the test instances. For the analyses of the quality of obtained solutions, the upper bounds are used.

2 Problem Formulation

The new Company plans to locate its facilities (supermarkets), which differ from one another in design: size, range, etc. Clients of each point choose to use the facilities of Company or its competitors depending on their attractiveness and distance. The Company’s goal is to attract a maximum number of customers, i.e. to serve the largest share of total demand. This share for the Company is not fixed. It depends on where and what design options open up new enterprises and, as a result, whose markets will be chosen by customers. Therefore, it can be classified as a multivariant location problem.

For the first time this problem is described by Kraas, O. Berman, R. Aboolian in [3]. Let us write out the mathematical model according to [2]. Let R be the set of facility designs, \(r\in R.\) There are \(w_i\) customers at the point i of discrete set \(N=\{1,2,\ldots , n\}\). All customers have the same demand, so each item can be considered as one client with weight \(w_i\). The distance \(d_{ij}\) between the points i and j is measured, for example, in Euclidean metric or equals to the shortest distance in the corresponding graph. Let \(P\subseteq N\) be the set of potential facility locations. It is assumed that \(C\subset P\) is the set of pre-existing competitor facilities. The Company may open its markets in \(S=P\setminus C\) taking into account the budget B and the cost of opening \(c_{jr}\) facility \(j\in S\) with design \(r\in R\).

Such flexible choice of customers is represented in the gravity-type spatial interaction models. These models are known as the brand share models in the marketing literature [4]. According to these models the utility \(u_{ij}\) for a customer at point \(i\in N\) of a facility at location \(j\in S\) can be written as an exponential function.

Let \(x_{jr}=1\), if facility j is opened with design variant r and \(x_{jr}=0\) otherwise, \(j\in S, r\in R.\) To determine the usefulness \(u_{ij}\) of the facility \(j\in S\) for the customer \(i\in N\) the supplementary coefficients \(k_{ijr}\) are introduced: \(k_{ijr}=a_{jr}(d_{ij}+1)^{-\beta }.\) They depend on the sensitivity \(\beta \) of customers to distance to facility and attractiveness \(a_{jr}.\) These two parameters are used in the spatial interaction models. In practice to determine the measures of attractiveness of each facility survey of the population is conducted. The survey data are processed using regression analysis.

Utility \(u_{ij} = \sum _{r=1}^{R} {k_{ijr} x_{jr}}.\) The total utility for the customers in point \(i \in N\) from the facilities controlled by the competitors is \(U_{i}(C) = \sum _{j \in C} {u_{ij}}.\)

The demand function is

$$g(U_{i}) = 1 - \exp \bigg (-\lambda _{i} U_{i}\bigg ),$$

where \(\lambda _{i}\) is the characteristic of flexible demand in point \(i,\,\,\lambda _{i}>0;\) \(U_{i}\) is the total utility for a customer at \(i \in N\) from all open facilities:

$$U_{i} = \sum _{j \in S} {\sum _{r=1}^{R} {k_{ijr} x_{jr}}} + U_{i}(C)=U_{i}(S)+U_{i}(C).$$

The company’s total share of facility \(i \in N\):

$$MS_{i} = \frac{U_{i}(S)}{U_{i}(S) + U_{i}(C)} = \frac{\sum _{j \in S} \sum _{r=1}^{R} {k_{ijr} x_{jr}}}{\sum _{j \in S} {\sum _{r=1}^{R} {k_{ijr} x_{jr}}} + \sum _{j \in C} {u_{ij}}}. $$

Then the mathematical model looks like:

$$\begin{aligned} \max \sum _{i \in N} {w_{i}\cdot g(U_{i})\cdot MS_{i}}, \end{aligned}$$
(1)
$$\begin{aligned} \sum _{j \in S} {\sum _{r \in R} {c_{jr} x_{jr}}} \le B, \end{aligned}$$
(2)
$$\begin{aligned} \sum _{r \in R} {x_{jr}} \le 1, j\in S, \end{aligned}$$
(3)
$$\begin{aligned} x_{jr} \in \{0,1\}, \quad r \in R, j \in S. \end{aligned}$$
(4)

Based on above notation, the objective function (1) looks as follows:

$$\begin{aligned} \max \sum _{i\in N}\! w_{i}\bigg (\! 1-\exp \bigg (\! -\lambda _{i} \bigg (\!\sum _{j\in S}{\sum _{r=1}^{R}{k_{ijr}x_{jr}}} + U_{i}(C)\!\bigg )\!\bigg )\!\bigg )\cdot \end{aligned}$$
(5)
$$ \cdot \bigg (\frac{\sum _{j \in S} {\sum _{r=1}^{R}k_{ijr} x_{jr}}}{\sum _{j \in S} {\sum _{r=1}^{R} {k_{ijr} x_{jr}}} + \sum _{j \in C} {u_{ij}}}\bigg ).$$

The objective function (5) reflects the Company’s goal to maximize the share of customers demand. Inequality (2) takes into account the available budget. Condition (3) shows that for each facility only one variant of the design can be selected.

3 Upper Bounds

It is known that the location problem considered in this paper is NP-hard [5]. Sience the objective function (5) is non-linear, it is impossible to use the linear programming methods to solve problem (2)–(5). In this case, the calculation of estimates of the objective function becomes relevant. Below there is an observation for constructing the upper bound for (5) proposed by Yu. Kochetov.

Let us consider the objective function (1) of a location and design problem. When \(\lambda _i\) is close to 1, the multiplier of the objective function behaves as a constant:

$$ 1 - \exp \bigg (-\lambda _{i} \bigg (\sum _{j \in S} {\sum _{r \in R} {k_{ijr} x_{jr}}} + U_{i}(C)\bigg ) \bigg )\approx 1.$$

Then the initial problem is equivalent to the following one:

$$\begin{aligned} \max \sum _{i \in N} w_{i} \cdot \bigg (\frac{\sum _{j \in S} {\sum _{r \in R} {k_{ijr} x_{jr}}}}{\sum _{j \in S} {\sum _{r \in R} {k_{ijr} x_{jr}}} + U_{i}(C)}\bigg ), \end{aligned}$$
(6)
$$\begin{aligned} \displaystyle \sum _{j \in S} {\sum _{r \in R} {c_{jr} x_{jr}}} \le B, \end{aligned}$$
(7)
$$\begin{aligned} \displaystyle \sum _{r \in R} {x_{jr}} \le 1, \quad j \in S, \end{aligned}$$
(8)
$$\begin{aligned} x_{jr} \in \{0,1\}, \quad r \in R, j \in S. \end{aligned}$$
(9)

It can be reduced to a problem of mixed-integer linear programming. To do this, we represent the objective function (6) in the following way:

$$\begin{aligned} \max \sum _{i \in N} w_{i} \cdot \bigg (\frac{\sum _{j \in S} {\sum _{r \in R} {k_{ijr} x_{jr}}}}{\sum _{j \in S} {\sum _{r \in R} {k_{ijr} x_{jr}}} + U_{i}(C)}\bigg )= \\ =\sum _{i \in N} \sum _{j \in S} \sum _{r \in R} \frac{w_{i}k_{ijr} x_{jr}}{\sum _{j \in S} {\sum _{r \in R} {k_{ijr} x_{jr}}} + U_{i}(C)}= \sum _{i\in N} \sum _{j \in S} \sum _{r \in R} z_{ijr}, \end{aligned}$$

where

$$z_{ijr}=\frac{w_{i}k_{ijr} x_{jr}}{\sum _{j \in S} {\sum _{r \in R} {k_{ijr} x_{jr}}} + U_{i}(C)}, i\in N, j\in S, r\in R.$$

The nonlinear model (2)–(5) is reduced to the mixed-integer programming model by introducing service variables:

$$y_{i}=\frac{w_{i}}{\sum _{j \in S} {\sum _{r \in R} {k_{ijr} x_{jr}}} + U_{i}(C)}, i\in N.$$

Then \(z_{ijr}\) is given by the inequalities:

$$\begin{aligned} k_{ijr}y_i+m(x_{jr}-1)\le z_{ijr}\le k_{ijr}y_i,\nonumber \\ z_{ijr}\le x_{jr}w_i,\nonumber \\ \text{ where } \ \ m=\max \frac{w_i k_{ijr}}{U_{i}(C)}, i\in N, j\in S, r\in R. \end{aligned}$$
(10)

The following linear model is obtained:

$$\begin{aligned} \max \sum _{i\in N} \sum _{j \in S} \sum _{r \in R} z_{ijr}, \end{aligned}$$
(11)
$$\begin{aligned} k_{ijr}y_i+m(x_{ir}-1)\le z_{ijr}\le k_{ijr}y_i, i\in N, j\in S, r\in R, \end{aligned}$$
(12)
$$\begin{aligned} z_{ijr}\le x_{jr}w_i, i\in N, j\in S, r\in R, \end{aligned}$$
(13)
$$\begin{aligned} \sum _{r\in R}\sum _{j\in S}z_{ijr}+y_iU_{i}(C)=w_i, i\in N, \end{aligned}$$
(14)
$$\begin{aligned} \displaystyle \sum _{j \in S} {\sum _{r \in R} {c_{jr} x_{jr}}} \le B, \end{aligned}$$
(15)
$$\begin{aligned} x_{jr} \in \{0,1\}, \quad j \in S, r \in R. \end{aligned}$$
(16)

Condition (14) says that every customer spends the budget proportionally to the utility either from the Company’s facilities or from a competitor. Problem (11)–(16) can be solved exactly.

Note that the constant m in (10) may be selected in various ways. This will determine the accuracy of the upper bounds.

4 Variable Neighborhood Search Approach

The use of solver CoinBonmin [6] for location and design problem can calculate only a record but not the optimal solution even when CPU time \(t\rightarrow \infty \) [7]. Solving such problems requires a significant investment of time and computing resources. In this regard, one of the approaches to its solution is the use of approximate methods. In this paper we develop Variable Neighborhood Search approach [8, 9] for the considered problem. The frame of Variable Neighborhood Search algorithm (VNS) is the following [8].

Scheme of VNS algorithm

Initialization. Select a set of neighborhood structures \(N_k, k=1,\ldots ,k_{max},\) that will be used in the search; find an initial solution x; choose a stopping condition.

Repeat the following until the stopping condition is met:

(1) Set \(k:=1.\)

(2) Until \(k=k_{max},\) repeat the following steps:

(a) Shaking. Generate a point \(x\prime \) at random from the k-th neighborhood of \(x \ (x\prime \in N_k(x));\)

(b) Local search. Apply some local search method with \(x\prime \) as initial solution; denote the obtained local optimum by \(x\prime \prime \);

(c) Move or not. If this local optimum \(x\prime \prime \) is better than the best incumbent, move to \(x:=x\prime \prime ,\) and continue the search with \(N_1, k:=1;\) otherwise, set \(k:=k+1.\)

We propose a variant of VNS approach which is called the Relaxed Neighborhood Search Algorithm (RVNS). Unlike the basic VNS there is no step “Local search” in RVNS. The basic idea of VNS approach is to explore a set of predefined neighborhoods successively to provide a better solution. Therefore, an important step is the choice of neighborhoods set. Here the new types of neighborhoods are used for the algorithm [10]. They will be described below.

Let the vector \(z=(z_i)\) be such that \(z_i\) corresponds to facility i: \(z_i=r\) iff \(x_{ir}=1\). The feasible initial solution z is obtained using special deterministic procedure.

Neighborhood 1 (N1). Feasible solution \(z'\) is called neighboring for z if it can be obtained with the following moves:

  1. (a)

    choose one of the open facilities p with design variant \(z_p\) and close it;

  2. (b)

    select the facility q which is closed and has highest attractiveness; then open facility q with the design variant \(z_p\).

Neighborhood 2 (N2). Feasible solution \(z'\) is called neighboring for z if it can be obtained with the following operations:

  1. (a)

    choose one of the open facilities p with design variant \(z_p\) and reduce the number of design variant;

  2. (b)

    select the facility q and increase the number of design variant of it.

Neighborhood 3 (N3). Unlike Neighborhood 2 on the step b) select the facility q which is closed; then open the facility q with the design variant \(z_p\).

Lin-Kernighan neighborhood (LK) was applied as Neighborhood 4 [11].

5 Experimental Study

The validation of the VNS algorithm was conducted for the following data: the neighborhoods N1, N2, N3 and LK were used; the local descent was carried out with the help of the neighborhood Lin-Kernighan, it consists of 9 elements. RVNS algorithm uses neighborhoods N1, N2, LK; Lin-Kernighan neighborhood consists of 9 elements. The facilities p in the neighborhood N1, the facilities p, q in N2 and q in N3 were selected randomly. Number of restarts shaking trials without improvement is limited by 100 for both algorithms. Stopping criteria for VNS and RVNS was an exploration of neighborhoods without improvement of the solution.

Table 1. Best known solutions
Full size table

To study the algorithms a series of test instances similar to the real data of the applied problem has been constructed [2]. The test instances consist of two sets with Euclidean and arbitrary distances. They contain 96 instances for location of 60, 80, 100, 150, 200 and 300 facilities; 3 types of design variants are used, the budget of 3, 5, 7, 9 is limited; the demand parameter is \(\lambda _{i} = 1, i\in N\); the customer sensitivity to the distance is high (\(\beta =2\)).

The parameter m was calculated by formula (10) and \(m=\max w_i k_{ijr},\) \(i\in N,\) \(j\in S, r\in R.\) Therefore, the two values UB1 and UB2 for the upper bound were obtained respectively. It should be noted that UB1 coincides with UB2 for all tasks with arbitrary distances. For all tasks with Euclidean distances the UB2 is closer to optimal solution than UB1. It is interesting to note that deviation UB2 from UB1 increases with the dimensions of problems. Thus the maximal and average deviations are equal to 27.4 % and to 11.9 % for \(|N|=60,\) and they are equal to 1.09 % and to 0.56 % for \(|N|=300\) respectively.

Table 1 shows the values of the upper bounds (UB1, UB2), the best solutions are found by CoinBonmin solver built into GAMS [7] and by algorithms VNS and RVNS for tests with the largest dimension from sets with Euclidean and arbitrary distances.

Table 2 contains some information about minimal (min), average (av) and maximal (max) CPU time (in seconds) of the proposed algorithms for test problems using a PC Intel i5-2450M, 2.50 GHz, memory 4 GB.

The test instances with Euclidean distances proved to be difficult for the CoinBonmin solver. In particular the maximum CPU time for test instances with \(|N|=60\) was more than 63 h. In all instances with a dimension of 300 the CoinBonmin solver could not find a feasible solutions in 25 min. While maximal running time of the proposed algorithms does not exceed 25 min. In the remaining test instances algorithms have been compared to the upper bound and among themselves. In 5 test instances with Euclidean distances VNS algorithm improved the record values found by RVNS. The average deviation of the VNS from the upper bound UB2 was 12.1 % (RVNS 12.1 %). The average time of the VNS algorithm until the stopping criterion triggered was 181.35 s (RVNS 4.28 s).

Table 2. CPU Time (sec)
Full size table

In the test instances with arbitrary distances CoinBonmin found the records for all tasks. The average time until the stopping criterion triggered was 139.39 s (RVNS 4.69 sec.). During this time in 27 test instances with arbitrary distances VNS algorithm improved RVNS records. The average deviation from the upper bound obtained by VNS was 0.14 % (RVNS 0.7 %).

Analyzing the results we can say that in 15 test instances the records of VNS coincided with upper bounds in the test instances with arbitrary distances. Therefore we can conclude that the VNS algorithm found the optimal solutions for 15 test instances. In addition CoinBonmin has found 10 optimal solutions and RVNS has found 9 such solutions. Optimal solutions have not been obtained on the series with the Euclidean distance. The confidence interval for the probability of obtaining an optimum (the confidence level is 95 %) is between 0.56 and 0.94.

In general we can say that VNS obtains solutions closer to the optimum, while RVNS algorithm is faster in comparison with other considered algorithms.

6 Conclusion

In this paper we have developed two variants of algorithms based on the Variable Neighborhood Search approach for the location and design problem. New neighborhoods of a special type allowed us to find the optimal solutions. Computational experiment was carried out on a series of test examples based on real data. The ways of constructing upper bounds of the objective function have described. The proposed algorithms found new best known solutions or solutions with smaller relative error. Having in mind the complexity and size of the considered problem we can conclude that the computational times are rather good.

The obtained results indicate the usefulness of the Variable Neighborhood Search approach for solving the commercial-size problem.