Dynamic location problem under uncertainty with a regret‐based measure of robustness

• DOI: http://doi.org/10.1111/itor.12183
• Date: 01 July 2018
• Published date: 01 July 2018

Intl. Trans. in Op. Res. 25 (2018) 1361–1381

DOI: 10.1111/itor.12183

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Dynamic location problem under uncertainty with a

regret-based measure of robustness

Maria do C´

eu Marquesa,c and Joana Matos Diasb,c

aDFM, ISEC, Polytechnic Institute of Coimbra,Rua Pedro Nunes, 3030-199 Coimbra, Portugal

bFaculty of Economics, University of Coimbra, Avenue Dias da Silva, 165, 3004-512 Coimbra, Portugal

cInstitute for Systems Engineering and Computers at Coimbra (INESC Coimbra), University of Coimbra, Rua Antero

de Quental, 199, 3000-033 Coimbra, Portugal

E-mail: cmarques@isec.pt [Marques];joana@fe.uc.pt [Dias]

Received 23 May2014; received in revised form 8 May 2015; accepted 9 May 2015

Abstract

In this paper, we present a dynamic uncapacitated facility location problem that considers uncertainty in

fixed and assignment costs as well as in the sets of potential facility locations and possible customers.

Uncertainty is represented via a set of scenarios. Our aim is to minimize the expected total cost, explicitly

considering regret. Regret is understood as a measure, for each scenario, of the loss incurredfor not choosing

that scenario’s optimal solution if that scenario indeed occurred. We guarantee that the regret for each

scenario is always upper bounded. We present a mixed integer programming model for the problem and we

propose a solution approach based on Lagrangean relaxation integrating a local neighborhood search and

a subgradient algorithm to update Lagrangean multipliers. The problem and the solutions obtained are first

analyzed through the use of illustrativeexamples. Computational results over sets of randomly generatedtest

problems are also provided.

Keywords:dynamic location problems; uncertainty; scenarios; heuristics; Lagrangean relaxation

1. Introduction

The strategic nature of most location decision problems associated with the limited knowledge

about problem parameters at the time of decision making, makes facility location problems under

uncertainty an active area of research within the location research field. Models and solution

methods that deal explicitly with uncertainties are even more complex than deterministic versions

and with higher computational difficulties to achieve optimal or near-optimal solutions. During the

last decades there has been considerable interest in location problems under uncertainty and a large

volume of work is now available in specialized papers and monographs. Among the vast collection

of works concerning facility location problems under uncertainty, we can find static (single-period)

C

2015 The Authors.

International Transactionsin Operational Research C

2015 International Federation of OperationalResearch Societies

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

USA.

1362 M. C. Marques and J. M. Dias / Intl. Trans. in Op. Res. 25 (2018) 1361–1381

or dynamic (multiperiod) approaches. Within the first class, we can include the following works,

from earlier to most recent ones, reflecting the richness of the contributions to the field. We stress

that this brief review has no pretensions of completeness. Louveaux (1986) presents a stochastic

version of the classical uncapacitated facility location problem (UFLP) in which demands, variable

production and transportation costs, and selling prices (incorporated in the model) can be random.

The problem is formulated as a two-stage stochastic program, where the first-stage decisions are

the location and the size (capacity) of the facilities to be established, and the second-stage decisions

are the allocation of the available production to the most profitable demands. In that work also

a stochastic version of the p-median, defined as a two-stage stochastic program, is presented, and

relations between the stochastic versions of the p-median and the UFLP are discussed. Solution

methods are later presented by Louveaux and Peeters (1992). The authors propose a heuristic dual-

based procedure, inspired by the approach developed in Bilde and Krarup (1977) and Erlenkotter

(1978) for the classical (static and deterministic) UFLP. Laporte et al. (1994) consider a capacitated

facility location problem (CFLP) in which customer demands are stochastic. The problem consists

of optimally determining the location and size of facilities given that future customer demand is

uncertain. The objective function minimizes the difference between the sum of fixed facility costs

and average cost of operating transportation services between facilities and customers (assignment

costs), and the expected net revenue from supplying customers. The problem can also be viewed as

a two-stage stochastic integer program. Current et al. (1997) address location problems in which

the total number of facilities to be sited is uncertain. Two decision criteria are considered in

p-median-based formulations: the minimization of the maximum regret and the minimization of

expected opportunity loss. Under the decision criteria, each problem locates an initial number of

facilities when the total number is unknown. The approaches are illustrated with a sample problem.

Serra and Marianov (1998) consider a p-median-based model in which travel times between nodes

and/or demand at nodes are uncertain, described by scenarios. Two p-median formulations are

presented, the min–max and the regret approaches. The authors propose a heuristic method for

both formulations, and a real application to the location of fire stations in Barcelona is presented.

More recently, Berman and Drezner (2008) also consider the p-median problem when the total

number of facilities to be sited in the future is uncertain. The problem seeks the location for p

facilities that minimize the expected weighted distance when up to qnew facilities are added to the

system in the future. The probability of adding 0 ≤r≤qnew facilities (possible scenarios) is given.

Heuristic algorithms are suggested to solve the problem (focusing in the case q=1). A similar

integer programming model and a decomposition algorithm to solve it is presented by Sonmez and

Lim (2012). As opposed to the previous work, in this paper the problem allows the closing of some

of the facilities that were opened initially, due to future demand change, and considers also budget

restrictions for the opening and closing of facilities. Ravi and Sinha (2004) propose a two-stage

stochastic version of the UFLP and an 8-approximation algorithm to solve it. Here, demand and

fixed costs are both random, and facilities may be opened in either the first or second stage. A related

two-stage stochastic program is proposed by Wang et al. (2011) in which service installationcosts are

also considered (services must be installed at the open facilities and each customer must be assigned

to an open facility at which the service requested by the customer is installed). The authors propose

a primal-dual approximation algorithm to solve the optimization problem. Lin (2009) proposes

a stochastic version of the single-source CFLP in which the demand is uncertain. The objective

C

2015 The Authors.

International Transactionsin Operational Research C

2015 International Federation of OperationalResearch Societies