M. Albareda Sambola, E. Fernández, F. Saldanha da Gama
In this work we propose a GRASP with Path Relinking procedure for the facility location problem with Bernoulli demands. This is a discrete two-stage stochastic facility location problem. A set of potential locations for the facilities is given. The demand of each customer follows a Bernoulli distribution with a parameter that may change from customer to customer. The facilities are capacitated. Such capacity is location-dependent and refers to the maximum number of customers that a facility operating in that location can serve.
A decision has to be made here-and-now concerning (i) the facilities to open, and (ii) the (single) assignment of all customers to the opened facilities. Since this decision is made prior to knowing which customers will actually call for being served, it may happen that for one or several opened facilities the above assignment results in a cluster of customers with cardinality larger than the capacity of the facility. Accordingly, after uncertainty is revealed (i.e., after knowing which customers actually call for being served) a recourse action may have to be made if for some facility the number of customers calling for service—among those assigned to the facility—is larger than the capacity of the facility. The recourse action consists of outsourcing the service. Two outsourcing strategies are considered. In the first one—facility outsourcing—extra capacity is paid for those facilities running out of capacity. In the second one—customer outsourcing—an external service provider is paid for fulfilling the missing capacity. The costs involved in this problem include the setup costs for the facilities, the service costs, and the outsourcing costs. A neutral attitude is assumed for the decision maker. The goal is to minimize the total setup cost for the facilities plus the expected service and outsourcing costs.
For the above problem, we propose a two-stage heuristic approach. In the first stage, feasible solutions are generated using a GRASP procedure whose constructive step focuses on the facility selection and the local search step focuses on customers’ assignment. In the second stage, Path Relinking is applied to a pool of elite solutions. Throughout the procedure, approximations for the cost function are used, since evaluating feasible solutions to overall problem is computationally expensive.
We report the results of a series of computational tests performed in order to evaluate the quality of the solutions obtained. We first test the approach for the homogeneous case (all customers having the same probability of calling for service) since, in this case, we can take advantage from “friendly” extensive forms for the deterministic equivalents, which are mixed-integer linear programming models solvable to optimality for instances of realistic dimensions using an off-the-shelf solver. For the general case, we compare the results obtained by the new heuristic with estimates for the optimal values obtained via sample average approximation.
Keywords: Discrete location; Stochastic programming; Heuristics
Scheduled
T2 Location 1
October 1, 2015 11:30 AM
Salón de actos
