46
47
relocation of facilities. In particular, the total cost incurred (l.h.s.), defined as sum of the closing costs 1∑ ∈j0 11 − 33 and the opening costs 1∑ ∈h0 3, has to be smaller than the maximum budget i available (r.h.s). Finally, constraints (2.47) define the nature of the introduced decision variables.
Wang et al. (2003) applied the model to tackle the real problem of locating/relocating bank branches in Amherst, New York.
In 2007, ReVelle et al. address the re-organization problem from another perspective. In this case, the motivations for modifying the current facilities configuration don't lie in the change of the distribution of the demand and, therefore, in the worsening of the service accessibility, but in some occurred financial circumstances that impose to contain costs and, then, to reduce the number of operating facilities. Consequently, any action is not aimed at improving the accessibility of users to the service, but, on the contrary, the perturbation of the previous demand allocation generally causes the wosening of the service quality offered to the users.
Suppose to have a set of facilities ∈ already located in a region (| | = ), that provide a given service to users ∈ . The decision-maker has to shrink the service by closing a pre-specified number of facilities ( < ). These actions will produce some side effects on the users. In particular, assuming that in the current configuration each user is allocated to its closest facility, the closure of the single facility imposes the re-allocation of its assigned demand to a farthest faciliity, with a consequent increase of costs and the worsening of the quality of the offered service. In order to take into account such damage on the users, ReVelle et al. introduced two parameters: a tolerance level l, expressed as maximum percentage of increasing of the current distance ̅ of each user from its assigned facility, over which user percieves the worsening of its condition and he can be considered damaged, and a standard distance n within which each user has necessarly to be covered.
Therefore, given that in the final configuration each user has to be covered within a standard distance n, the model aims at identifying the facilities to be closed in order to mnimize the number of damaged users, i.e. for which the distance from its closest facility increases more than l times from its current value ̅̅ .
Indicating with:
= a ∈ : ≤ (1 + l) ̅q bp the set of facilities that are distant from within l times the current distance q̅p to its closest facility;
48
S = a ∈ : ≤ nb the set of facilities that are able to cover user within the standard distance n;
binary variable equal to 1 if and only if user is in worse condition after the closure of the facilities;
binary variable equal to 1 if and only if facility is kept opened;
the Planned Shrinkage Model can be formulated as follows:
=
∈ (2.48)
≥ 1
∈^r ∀ ∈ (2.49)
≥ 1 −
∈sr ∀ ∈ (2.50)
=
∈ (2.51)
, ∈ "0,1# ∀ ∈ , ∈ (2.52)
The objective (2.48) minimizes the population that will be uncovered within a threshold level after the closing of facilities. Thus, the first group of constraints (2.49) guarantees that all the population will be covered within the distance standard n. The second group (2.50) accounts for population loss at node i if there is no facility within(1 + l) ̅ . The use of l allows for a range of nearest facilities to be modeled. If l = 0%, then the set will consist of the nearest facility to node or the nearest facilities if there is a tie. Alternatively, if l = 25%,, as an example, then the nearest set will consist of those facilities at most 25%
farther than the closest facility. Finally, constraint (2.51) sets the number of facilities to be kept opened.
Apart from the above formulation, suitable for services in the public sector, ReVelle et al.
(2007) formulated another version of the Planned Shrinkage Model, for dealing with facilities closure problems in the private sector. In particular, the model consider firms under situations of pressing financial needs that need to cede market share to competitors.
Recently models dealing with re-organization of existing facility systems have began to appear also in the field of districting problems. In this case, the problem consists of modifying the current partition of territorial units in districts, in order to satisfy some planning criteria (re-districting problem). In the final configuration the number of the districts, and hence the operating facilities, may be smaller, higher or equal to the current one. The extant literature
49
offers a good number of example of redistricting problems, most of which addressing electoral and political versions of the problem (for a complete survey, see Duque et al., 2007).
In the context of service-oriented application, motivations for re-districting lie in the changes in the distribution of the units attributes (i.e. service demand, population) that may result in a non balanced district map. The expansion of cities, people migration and uneven changes of service demand in somea areas are examples of forces that pressure the redefinition of districts Therefore, they generally have the aim of improving the quality of solution with reference to some planning criteria. For instance, Eagleson et al. (2002) develop a method for school redistricting; D’Amico et al. (2002) suggest an approach for dealing with police districts redesign.
Silva de Assis et al. (2014) were the first to propose a mathematical model to address the problem of reshaping districts for energy metering.
Suppose to have a set of territorial units already grouped in districts, where the binary label vw indicates if the unit is currently assigned to district x (x = 1. . ). Each territorial unit is associated with a set of attributes y and Uz is the value of attribute ∈ y associated to the generic unit ∈ . The target value for each district, with reference to the generic attribute is equal to {z = ∑ |r∈~d r}. Introducing the binary variables w, equal to 1 if and only if unit is assigned to district x, and w, equal to 1 if and only if both units and are assigned to district x, the model has been formulated as follows:
) = max, ∈ a wb
d wN)
(2.53)
- = |Uz w− {z|
∈ z∈•
d wN)
(2.54)
w ≤ w ∀ , ∈ , ∀x = 1. . (2.55)
w ≤ w ∀ , ∈ , ∀x = 1. . (2.56)
w ≥ w+ w− 1 ∀ , ∈ , ∀x = 1. . (2.57)
w = 1
d wN)
∀ ∈ (2.58)
vw(1 − w)
∈
≤ T
d wN)
(2.59)
w− w
∈‚
≥ 1 − |ƒ|
∈⋃…∈‡^…/‚
∀ƒ ⊂ , ∀x = 1. . (2.60)
w, w ∈ "0,1# ∀ , ∈ , ∀x = 1. . (2.61)
50
The first objective function (2.53) minimizes the sum of the greatest distances between pairs of units within the same district (compactness). The second objective function (2.54) minimizes the sum of deviations of district attributes values from the related target (balance).
Constraints (2.55-2.57) ensure that, for each pair of unit ( , ) ∈ and each x = 1. . , variable w is equal to 1 if and only if both units are assigned to the same district x.
Constraint (2.58) assure that each unit is assigned to a single district. Constraint (2.59) limits to T the number of units that can change district. Constraints (2.60) guarantee that all the units assigned to a district are connectd to each other. Indicated with S the set of territorial units adjacent to , the contiguity property is verified as the constraints impose that any subset of units ƒ ⊂ can be entirely assigned to to the same district x (∑∈‚ w = |ƒ|) if and only if in its neighborhood (⋃‰∈‚S‰/ƒ) there is at least another unit belonging to district x (∑∈⋃…∈‡^…/‚ w). Finally, constraints (2.61) define the nature of the above introduced decisions variables.
In order to solve the model, Silva de Assis et al. (2014) proposed a solution framework based on a greedy randomized adaptive search procedure and multicriteria scalarization techniques to approximate the Pareto frontier. The computational experiments show the effectiveness of the method for a set of randomly generated networks and for a real-world network extracted from the city of São Paulo.