Production, Manufacturing and LogisticsA location–allocation heuristic for the capacitated multi-facility Weber problem with probabilistic customer locations☆
Introduction
Given the locations of n customers and their demands, the multi-facility Weber problem (MFWP) is concerned with locating m uncapacitated facilities in the Euclidean plane and allocating them to the customers in order to satisfy their demand at minimum total cost. It is also known as the multi-source Weber problem (Brimberg et al., 2000). The objective function of the MFWP is neither convex nor concave (Cooper, 1967), which makes it hard to solve exactly. It becomes the so-called single-facility Weber problem if the objective is the determination of an optimal location for a single facility. In some situations, facilities can have capacity constraints, which gives rise to the capacitated multi-facility Weber problem (CMFWP). As can be observed, in an optimal solution of the uncapacitated problem each customer is served from the nearest facility, which is not true for the more restricted CMFWP because of the capacity constraints. The demand of a customer can be satisfied from different facilities. In other words, the CMFWP is a multi-source problem. The CMFWP belongs to a difficult class of problems. Sherali and Nordai (1988) have shown that it is NP-hard even if all the customers are located on a straight line. This is the deterministic version of the problem and assumes that customer locations are known, which is not satisfied in most of the real world applications. A typical example is the determination of emergency station locations. Since we can never exactly know where an emergency call occurs, a reasonable approach is to assume that they have random locations. We refer to this probabilistic version of the problem as the probabilistic capacitated multi-facility Weber problem (PCMFWP), where customer locations are two-dimensional random vectors distributed according to some bivariate probability density function.
Several attempts have been made to solve different classes of the uncapacitated version of the probabilistic multi-facility Weber problem (PMFWP). The earliest ones are due to Cooper, 1974, Katz and Cooper, 1974 where they consider the single-facility probabilistic Weber problem, or simply the probabilistic Weber problem, with the Euclidean distance. They assume that customer locations are independently distributed according to a bivariate normal distribution and propose an algorithm to minimize the total expected cost. Later on, Katz and Cooper (1976) extend their previous results to also consider the cases where customer locations follow bivariate exponential and bivariate symmetric exponential distributions. The paper by Wesolowsky (1977) is also on the probabilistic Weber problem, but involves the rectilinear distance function, and three different probability distributions for customer locations: bivariate normal, bivariate symmetric exponential and bivariate uniform. Although there are works on the multi-facility (pure) location problem with probabilistic customer locations (Aly and White, 1978, Rao and Varma, 1985), none of them actually deals with the PCMFWP. The only exception is due to Cooper (1978) where he proposes a solution procedure for the probabilistic multi-facility location–allocation problem in which facilities have limited capacities using his (1974), and Katz and Cooper (1974) earlier results. This method requires the complete enumeration of all extreme points of the transportation polytope, and hence can be used only for small problems. They also assume that distances are Euclidean, which is somewhat restrictive since the Euclidean distance function may not be a good choice to model distances as discussed by Love and Morris, 1972, Love and Morris, 1979.
In this work, we consider the PCMFWP and propose a new local improvement method using Cooper’s alternate location–allocation (ALA) idea (Cooper, 1964). We call it the probabilistic capacitated alternate location–allocation heuristic (PCALA). Expected distance evaluations are crucial in the use of PCALA. We first consider specific distance functions and customer probability distributions for which this can be done exactly. We derive expressions for the expected values of the squared Euclidean and rectilinear distances, and the weighted -norm with and without assumptions on customer location probability distributions. Then we suggest approximations, which extend PCALA and make it applicable for any distance function and location distribution. One of them is general and can be used not only for the determination of the expected distances but also the expected value of more general functions of random variables. The others use basic principles of non-parametric statistics.
In the next section we present the mathematical programming formulation of the PCMFWP, which is followed by the description of the new heuristic in Section 3. Sections 4 and 5 report new results useful for evaluating expected distances. Computational experiments helping to assess the effect of the approximations on the performance of the new heuristic both in terms of solution quality and computational efficiency are presented in Section 6. Finally, conclusions and directions for future research can be found in the last section.
Section snippets
The probabilistic capacitated multi-facility Weber problem
The well-known mathematical formulation of the CMFWP is
CMFWP:Here, n is the number of customers and m is the number of facilities to be located. and represent, respectively, the demand and coordinates of customer j. The capacity of facility i is given by and denotes its unknown coordinates. Then, the distance between facility i and customer j is measured by the function
Alternate location–allocation heuristic
Once a feasible transportation plan is given, the problem reduces to the solution of m probabilistic Weber problemsfor each facility . Although the summation is taken over all customers, it only considers of them, which is the size of the set . Clearly, since a customer can be served by more than one facility. Notice that the expected cost is a function of the coordinates of facility i. In short, when a feasible
Evaluating expected distances
The evaluation of the expected distancefor given facility coordinate values is crucial not only for the implementation of PCALA but also for the solution of the PCMFWP in general. This may not be possible because of a couple of reasons. First of all the bivariate probability density function of customer locations may be unavailable. Second, even if such information is available it may still be impossible to evaluate the double integral
Computational results
In this section, we assess the performance of the three approximation methods, namely Taylor series with true parameters (TSTP), Taylor series with estimated parameters (TSEP) and average distance (AD) with respect to the exact method (EM) in terms of solution quality and running time efficiency. We use PCALA as our instrument and run it on a number of PCMFWP instances with exact and approximate expectations. Unfortunately, there is no standard test library for the PCMFWP available in the
Conclusions
In this paper, we have considered the probabilistic capacitated multi-facility Weber problem. It is a more realistic extension of the deterministic capacitated multi-facility Weber problem where customer coordinates are distributed according to some bivariate probability distribution. Although it is not difficult to show that an optimal solution occurs at one of the extreme points of the transportation polytope, which describes the set of feasible allocations, no efficient method is known for
References (29)
- et al.
Accelerating convergence in the Fermat–Weber location problem
Operations Research Letters
(1998) The stochastic transportation-location problem
Computational Mathematics with Applications
(1978)An efficient algorithm for determining the convex hull of a finite planar set
Information Process Letter
(1972)- et al.
Probabilistic formulations of the multi-facility Weber problem
Naval Research Logistics Quarterly
(1978) - Al-Loughani, I., 1997. Algorithmic approaches for solving the Euclidean distance location–allocation problems. Ph.D....
- et al.
Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem
Journal of the Operational Society
(2007) - et al.
Improvements and comparison of heuristics for solving the uncapacitated multi-source Weber problem
Operations Research
(2000) - et al.
Global convergence of a generalized iterative procedure for the minisum location problem with distances
Operations Research
(1993) Heuristic methods for location–allocation problems
SIAM Review
(1964)Solutions of generalized locational equilibrium models
Journal of Regional Science
(1967)
The transportation-location problem
Operations Research
A random locational equilibrium problem
Journal of Regional Sciences
A Weiszfeld method for a generalized distance minisum location model in continuous space
Location Science.
Cited by (32)
The Obnoxious Facilities Planar p-Median Problem with Variable Sizes
2022, Omega (United Kingdom)Navigating concave regions in continuous facility location problems
2020, Computers and Industrial EngineeringAmbulance allocation considering the spatial randomness of demand
2020, Computers and Industrial EngineeringCitation Excerpt :Their method can overcome the overstaffing in existing models; however, the specific spatial distribution of the demand in each area is ignored. Altınel, Durmaz, Aras, and Özkısacık (2009) studied the capacitated multifacility Weber problem with probabilistic customer locations. They assumed that customer locations are randomly distributed according to a bivariate distribution.
Simulation modeling and optimization for ambulance allocation considering spatiotemporal stochastic demand
2019, Journal of Management Science and EngineeringCitation Excerpt :Their method overcomes the problem of overstaffing encountered in existing models; however, they ignore the specific spatial distribution of the demand in each area. Altınel, Durmaz, Aras, and Özkısacık (2009) studied the capacitated multifacility Weber problem using probabilistic customer locations. They assume that customer locations are randomly distributed according to a bivariate distribution.
Data center supply chain configuration design: A two-stage decision approach
2019, Socio-Economic Planning SciencesCitation Excerpt :Katz and Cooper [14] introduced Weber problem in a probabilistic setting and presented an iterative heuristic with has the global convergence property. This problem was later revisited by Altınel et al. [2], in which the authors proposed an alternate location-allocation local search heuristic derived from the deterministic version. Facility location problem with consideration to balancing the allocation of capacities has been addressed by several studies.
Designing sustainable energy regions using genetic algorithms and location-allocation approach
2016, EnergyCitation Excerpt :Manzour-al-Ajdad et al. [42] propose an iterative two-phase solution procedure and they modify the allocation phase of the algorithm by considering the preferences of the customers. Altinel et al. [3] propose a location–allocation heuristic for the capacitated multi-facility Weber problem with probabilistic customer locations. Oncan [50] uses location-allocation heuristic and considers both the Euclidean and rectilinear distance and applies its extension by embedding a Very Large Scale Neighborhood search procedure.
- ☆
This work has been partly supported by Boğaziçi Research Fund Grant No: 06HA304D.