## 1 Introduction

*et al.*, 2002). The demand of these customers is fixed and currently satisfied by a set of facilities already established in that area belonging to one or several firms. When a new firm wants to enter this market with the idea of capturing as much demand as possible, the company is facing a problem of Competitive Location. The entering firm must decide where to locate its own facilities in order to maximize its total profit, which will depend on the total captured demand. This decision implies the study of the conditions that surround the distribution of a specific product, such as the location space, the characteristics of the facilities (quality), the customer choice rule, and additional constraints imposed by the firm, or by the local administration. The combination of all these factors will give rise to different competitive location models that will need a different study and the use of different techniques to solve them (see Eiselt

*et al.*, 1993, 2015; Friesz

*et al.*, 1988; Plastria, 2001; Revelle and Eiselt, 2005; Al-Yakoob and Sherali, 2018).

*binary*or

*deterministic*rule (the full demand of a customer is satisfied by only one facility, the one to which he is attracted most –

*binary attraction*), and the

*Huff*,

*probabilistic*or

*proportional*rule (a customer splits his demand over all facilities in the market proportionally with his attraction to each facility –

*additive attraction*), see Drezner and Drezner (2004), Serra

*et al.*(1999b). Although in many cases customers patronize facilities according to these two rules, there are others in which these rules do not represent customer behaviour properly. In this paper we are going to consider that customers follow the partially binary or multideterministic rule, where it is supposed that several firms are present in the market with some pre-existing facilities, and the full demand of a customer is served by all the firms but patronizing only one facility from each firm, the facility with the maximum attraction, then its demand is split between those facilities proportionally with their attraction (see Fernández

*et al.*, 2017; Hakimi, 1990; Suárez-Vega

*et al.*, 2004).

*et al.*, 2015).

*et al.*, 2003; Ljubić and Moreno, 2018; Serra

*et al.*, 1999a for minimum capture constrained models and Drezner

*et al.*, 2002; McGarvey and Cavalier, 2005; Plastria and Vanhaverbeke, 2008 for other constrained models).

*et al.*(2017), where unconstrained discrete competitive facility location models were analysed under binary and partially binary customer choice rules. There are some highlight differences between the previous paper and this new one that justify its relevance. In the previous one, none ties breaking rule was used if ties in maximum attraction occur for the new facilities, since this was irrelevant for the entering firm when its market share was going to be maximized. In this new one, we deal with a nonlinear constrained problem due to the use of the equity-based ties breaking rule when there are several new facilities with maximal attraction for a customer. In addition, and for each customer, it has been considered that a new facility will capture part of the consumer’s demand if the attraction between them exceeds a certain fixed threshold, so it may happen that there are customers with no captured demand by the new facilities.

*et al.*(2017).

## 2 Partially Binary Basic Model

*x*,

*x*being an integer value.

### 2.1 Notation

*Indices*

*Data*

*i*,

*j*,

*i*and facility

*j*considered by intervals of a fixed range,

*i*feels for facility

*j*,

*i*feels for facilities in

*J*,

*i*for a new facility,

*k*in the market area,

*L*

*Variables*

##### (1)

