دانلود رایگان ترجمه مقاله مسئله مکان یابی حداکثر پوشش MCLP با زمان های سفر فازی (نشریه الزویر 2011)

مسئله مکان یابی حداکثر پوشش MCLP با زمان های سفر فازی

Maximal covering location problem (MCLP) with fuzzy travel times

Abstract

This paper presents a fuzzy maximal covering location problem (FMCLP) in which travel time between any pair of nodes is considered to be a fuzzy variable. A fuzzy expected value maximization model is designed for such a problem. Moreover, a hybrid algorithm of fuzzy simulation and simulated annealing (SA) is used to solve FMCLP. Some numerical examples are presented, solved and analyzed to show the performance of the proposed algorithm. The results show that the proposed SA finds solutions with objective values no worse than 1.35% below the optimal solution. Furthermore, the simulation-embedded simulated annealing is robust in finding solutions.

1- Introduction and problem description

The term location analysis refers to the modeling, formulation, and solution of a class of problems that can best be described as siting facilities in some given space. The expressions deployment, positioning, and siting are frequently used as synonyms (ReVelle & Eiselt, 2005). Applications of location problems range from gas stations and fast food outlets to landfills and power plants. One of the traditional location problems, which has been well studied since its introduction, is the covering location problem. In a covering location problem, one seeks a solution to cover a subset of customers considering one or more objectives. The covering location problem is often categorized as location set covering problem (LSCP) and maximal covering location problem (MCLP). In a standard MCLP, one seeks location of a number of facilities on a network in such a way that the covered population is maximized. A population is covered if at least one facility is located within a pre-defined distance of it. This pre-defined distance is often called coverage radius. The choice of this distance has a vital role and affects the optimal solution of the problem to a great extent. MCLP is of paramount importance in practice to locate many service facilities such as schools, parks, hospitals and emergency units. The problem was first introduced by Church and ReVelle (1974) on a network and since then, various extensions to the original problem have been made. Normally, MCLP is considered whenever there are insufficient resources or budget to cover the demand of all the nodes. Therefore, the decision maker determines a fixed budget/resource to cover the demands as much as possible. Uncertainty is ubiquitous in reality and this makes description of many parameters difficult or even impossible. Some examples of uncertainty in real world problems are the estimation of customer demands, travel times, inflation rate, etc. In this paper, we assume that there is not precise information concerning travel times on the arcs of network. In addition, there is not enough data to be used in order to find a statistical distribution. Therefore, demands are estimated based on the knowledge of experts. For example, experts may state their ideas as ‘‘about 40 units per day’’, ‘‘between 10 and 20 units weekly’’, etc. Fuzzy variables are used in these cases to deal with this kind of uncertainty. Travel time is an instance of variables which are difficult to estimate using traditional methods such as probabilistic methods. In most of the cases, there is not enough data to be used to fit a probability distribution of travel times between nodes or probabilistic approach is too costly to be used. On the other hand, based on the expert’s judgment; one can easily estimate transportation times. Therefore, we use fuzzy theory in order to model and solve our problem. In this paper, we present a fuzzy version of MCLP (FMCLP) where travel times are considered to be fuzzy variables. A model based on credibility theory is presented and a hybrid intelligent algorithm is proposed in order to solve this problem. The hybrid algorithm is comprised of a simulation embedded within a simulated annealing procedure. The rest of the paper is organized as follows: First, a concise literature review of covering problems and related issues is presented. Then, fuzzy variables and basics of credibility theory are discussed. Section 4 is dedicated to description of our problem. The proposed solution algorithm is presented in Section 5 and a numerical example appears in Section 6. Finally, conclusions and outlooks for potential future research are given in Section 7.