The generalized discrete (r|p)‐centroid problem

• Published date: 01 January 2019
• Author: D.R. Santos‐Peñate,J.A. Moreno‐Pérez,C.M. Campos‐Rodríguez
• DOI: http://doi.org/10.1111/itor.12289
• Date: 01 January 2019

Intl. Trans. in Op. Res. 26 (2019) 340–363

DOI: 10.1111/itor.12289

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

The generalized discrete (r|p)-centroid problem

D.R. Santos-Pe˜

natea, C.M. Campos-Rodr´

ıguezband J.A. Moreno-P´

erezb

aInstituto Universitario de Turismo y DesarrolloEcon ´

omico Sostenible, Universidad de Las Palmas de G.C.,

35017 Las Palmas de Gran Canaria, Spain

bInstituto Universitario de Desarrollo Regional, Universidad de La Laguna, 38271 La Laguna, Spain

E-mail: dr.santos@ulpgc.es [Santos-Pe˜

nate]; ccampos@ull.es [Campos-Rodr´

ıguez];

jamoreno@ull.es [Moreno-P´

erez]

Received 3 November2015; accepted 7 March 2016

Abstract

The (r|p)-centroid problem or leader–follower problem is generalized considering differentcustomer choice

rules where a customer may use facilities belonging to different firms, if the difference in travel distance (or

time) is small enough. Assuming essential goods, some particular customer choice rules are analyzed. Linear

programming formulations for the generalized (r|Xp)-medianoid and (r|p)-centroid problems are presented

and an exact solution approach is applied. Some computational examples are included.

Keywords: competitive location; bilevel problems; (r|p)-centroid; (r|Xp)-medianoid; leader–follower problem; linear

programming

1. Introduction

The (r|p)-centroid problem is a competitive location problem where two players, the leader and

follower, enter the market sequentially and compete in providing goods and services to customers.

The leader enters the market first with pfacilities and seeks to minimize the maximum market share

captured by a future competitor, called the follower. The follower opens rfacilities at the locations

that maximize its market share. We consider the case of essential goods, which means that demand

has to be satisfied, and so customers will visit at least one facility to obtain all the goods and services

they need. As demand is assumed to be essential, the objective of minimizing the maximum market

share the competitor can capture is equivalent to maximizing one’s own market share.

The customer choice rule represents the behavior of the customers. The binary rule represents

the “all or nothing” behavior, according to which a customer uses the closest facility, disregarding

any other facility that is more distant, even if the difference in terms of distance is very small. The

ties among the competing firms are solved by a sharing function. The binary choice rule assumes

that customers are sensitive to anydifference in distances to the facilities. Under the partially binary

choice rule, a customer visits the closest facility for both firms. In this case, a customer could visit

C

2016 The Authors.

International Transactionsin Operational Research C

2016 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

D.R. Santos-Pe˜

nate et al. / Intl. Trans. in Op.Res. 26 (2019) 340–363 341

a facility belonging to firm Aand pass over a closer facility belonging to firm Bbut not the closest

one to the customer. According to the proportional choice rule, a customer visits all the facilities

and the proportion of the demand captured depends on the travel distance. Binary, partially binary

and proportional rules, for essential and unessential demands, are studied in Hakimi (1990). Some

customer choice rules replace the hypersensitive consumer conduct implicit in the binary model by

a threshold-sensitive behavior; in this case, a customer only uses firm Aexclusively if the distance

from this customer to the competitors exceeds the distance to firm Aby an amount greater than

or equal to a threshold or “minimum sensibility” (Devletoglou, 1965; Devletoglou and Demetriou,

1967). An alternative to the binary and proportional rules is a threshold-sensitive choice rule, under

which the demand captured by each firm in the “doubtful zone” is givenby a nonincreasing function

of the travel distance, such as the decay functions used in the generalized coverage models (Berman

and Krass, 2002; Berman et al., 2003, 2010).

The (r|p)-centroid problem is a bilevel problem whose resolution, even for a moderate size,

requires significant computational effort. Some solution approaches can be found in the litera-

ture. An exact algorithm to find the locations that maximize the expected profit is presented in

Ghosh and Craig (1984). However, this approach consists basically of an enumeration of the fea-

sible solutions for the leader, and so this algorithm is not very useful. A tabu search algorithm is

proposed in Benati and Laporte (1994), and Davydov et al. (2014). In Campos Rodr´

ıguez et al.

(2010), the (r|p)-centroid is solved via an exact algorithm based on the evaluation of the score

(demand captured by the best locations for the follower) of a sequence of leader’s solutions con-

strained to a family of good follower’s solutions. During the process, the leader’s solutions with

a score higher than the current upper bound of the optimum are eliminated from the feasible

set. Another exact algorithm is presented in Alekseeva et al. (2010). In this case, an alternating

heuristic, used previously in Bhadury et al. (2003) to solve the centroid problem in the plane, is

applied to obtain initial solutions. At each iteration, the problem of the leader constrained to a

family of follower’s solutions is solved to obtain a lower bound of the optimum; then, for the

leader’s solution obtained, the problem of the follower is solved to obtain an upper bound. The

process ends when the best lower and upper bounds coincide. A branch-and-cut algorithm to solve

the (r|p)-centroid problem is proposed in Costa Roboredo and Alves Pessoa (2013). A variable

neighborhood search is used in Davydov et al. (2014). Other heuristic and exact methods to solve

the discrete (r|p)-centroid problem are described in Alekseeva and Kochetov (2013). Most of

the mentioned references consider the binary and essential scenario. Different scenarios are an-

alyzed in Biesinger et al. (2015a, 2015b), where the problem is solved by applying evolutionary

algorithms.

In this paper, we consider a general customer choice rule that incorporates the possibility of a

customer visiting both firms if the distances to the competing firms are not very different. This

generalized choice function includes the binary rule as a particular case. We use this general choice

function to define the generalized discrete (r|p)-centroid problem in the case of essential goods,

and analyze some particular decay functions. Linear programming formulations for both problems

(follower and leader) are given, and an exact procedure is applied.

The remainder of this paper is organized as follows. The model is introduced in Section 2

and an example is then described in Section 3. Integer programming formulations are presented

in Section 4. A solution approach is described in Section 5. Some computational examples are

presented in Section 6 and, finally, the main conclusions are summarized in Section 7.

C

2016 The Authors.

International Transactionsin Operational Research C

2016 International Federation of OperationalResearch Societies