\[ {a_{ij}}=\left\{\begin{array}{l@{\hskip4.0pt}l}\frac{{q_{j}}}{f({d_{ij}})}\hspace{1em}& \text{if}\hspace{2.5pt}\frac{{q_{j}}}{f({d_{ij}})}\geqslant {A_{i}},\\ {} 0\hspace{1em}& \text{otherwise},\end{array}\right.\]*X*when partially binary customer choice rule is considered,

##### (2)

\[ \begin{aligned}{}& {x_{j}}=\left\{\begin{array}{l@{\hskip4.0pt}l}1\hspace{1em}& \text{if a new facility is located at}\hspace{2.5pt}j,\\ {} 0\hspace{1em}& \text{otherwise},\end{array}\right.\hspace{1em}j\in L,\\ {} & {y_{ij}}=\left\{\begin{array}{l@{\hskip4.0pt}l}1\hspace{1em}& \text{if}\hspace{2.5pt}i\hspace{2.5pt}\text{is allocated to}\hspace{2.5pt}j,\\ {} 0\hspace{1em}& \text{otherwise},\end{array}\right.\hspace{1em}i\in I,\hspace{2.5pt}j\in L\end{aligned}\]*i*is allocated to a new facility

*j*with maximum attraction, that is, ${a_{ij}}=\max \{{a_{ir}}:{x_{r}}=1,\hspace{0.1667em}r\in L\}$. In addition, as ${\textstyle\sum _{j\in L}}{y_{ij}}=1$, each

*i*will be allocated to only one new facility with maximum attraction, following the partially binary customer choice rule. Note that constraints ${y_{ij}}\in \{0,1\}$ can be replaced by ${y_{ij}}\geqslant 0$. At optimality, ${y_{ij}}$ may be positive only if ${a_{ij}}=\max \{{a_{ir}}:{x_{r}}=1,\hspace{0.1667em}r\in L\}$.

## 3 Partially Binary Constrained Model

*α*. With this new constraint, it is necessary to know what demand points are allocated to each new facility, and what part of the demand is captured by the entering firm. Given $i\in I$, it is known what proportion of its demand will be captured by the entering firm, the proportion corresponding to its maximum attraction (this could be zero), but it is possible that there exist several new facilities with non zero maximum attraction. Since the minimal market share constraints refer to the new facilities, not to the entering firm, it is very important to know exactly the captured demand by each new facility, and then it is crucial to know what breaking rule is going to be used in case of ties in the maximum attraction. In this paper, instead of selecting only one of them to serve the full demand, we assume a more realistic situation, so, if ties occur, the demand of each customer captured by the entering firm will be equally split among its open facilities with maximum attraction. Then, we consider the following new variables:

##### (4)

\[\begin{aligned}{}& \operatorname{Max}\sum \limits_{i\in I}{w_{i}}\frac{\frac{{\textstyle\sum _{j\in L}}{a_{ij}}{z_{ij}}}{{\textstyle\sum _{j\in L}}{z_{ij}}}}{\frac{{\textstyle\sum _{j\in L}}{a_{ij}}{z_{ij}}}{{\textstyle\sum _{j\in L}}{z_{ij}}}+{\textstyle\sum _{k\in K}}{a_{i}}({J_{k}})}\end{aligned}\]##### (7)

\[ \epsilon \hspace{0.1667em}{z_{ij}}+\bigg(\hspace{0.1667em}\sum \limits_{h\in L}{z_{ih}}{a_{ih}}-\bigg(\hspace{0.1667em}\sum \limits_{h\in L}{z_{ih}}\bigg){a_{ij}}\hspace{-0.1667em}\bigg)+|L|(1-{x_{j}}){a_{\max }}\geqslant \epsilon ,\hspace{1em}\forall i\in I,\hspace{2.5pt}\forall j\in L,\]*ϵ*is small enough and ${a_{\max }}=\operatorname{Max}\{{a_{ij}}:\forall i\in I,\hspace{0.1667em}\forall j\in L\}$.

##### (8)

\[\begin{aligned}{}& \sum \limits_{i\in I}{w_{i}}\frac{\frac{{a_{ij}}{z_{ij}}}{{\textstyle\sum _{j\in L}}{z_{ij}}}}{\frac{{\textstyle\sum _{j\in L}}{a_{ij}}{z_{ij}}}{{\textstyle\sum _{j\in L}}{z_{ij}}}+{\textstyle\sum _{k\in K}}{a_{i}}({J_{k}})}\geqslant \alpha {x_{j}},\hspace{1em}\forall j\in L\hspace{1em}\Leftrightarrow \end{aligned}\]### 3.1 Linearization of the Constrained Model

*et al.*, 2016; Fernández

*et al.*, 2017; Haase and Muller, 2014; Kochetov

*et al.*, 2013 for similar linearizations):

##### (10)

\[ \begin{aligned}{}& {q_{i}}=\frac{1}{{\textstyle\sum _{j\in L}}{a_{ij}}{z_{ij}}+({\textstyle\sum _{k\in K}}{a_{i}}({J_{k}})){\textstyle\sum _{j\in L}}{z_{ij}}},\hspace{1em}\forall i\in I,\\ {} & {v_{ij}}={q_{i}}{z_{ij}},\hspace{1em}\forall i\in I,\hspace{2.5pt}\forall j\in L,\end{aligned}\]## 4 Ranking-Based Random Search

*et al.*(2017). The RDOA is specially adopted to discrete facility location and is based on ranking of candidate locations. The algorithm demonstrated good efficiency when solving different instances of unconstrained discrete facility location problems and outperformed well-known algorithms suitable to solve similar problems.

### 4.1 Ranking-Based Constrained Discrete Optimization Algorithm

*L*and is considered as the best solution found so far. Here

*s*is the number of facilities expected to locate. The initial solution can be generated at random or obtained by other optimization methods, but must be feasible according to the problem constraints.

*Y*and changing them to another ones randomly selected from the set of all possible candidate locations excluding those which already form

*Y*or ${Y^{\prime }}$. Each location ${y_{k}}$ is changed to probability $1/s$, and is copied without changing to probability $1-1/s$:

##### (13)

\[ {y^{\prime }_{k}}=\left\{\begin{array}{l@{\hskip4.0pt}l}l\in L\setminus (Y\cup {Y^{\prime }}),\hspace{1em}& \text{if}\hspace{2.5pt}{\xi _{k}}<1/s,\\ {} {y_{k}},\hspace{1em}& \text{otherwise},\end{array}\right.\]*l*is randomly selected among the location candidates not already included in $Y\cup {Y^{\prime }}$ using a roulette wheel strategy.

##### (14)

\[ {\pi _{i}}=\frac{{r_{i}}}{d({l_{i}},{y_{k}}){\textstyle\textstyle\sum _{j=1}^{|L|}}\frac{{r_{j}}}{d({l_{j}},{y_{k}})}},\]*Y*, but do not form ${Y^{\prime }}$, are reduced by one:

##### (15)

\[ {r_{i}}=\left\{\begin{array}{l@{\hskip4.0pt}l}{r_{i}}+1,\hspace{1em}& \text{if}\hspace{2.5pt}{l_{i}}\in {Y^{\prime }},\\ {} {r_{i}}-1,\hspace{1em}& \text{if}\hspace{2.5pt}{l_{i}}\in Y\setminus {Y^{\prime }},\\ {} {r_{i}},\hspace{1em}& \text{otherwise}.\end{array}\right.\]*Y*, are reduced by one:

*Y*is changed to ${Y^{\prime }}$ and iteration is assumed to be successful; otherwise,

*Y*remains unchanged and iteration is assumed to be unsuccessful.

### 4.2 Pre-Optimization Stage

*Y*used to generate new ones must be feasible. However, finding a feasible solution can be a non-trivial task, requiring significant computational effort.

*α*of the market share. Otherwise the solution is treated as infeasible and cannot be considered as a candidate solution for the problem. Let’s denote by ${m_{1}},{m_{2}},\dots ,{m_{s}}$ the market share captured by facilities located in ${y_{i}}\in Y$. Then violation of the minimal market share constraint of facility located in ${y_{i}}$ is expressed by market share deficiency:

##### (17)

\[ {v_{i}}=\left\{\begin{array}{l@{\hskip4.0pt}l}\alpha -{m_{i}},\hspace{1em}& \text{if}\hspace{2.5pt}{m_{i}}<\alpha ,\\ {} 0,\hspace{1em}& \text{otherwise},\end{array}\right.\]*Y*is Equation (17) guarantees that (18) is a sum of non-negative values. Thus makes $V(Y)$ a non-negative function with zero lower bound, which indicates that solution

*Y*is feasible; larger $V(Y)$ indicates larger violation of the constraint.

*Y*using the same strategy as in RDOA – the algorithm for unconstrained optimization. The ranking of candidate locations is also performed using similar strategy as in RDOA: if $V({Y^{\prime }})$ is lower than $V(Y)$, then ranks of the candidate locations forming ${Y^{\prime }}$ are increased by one and ranks of the candidate locations in $Y\setminus {Y^{\prime }}$ are reduced by one; similarly, if $V({Y^{\prime }})$ is not lower than $V(Y)$, then ranks of the candidate locations in ${Y^{\prime }}\setminus Y$ are reduced by one.

*Y*such that $V(Y)=0$ cannot be found using a predefined number of function evaluations or within a reasonable time devoted to solve the whole optimization problem, then it is stated that a feasible solution cannot be found. The complexity of the pre-optimization stage, depends on the optimization problem instance and will be investigated hereinafter.

## 5 Experimental Investigation

*L*(see Fig. 1).

##### Table 1

Firm | Indices of demand points | |

3 facilities per firm | 5 facilities per firm | |

${J_{1}}$ | 1, 4, 7 | 1, 4, 7, 10, 13 |

${J_{2}}$ | 2, 5, 8 | 2, 5, 8, 11, 14 |

${J_{3}}$ | 3, 6, 9 | 3, 6, 9, 12, 15 |

*I*. Then the minimal market share is considered as 0% to 80% of $\tilde{m}$, depending on the problem instance, but only the results for some of them will be shown, the ones with significative information for the model. For small

*α*values, Xpress is able to find the optimal solutions, which do not usually change, and only when

*α*values increase, the optimal solutions can change, if any, and it is even possible that Xpress can not find them because of the time limit. The values of minimal market share

*α*are presented in Table 2, knowing that the total demand

*W*of

*I*is 35462869.

##### Table 2

*α*) for different $({\text{PBCM}_{\alpha }})$ instances.

$(|{J_{k}}|,s)$ | 0% | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% |

$(3,5)$ | 0 | 253310 | 506620 | 759930 | 1013240 | 1266550 | 1519860 | 1773170 | 2026480 |

$(3,10)$ | 0 | 186650 | 373300 | 559950 | 746600 | 933250 | 1119900 | 1306550 | 1493200 |

$(5,5)$ | 0 | 177310 | 354620 | 531930 | 709240 | 886550 | 1063860 | 1241170 | 1418480 |

$(5,10)$ | 0 | 141850 | 283700 | 425550 | 567400 | 709250 | 851100 | 992950 | 1134800 |

*i*, we consider ${A_{i}^{\max }}=\max \{{a_{i}}({J_{k}}):k\in K\}$ and ${A_{i}^{\min }}=\min \{{a_{i}}({J_{k}}):k\in K\}$, then ${A_{i}}={A_{i}^{\min }}+\delta ({A_{i}^{\max }}-{A_{i}^{\min }})$ with $0\leqslant \delta \leqslant 1$. Four

*δ*values have been selected for the result tables, $\delta =0,0.2,0.6,1$, in order to reduce the table size.

### 5.1 Validation of RCDOA

*s*), the minimal market share

*α*and

*δ*values were solved using Xpress and RCDOA. The computations with Xpress have been executed until the whole search space was explored or the predefined time limit was exceeded (18000 s). The RCDOA has been executed for 10000 function evaluations. Due to stochastic nature of RCDOA, each problem instance was solved 100 times to get statistically significant results.

*α*(%) = 0, 30, 60, 70 and 80, since only for large

*α*values Xpress has problems to obtain the optimal solutions. The acronym UNF in the table means that Xpress was unable to complete computation within the predefined time limit (unfinished). The acronym FNF stands for Feasible Not Found and means that an algorithm was unable to find a feasible solution – within a predefined time with Xpress and within 10000 function evaluations with RCDOA.

##### Table 3

$(|{J_{k}}|,s)$ | δ |
α (%) |
$M(Y)$ | $(|{J_{k}}|,s)$ | δ |
α (%) |
$M(Y)$ | ||

XPress | RDOA | XPress | RDOA | ||||||

$(3,5)$ | 0 | 0 | 12819396 | 12819396 | $(5,5)$ | 0 | 0 | 10936974 | 10936974 |

30 | 12819396 | 12819396 | 30 | 10936974 | 10936974 | ||||

60 | 12819396 | 12819396 | 60 | 10936974 | 10936974 | ||||

70 | 12819396 | 12819396 | 70 | 10936974 | 10936974 | ||||

80 | UNF | FNF | 80 | UNF | FNF | ||||

0.2 | 0 | 12342550 | 12342550 | 0.2 | 0 | 10150267 | 10150267 | ||

30 | 12342550 | 12342550 | 30 | 10150267 | 10150267 | ||||

60 | 12342550 | 12342550 | 60 | 10150267 | 10150267 | ||||

70 | UNF | FNF | 70 | 10026202 | 10026202 | ||||

80 | UNF | FNF | 80 | UNF | FNF | ||||

0.6 | 0 | 11579618 | 11579618 | 0.6 | 0 | 9552229 | 9552229 | ||

30 | 11579618 | 11579618 | 30 | 9552229 | 9552229 | ||||

60 | 11579618 | 11579618 | 60 | 9552229 | 9552229 | ||||

70 | UNF | FNF | 70 | 8679257 | 8679257 | ||||

80 | FNF | FNF | 80 | FNF | FNF | ||||

1 | 0 | 11177870 | 11177870 | 1 | 0 | 9040555 | 9040555 | ||

30 | 11177870 | 11177870 | 30 | 9040555 | 9040555 | ||||

60 | UNF | FNF | 60 | 8435659 | 8435659 | ||||

70 | FNF | FNF | 70 | FNF | FNF | ||||

80 | FNF | FNF | 80 | FNF | FNF | ||||

$(3,10)$ | 0 | 0 | 16128566 | 16128566 | $(5,10)$ | 0 | 0 | 14110653 | 14110653 |

30 | 16128566 | 16128566 | 30 | 14110653 | 14110653 | ||||

60 | UNF | FNF | 60 | UNF | FNF | ||||

70 | UNF | FNF | 70 | UNF | FNF | ||||

80 | UNF | FNF | 80 | UNF | FNF | ||||

0.2 | 0 | 16122297 | 16122297 | 0.2 | 0 | 13969654 | 13969654 | ||

30 | 16122297 | 16122297 | 30 | 13969654 | 13969654 | ||||

60 | UNF | FNF | 60 | UNF | FNF | ||||

70 | UNF | FNF | 70 | 13595768 | 13595768 | ||||

80 | FNF | FNF | 80 | UNF | FNF | ||||

0.6 | 0 | 15995766 | 15995766 | 0.6 | 0 | 13429857 | 13429857 | ||

30 | 15995766 | 15995766 | 30 | 13429857 | 13429857 | ||||

60 | 15784480 | 15784480 | 60 | UNF | FNF | ||||

70 | UNF | FNF | 70 | UNF | FNF | ||||

80 | FNF | FNF | 80 | FNF | FNF | ||||

1 | 0 | 15887608 | 15887608 | 1 | 0 | 12978556 | 12978556 | ||

30 | 15887608 | 15887608 | 30 | 12978556 | 12978556 | ||||

60 | 15489291 | 15489291 | 60 | 11925893 | 11925893 | ||||

70 | FNF | FNF | 70 | FNF | FNF | ||||

80 | FNF | FNF | 80 | FNF | FNF |

##### Table 4

$(|{J_{k}}|,s)$ | δ |
α (%) |
$M(Y)$ | $(|{J_{k}}|,s)$ | δ |
α (%) |
$M(Y)$ | ||

XPress | RDOA | XPress | RDOA | ||||||

$(3,5)$ | 0 | 0 | 12862282 | 12862282 | $(5,5)$ | 0 | 0 | 11043517 | 11043517 |

30 | 12862282 | 12862282 | 30 | 11043517 | 11043517 | ||||

60 | 12862282 | 12862282 | 60 | 11043517 | 11043517 | ||||

70 | 12862282 | 12862282 | 70 | 11043517 | 11043517 | ||||

80 | UNF | FNF | 80 | UNF | FNF | ||||

0.2 | 0 | 12406408 | 12406408 | 0.2 | 0 | 10356344 | 10356344 | ||

30 | 12406408 | 12406408 | 30 | 10356344 | 10356344 | ||||

60 | 12406408 | 12406408 | 60 | 10356344 | 10356344 | ||||

70 | UNF | FNF | 70 | 10254115 | 10254115 | ||||

80 | UNF | FNF | 80 | UNF | FNF | ||||

0.6 | 0 | 11645211 | 11645211 | 0.6 | 0 | 9746979 | 9746979 | ||

30 | 11645211 | 11645211 | 30 | 9746979 | 9746979 | ||||

60 | 11645211 | 11645211 | 60 | 9746979 | 9746979 | ||||

70 | UNF | FNF | 70 | 9018939 | 9018939 | ||||

80 | FNF | FNF | 80 | FNF | FNF | ||||

1 | 0 | 11212067 | 11212067 | 1 | 0 | 9272288 | 9272288 | ||

30 | 11212067 | 11212067 | 30 | 9272288 | 9272288 | ||||

60 | FNF | FNF | 60 | 9272288 | 9272288 | ||||

70 | FNF | FNF | 70 | 7936323 | 7936323 | ||||

80 | FNF | FNF | 80 | FNF | FNF | ||||

$(3,10)$ | 0 | 0 | 16266416 | 16266416 | $(5,10)$ | 0 | 0 | 14291976 | 14291976 |

30 | 16266416 | 16266416 | 30 | 14291976 | 14291976 | ||||

60 | UNF | FNF | 60 | UNF | FNF | ||||

70 | UNF | FNF | 70 | 14210030 | 14210030 | ||||

80 | UNF | FNF | 80 | UNF | FNF | ||||

0.2 | 0 | 16224017 | 16224017 | 0.2 | 0 | 14185476 | 14185476 | ||

30 | 16224017 | 16224017 | 30 | 14185476 | 14185476 | ||||

60 | UNF | FNF | 60 | 14050852 | 14050852 | ||||

70 | UNF | FNF | 70 | 14050852 | 14050852 | ||||

80 | UNF | FNF | 80 | FNF | FNF | ||||

0.6 | 0 | 16040410 | 16040410 | 0.6 | 0 | 13643691 | 13643691 | ||

30 | 16040410 | 16040410 | 30 | 13643691 | 13643691 | ||||

60 | 15950660 | 15950660 | 60 | 13310686 | 13310686 | ||||

70 | UNF | FNF | 70 | UNF | FNF | ||||

80 | FNF | FNF | 80 | FNF | FNF | ||||

1 | 0 | 15938689 | 15938689 | 1 | 0 | 13259531 | 13259531 | ||

30 | 15938689 | 15938689 | 30 | 13259531 | 13259531 | ||||

60 | 15668471 | 15668471 | 60 | FNF | FNF | ||||

70 | FNF | FNF | 70 | FNF | FNF | ||||

80 | FNF | FNF | 80 | FNF | FNF |

*δ*values increase. In general, times increase when

*α*or

*δ*increase and the rest of the parameters are fixed. When

*δ*increases, the minimum level of attraction for customers increases, and it is possible that instances that were feasible become infeasible because of the decreasing in the number of demand points that each facility can capture. If

*α*and/or

*δ*increase too much, the instances can be infeasible. Meanwhile, RCDOA performs its 10000 function evaluations within less than a half minute independent of the instance.

##### Table 5

$(|{J_{k}}|,s)$ | δ |
α |
$M(Y)$ | FNF | FFA | ||

Avg | Min | Max | |||||

$(5,5)$ | 0 | 0 | 10943317 | 10936974 | 10950470 | 0 | 1 |

30 | 10942777 | 10936974 | 10950470 | 0 | 3 | ||

60 | 10941666 | 10758392 | 10950470 | 0 | 61 | ||

70 | 10940315 | 10744730 | 10950470 | 0 | 321 | ||

80 | 7379300 | 7150127 | 9862744 | 96 | 580 | ||

0.2 | 0 | 10146666 | 9995868 | 10167048 | 0 | 1 | |

30 | 10146520 | 10008293 | 10167048 | 0 | 4 | ||

60 | 10143395 | 9978345 | 10167048 | 0 | 311 | ||

70 | 9932472 | 7879719 | 10044660 | 43 | 1939 | ||

80 | N/A | N/A | N/A | 100 | N/A | ||

0 | 9526613 | 9259547 | 9552229 | 0 | 1 | ||

30 | 9535052 | 9410487 | 9552229 | 0 | 15 | ||

0.6 | 60 | 9450394 | 5837770 | 9552229 | 2 | 1716 | |

70 | 8637104 | 6888141 | 8726454 | 67 | 2723 | ||

80 | N/A | N/A | N/A | 100 | N/A | ||

$(5,10)$ | 0 | 0 | 14076637 | 13936239 | 14128881 | 0 | 1 |

30 | 14071104 | 13930319 | 14128881 | 0 | 12 | ||

60 | 13454097 | 8845844 | 13751062 | 3 | 883 | ||

70 | 12915529 | 10160219 | 13751062 | 19 | 1685 | ||

80 | N/A | N/A | N/A | 100 | N/A | ||

0.2 | 0 | 13910487 | 13797369 | 13987882 | 0 | 1 | |

30 | 13918547 | 13702294 | 13987882 | 0 | 16 | ||

60 | 12801503 | 9333460 | 13607286 | 2 | 860 | ||

70 | 13229673 | 12115228 | 13605241 | 77 | 2518 | ||

80 | N/A | N/A | N/A | 100 | N/A | ||

0.6 | 0 | 13393572 | 13265791 | 13448805 | 0 | 1 | |

30 | 13393438 | 13180237 | 13448805 | 0 | 33 | ||

60 | 12264524 | 12168197 | 12316132 | 93 | 3603 | ||

70 | N/A | N/A | N/A | 100 | N/A | ||

80 | N/A | N/A | N/A | 100 | N/A |

*δ*and

*α*values can be seen on Tables 3 and 4. Although, solutions found by RCDOA only are not proven to be optimal, their objective values are similar to the optimal ones found by Xpress when solving similar problem instances.

### 5.2 Investigation of RCDOA

*α*values required more than 1000 function evaluations to determine a feasible solution. A feasible solution was not found for instances with larger constraint for the minimal market share ($\alpha =80\% $ in most cases and $\alpha =70\% $ for one instance), except the instance with $|{J_{k}}|=5$, $s=5$, and $\delta =0$ where a feasible solution was found even using the largest constraint.

*δ*and

*α*: larger values – smaller probability. On the other hand, it is probability equal to 1 to find approximation with 5% error for most problem instances, except for 7 instances, where probability was lower, and instances where feasible solution was not found at all.

##### Table 6

$(|{J_{k}}|,s)$ | δ |
α |
Probability to find the best known solution | |||||

0% | 1% | 2% | 3% | 4% | 5% | |||

$(5,5)$ | 0 | 0 | 0.47 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 |

30 | 0.43 | 1.00 | 1.00 | 1.00 | 1.00 | 1.00 | ||

60 | 0.48 | 0.99 | 1.00 | 1.00 | 1.00 | 1.00 | ||

70 | 0.39 | 0.99 | 1.00 | 1.00 | 1.00 | 1.00 | ||

80 | 0.25 | 0.75 | 1.00 | 1.00 | 1.00 | 1.00 | ||

0.2 | 0 | 0.15 | 0.98 | 1.00 | 1.00 | 1.00 | 1.00 | |

30 | 0.12 | 0.97 | 1.00 | 1.00 | 1.00 | 1.00 | ||

60 | 0.12 | 0.96 | 1.00 | 1.00 | 1.00 | 1.00 | ||

70 | 0.40 | 0.89 | 0.89 | 0.89 | 0.90 | 0.89 | ||

80 | N/A | N/A | N/A | N/A | N/A | N/A | ||

0.6 | 0 | 0.14 | 0.96 | 0.97 | 0.97 | 1.00 | 1.00 | |

30 | 0.18 | 0.99 | 1.00 | 1.00 | 1.00 | 1.00 | ||

60 | 0.19 | 0.98 | 0.98 | 0.98 | 1.00 | 0.98 | ||

70 | 0.21 | 0.97 | 0.97 | 0.97 | 1.00 | 0.97 | ||

80 | N/A | N/A | N/A | N/A | N/A | N/A | ||

$(5,10)$ | 0 | 0 | 0.06 | 0.97 | 1.00 | 1.00 | 1.00 | 1.00 |

30 | 0.06 | 0.93 | 1.00 | 1.00 | 1.00 | 1.00 | ||

60 | 0.04 | 0.76 | 0.89 | 0.91 | 0.90 | 0.95 | ||

70 | 0.01 | 0.69 | 0.72 | 0.73 | 0.80 | 0.88 | ||

80 | N/A | N/A | N/A | N/A | N/A | N/A | ||

0.2 | 0 | 0.01 | 0.88 | 1.00 | 1.00 | 1.00 | 1.00 | |

30 | 0.02 | 0.92 | 0.99 | 1.00 | 1.00 | 1.00 | ||

60 | 0.01 | 0.54 | 0.64 | 0.65 | 0.70 | 0.66 | ||

70 | 0.04 | 0.52 | 0.61 | 0.61 | 0.60 | 0.61 | ||

80 | N/A | N/A | N/A | N/A | N/A | N/A | ||

0.6 | 0 | 0.06 | 0.89 | 1.00 | 1.00 | 1.00 | 1.00 | |

30 | 0.01 | 0.89 | 1.00 | 1.00 | 1.00 | 1.00 | ||

60 | 0.14 | 0.86 | 1.00 | 1.00 | 1.00 | 1.00 | ||

70 | N/A | N/A | N/A | N/A | N/A | N/A | ||

80 | N/A | N/A | N/A | N/A | N/A | N/A |