مدل برنامه ریزی خطی جدید عدد صحیح مختلط برای مشکل موقعیت تاسیسات چندسطحی
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|25484||2014||12 صفحه PDF||سفارش دهید||7510 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : DOI: 10.1016/j.apm.2013.10.012, Volume 38, Issues 7–8, 1 April 2014, Pages 2118–2129
This paper considers the multi level uncapacitated facility location problem (MLUFLP). A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on instances known from literature. The results achieved by CPLEX and Gurobi solvers, based on the proposed MILP formulation, are compared to the results obtained by the same solvers on the already known formulations. The results show that CPLEX and Gurobi can optimally solve all small and medium sized instances and even some large-scale instances using the new formulation.
The interest in solving facility location problems has been growing steadily in the past few decades. Review of a large variety of facility location problems can be found in . The main focus of the research in this area has been concentrated on the location problems, which require minimization of total travel time, physical distance, or some other related cost. Very often, it is assumed that facilities have sufficiently large capacities to meet even the largest demands. Such problems are mostly called uncapacitated, in contrast to those where capacities are limited, and quite a few deterministic models are proposed for solving such problems. On the other hand, there are some models which include uncertainty , but describing all such approaches is out of this paper scope. In the classical single-level uncapacitated facility location problem, the key decision is to determine the location of facilities and to assign each client to an open facility, in a way that minimizes the total cost of opening the facilities and servicing the clients. In the multilevel uncapacitated facility location problem (MLUFLP), each client must be serviced, in general, by a sequence of, at most, k different facilities. The multi level uncapacitated facility location problem is NP-hard, since it is a generalization of the (single level) uncapacitated facility location problem whose NP-hardness is proven in . This paper considers a hierarchical system of facilities composed of k levels in which the lowest level of facilities is called level 1, whereas the highest level is level k. The clients can be defined as level 0. The existence of a network whose vertices represent facilities and clients is assumed. Classification of such a hierarchical system of facilities and their associated client and respective location problems is given in  where it was determined according to four attributes. The first attribute, flow pattern, describes the flow of services or goods on edges between vertices of the network. The other two attributes, service availability and spatial configuration of services, express the vertical interaction between levels of the hierarchy. The last attribute is the objective for locating the facilities. • Flow pattern. It can be either single-flow or multi-flow. Single-flow starts at level 0, passes through all levels, and ends at the highest level (or it starts from the highest level and ends at level 0). It means that facilities included in flow must belong to consecutive levels. Multi-flow can be between facilities on any level, not only consecutive ones. • Service varieties. There are two possibilities, nested or non-nested, depending on the service availability at various levels. In a nested case, a higher-level facility provides all the services provided by a lower level facility and at least one additional service. In a non-nested case, facilities at each level offer different services, as can be seen in . • Spatial configuration: Depending on the spatial configuration of levels the system can be coherent or non-coherent. In the former case, all clients assigned to a particular lower-level facility are assigned to one and the same higher-level facility as in . Non-coherent systems are less constrained on the spatial configuration of levels. • Objective: There are three well-known types of objectives to locate facilities: median, covering, and fixed charge objectives. The median models try to minimize transportation costs between clients and facilities. In covering models, a client is considered covered by a facility if the facility is located within a specified proximity. Consequently, covering models essentially try to minimize the number of facilities needed for coverage of all clients (set covering) and to maximize covered clients with a particular number of facilities (maximum covering). The fixed charge location models try to minimize the total facility set up and transportation costs. Most of these problem types can be extended to a multiple objective optimization. Basic applications of multilevel facility location problem (uncapacitated and capacitated) can be found, for example, in health-care systems  and , solid waste management systems , production–distribution systems  and , education systems , emergency medical service (EMS) systems , telecommunication networks  and , etc. Theoretical applications on the bounded depth Steiner tree and range assignment problems with corresponding model can be found in . There are two different approaches in formulating MILP models for hierarchical location problems. Both approaches are well represented in literature: flow-based and (path) assignment-based formulations. In flow-based formulations, demand flows from facilities at one level to the next level of the hierarchy, similarly to network flow problems. The assignment-based formulations allocate demand to facilities at each hierarchical level, as it may be the case in assignment problems. Both formulations are usually used in solving minisum location problems: p-Median and fixed charge problems. The models that consider the covering location problems are out of the scope of this paper and can be found in . Both flow-based and assignment-based formulations have produced several MILP models. Some of the flow-based formulation models can be found in , ,  and  and certain assignment-based formulation models can be found in ,  and . Models for both formulations can be found in . The difference between the two formulations is in the way that the demand of each facility is being treated. In the flow-based formulation, the quantity of goods or services that flows through the facility, is represented by a variable, which determines the flow from one-level of the hierarchy to another. Assignment-based formulation, on the other hand, determines demand of a client by assigning a set of facilities, one from each level, which will satisfy it. The model proposed in this paper belongs to the class of assignment-based formulations, so those models will be discussed in more detail.
نتیجه گیری انگلیسی
This paper deals with the multilevel uncapacitated facility location problem. New mixed integer linear programming formulation is proposed. Furthermore, equivalence between the ILP model (EDW model) and the new model is proven. In comparison to the EDW and GAB models, the numbers of variables for large-scale instances with more than 1 level, are significantly reduced in the new model. All models are tested by CPLEX and Gurobi solvers on instances from literature. By using the new model, medium-size instances can be optimally solved with both solvers in relatively short period of time. Furthermore, CPLEX and Gurobi solvers on the new model optimally solve some of large-scale instances which are out of reach when applied on EDW and GAB models. This research can be extended in several ways. It would be desirable to investigate the application of some exact method using the proposed MILP formulation. Further research should also be directed at solving similar problems and testing on parallel computers.