The incorporation of fixed cost and multilevel capacities into the discrete and continuous single source capacitated facility location problem

In this study we investigate the single source location problem with the presence of several possible capacities and the opening (fixed) cost of a facility that is depended on the capacity used and the area where the facility is located. Mathematical models of the problem for both the discrete and the continuous cases using the Rectilinear and Euclidean distances are produced. Our aim is to find the optimal number of open facilities, their corresponding locations, and their respective capacities alongside the assignment of the customers to the open facilities in order to minimise the total fixed and transportation costs. For relatively large problems, two solution methods are proposed namely an iterative matheuristic approach and VNS-based matheuristic technique. Dataset from the literature is adapted to assess our proposed methods. To assess the performance of the proposed solution methods, the exact method is first applied to small size instances where optimal solutions can be identified or lower and upper bounds can be recorded. Results obtained by the proposed solution methods are also reported for the larger instances.

     

关于可靠性设施布局问题的近似算法

设施布局问题的研究始于20世纪60年代,主要研究选择修建设施的位置和数量,以及与需要得到服务的城市之间的分配关系,使得设施的修建费用和设施与城市之间的连接费用之和达到最小.现实生活中, 受自然灾害、工人罢工、恐怖袭击等因素的影响,修建的设施可能会出现故障, 故连接到它的城市无法得到供应,这就直接影响到了整个系统的可靠性.针对如何以相对较小的代价换取设施布局可靠性的提升,研究人员提出了可靠性设施布局问题.参考经典设施布局问题的贪婪算法、原始对偶算法和容错性问题中分阶段分层次处理的思想,设计了可靠性设施布局问题的一个组合算法.该算法不仅在理论上具有很好的常数近似度,而且还具有运算复杂性低的优点.这对于之前的可靠性设施布局问题只有数值实验算法, 是一个很大的进步.     

Medi-centre Location Problems

In this paper we consider two medi-centre location problems. One is the m-medi-centre problem in which we add to the m-median problem uniform distance constraints. The other problem is the uncapacitated medi-centre facility location problem where we include the fixed costs of establishing the facilities and thus the number of facilities is also a decision variable. For the two problems we present algorithms and discuss computational experience.     

A neural network approach to facility layout problems

A near-optimum parallel algorithm for solving facility layout problems is presented in this paper where the problem is NP-complete. The facility layout problem is one of the most fundamental quadratic assignment problems in Operations Research. The goal of the problem is to locate N facilities on an N-square (location) array so as to minimize the total cost. The proposed system is composed of N × N neurons based on an artificial two-dimensional maximum neural network for an N-facility layout problem. Our algorithm has given improved solutions for several benchmark problems over the best existing algorithms.     

GRASP with path-relinking for the generalized quadratic assignment problem

The generalized quadratic assignment problem (GQAP) is a generalization of the NP-hard quadratic assignment problem (QAP) that allows multiple facilities to be assigned to a single location as long as the capacity of the location allows. The GQAP has numerous applications, including facility design, scheduling, and network design. In this paper, we propose several GRASP with path-relinking heuristics for the GQAP using different construction, local search, and path-relinking procedures. We introduce a novel approximate local search scheme, as well as a new variant of path-relinking that deals with infeasibilities. Extensive experiments on a large set of test instances show that the best of the proposed variants is both effective and efficient.     

LP-based approximation algorithms for capacitated facility location

In the capacitated facility location problem with hard capacities, we are given a set of facilities, ${\mathcal{F}}$ , and a set of clients ${\mathcal{D}}$ in a common metric space. Each facility i has a facility opening cost f _i and capacity u _i that specifies the maximum number of clients that may be assigned to this facility. We want to open some facilities from the set ${\mathcal{F}}$ and assign each client to an open facility so that at most u _i clients are assigned to any open facility i. The cost of assigning client j to facility i is given by the distance c _ij , and our goal is to minimize the sum of the facility opening costs and the client assignment costs. The only known approximation algorithms that deliver solutions within a constant factor of optimal for this NP-hard problem are based on local search techniques. It is an open problem to devise an approximation algorithm for this problem based on a linear programming lower bound (or indeed, to prove a constant integrality gap for any LP relaxation). We make progress on this question by giving a 5-approximation algorithm for the special case in which all of the facility costs are equal, by rounding the optimal solution to the standard LP relaxation. One notable aspect of our algorithm is that it relies on partitioning the input into a collection of single-demand capacitated facility location problems, approximately solving them, and then combining these solutions in a natural way.     

The single facility location problem with time-dependent weights and relocation cost over a continuous time horizon

In this study, we investigate the problem of locating a facility in continuous space when the weight of each existing facility is a known linear function of time. The location of the new facility can be changed once over a continuous finite time horizon. Rectilinear distance and time- and location-dependent relocation costs are considered. The objective is to determine the optimal relocation time and locations of the new facility before and after relocation to minimize the total location and relocation costs. We also propose an exact algorithm to solve the problem in a polynomial time according to our computational results.     

An efficient algorithm for facility location in the presence of forbidden regions

This paper investigates a constrained form of the classical Weber problem. Specifically, we consider the problem of locating a new facility in the presence of convex polygonal forbidden regions such that the sum of the weighted distances from the new facility to n existing facilities is minimized. It is assumed that a forbidden region is an area in the plane where travel and facility location are not permitted and that distance is measured using the Euclidean-distance metric. A solution procedure for this nonconvex programming problem is presented. It is shown that by iteratively solving a series of unconstrained problems, this procedure terminates at a local optimum to the original constrained problem. Numerical examples are presented.     

A new exact discrete linear reformulation of the quadratic assignment problem

The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB.     

A note on the allocation of queuing facilities using a minisum criterion

This paper suggests a formulation and a solution procedure for resource allocation problems which consider a central planner, m static queuing facilities providing a homogeneous service at their locations, and a known set of demand points or customers. It is assumed that upon a request for service the customer is routed to a facility by a probabilistic assignment. The objective is to determine how to allocate a limited number of servers to the facilities, and to specify demand rates from customers to facilities in order to minimize a weighted sum of response times. This sum measures the total time lost in the system due to two sources: travel time from customer to facility locations and waiting time for service at the facilities. The setting does not allow for cooperation between the facilities.     

A k-product uncapacitated facility location problem

A k-product uncapacitated facility location problem can be described as follows. There is a set of demand points where clients are located and a set of potential sites where facilities of unlimited capacities can be set up. There are k different kinds of products. Each client needs to be supplied with k kinds of products by a set of k different facilities and each facility can be set up to supply only a distinct product with a non-negative fixed cost determined by the product it intends to supply. There is a non-negative cost of shipping goods between each pair of locations. These costs are assumed to be symmetric and satisfy the triangle inequality. The problem is to select a set of facilities to be set up and their designated products and to find an assignment for each client to a set of k   facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, an approximation algorithm within a factor of 2k+1$2k+1$ of the optimum cost is presented. Assuming that fixed setup costs are zero, we give a 2k-1$2k-1$ approximation algorithm for the problem. In addition we show that for the case k=2$k=2$, the problem is NP-complete when the cost structure is general and there is a 2-approximation algorithm when the costs are symmetric and satisfy the triangle inequality. The algorithm is shown to produce an optimal solution if the 2-product uncapacitated facility location problem with no fixed costs happens to fall on a tree graph.     

Greedy approaches for a class of nonlinear Generalized Assignment Problems

The traditional Generalized Assignment Problem (GAP) seeks an assignment of customers to facilities that minimizes the sum of the assignment costs while respecting the capacity of each facility. We consider a nonlinear GAP where, in addition to the assignment costs, there is a nonlinear cost function associated with each facility whose argument is a linear function of the customers assigned to the facility. We propose a class of greedy algorithms for this problem that extends a family of greedy algorithms for the GAP. The effectiveness of these algorithms is based on our analysis of the continuous relaxation of our problem. We show that there exists an optimal solution to the continuous relaxation with a small number of fractional variables and provide a set of dual multipliers associated with this solution. This set of dual multipliers is then used in the greedy algorithm. We provide conditions under which our greedy algorithm is asymptotically optimal and feasible under a stochastic model of the parameters.     

An algorithm portfolio for the dynamic maximal covering location problem

The location of facilities (antennas, ambulances, police patrols, etc) has been widely studied in the literature. The maximal covering location problem aims at locating the facilities in such positions that maximizes certain notion of coverage. In the dynamic or multi-period version of the problem, it is assumed that the nodes’ demand changes with the time and as a consequence, facilities can be opened or closed among the periods. In this contribution we propose to solve dynamic maximal covering location problem using an algorithm portfolio that includes adaptation, cooperation and learning. The portfolio is composed of an evolutionary strategy and three different simulated annealing methods (that were recently used to solve the problem). Experiments were conducted on 45 test instances (considering up to 2500 nodes and 200 potential facility locations). The results clearly show that the performance of the portfolio is significantly better than its constituent algorithms.     

Heuristic algorithms for general <Emphasis Type="Italic">k</Emphasis>-level facility location problems

In a general k-level uncapacitated facility location problem (k-GLUFLP), we are given a set of demand points, denoted by D, where clients are located. Facilities have to be located at a given set of potential sites, which is denoted by F in order to serve the clients. Each client needs to be served by a chain of k different facilities. The problem is to determine some sites of F to be set up and to find an assignment of each client to a chain of k facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, for a fixed k, an approximation algorithm within a factor of 3 of the optimum cost is presented for k-GLUFLP under the assumption that the shipping costs satisfy the properties of metric space. In addition, when no fixed cost is charged for setting up the facilities and k=2, we show that the problem is strong NP-complete and the constant approximation factor is further sharpen to be 3/2 by a simple algorithm. Furthermore, it is shown that this ratio analysis is tight.     

Algorithms for central-median paths with bounded length on trees

The location of path-shaped facilities on trees has been receiving a growing attention in the specialized literature in the recent years. Examples of such facilities include railroad lines, highways and public transit lines. Most of the papers deal with the problem of locating a path on a tree by minimizing either the maximum distance from the vertices of the tree to the facility or of minimizing the sum of the distances from all the vertices of the tree to the path. However, neither of the two above criteria alone capture all essential elements of a location problem. The sum of the distances criterion alone may result in solutions which are unacceptable from the point of view of the service level for the clients who are located far away from the facilities. On the other hand, the criterion of the minimization of the maximum distance, if used alone, may lead to very costly service systems. In the literature, there is just one paper that considers the problem of finding an optimal location of a path on a tree using combinations of the two above criteria, and efficient algorithms are provided. In particular, the cases where one criterion is optimized subject to a restriction on the value of the other are considered and linear time algorithms are presented. However, these problems do not consider any bound on the length or cost of the facility. In this paper we consider the two following problems: find a path which minimizes the sum of the distances such that the maximum distance from the vertices of the tree to the path is bounded by a fixed constant and such that the length of the path is not greater than a fixed value; find a path which minimizes the maximum distance with the sum of the distances being not greater than a fixed value and with bounded length. From an application point of view the constraint on the length of the path may refer to a budget constraint for establishing the facility. The restriction on the length of the path complicates the two problems but for both of them we give O(n log² n) divide-and-conquer algorithms.     

带有线性惩罚的鲁棒k-种产品设施选址问题的近似算法

$k$-种产品设施选址问题是指存在一组客户和一组可以建设设施的地址。现有$k$种不同的产品,每一客户均需要$k$种不同的产品,且每一设施最多只能生产一种产品。问题的要求是从若干地址中选择一组地址来建立设施,对所要建立的设施指定其生产的产品,并为每一个客户提供一组指派确保每一客户都有$k$个设施来为其提供$k$种不同的产品,使得设施建设费用与运输费用之和最小。对于$k$-种产品设施选址问题,我们通常简写为$k$-PUFLP,其中,当所有设施建设费用为0时,记为$k$-PUFLPN。本文对$k$-PUFLPN进行线性舍入,通过分析最优分数解特殊结构,当$k\geq 3$时分析算法将$k$-PUFLPN的近似比从$\frac{3k}{2}-1$提升到了$\frac{3k}{2}-\frac{3}{2}$。鲁棒$k$-种产品设施选址问题是指在该问题中,最多有$q$个客户可以不被服务。我们首次对无容量限制下建设费用为0时的鲁棒$k$-种产品选址问题建立模型,当$k\geq 3$,得到了$\frac{3k}{2}-\frac{3}{2}$近似算法。对顾客伴有线性惩罚的鲁棒$k$-种产品设施选址问题,本文同时考虑异常值与惩罚性,利用$k$-PUFLPN中最优整数解与最优分数解的关系,得到了$\frac{3k}{2}-\frac{3}{2}$近似算法。     

Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem

In this paper, we consider the capacitated multi-facility Weber problem with rectilinear distance. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the rectilinear distance separating them. We first give a new mixed integer linear programming formulation of the problem by making use of a well-known necessary condition for the optimal facility locations. We then propose new heuristic solution methods based on this formulation. Computational results on benchmark instances indicate that the new methods can provide very good solutions within a reasonable amount of computation time.     

A new formulation and an exact approach for the many-to-many hub location-routing problem

An important problem of the freight industry is the parcel delivery network design, where several facilities are responsible for assembling flows from several origins, re-routing them to other facilities where the flows are disassembled and the packages delivered to their final destinations. In order to provide this service, local tours are established for the vehicles assigned to each of the processing facilities, which are then responsible for the pickup and delivery tasks. This application gives rise to the many-to-many hub location routing problem that is the combination of two well known problems: the vehicle routing problem and the single assignment hub location problem. In this work, a new formulation for this important problem is proposed and solved by a specially tailored Benders decomposition algorithm. The proposed method is robust enough to solve instances up to 100 nodes having 4 million integer variables.     

A Linear Programming Approach to the Solution of Constrained Multi-Facility Minimax Location Problems where Distances are Rectangular

The problem of locating new facilities with respect to existing facilities is stated as a linear programming problem where inter-facility distances are assumed to be rectangular. The criterion of location is the minimization of the maximum weighted rectangular distance in the system. Linear constraints which (a) limit the new facility locations and (b) enforce upper bounds on the distances between new and existing facilities and between new facilities can be included. The dual programming problem is formulated in order to provide for an efficient solution procedure. It is shown that the duLal variables provide information abouLt the complete range of new facility locations which satisfy the minimax criterion.     

Improving solution of discrete competitive facility location problems

We consider discrete competitive facility location problems in this paper. Such problems could be viewed as a search of nodes in a network, composed of candidate and customer demand nodes, which connections correspond to attractiveness between customers and facilities located at the candidate nodes. The number of customers is usually very large. For some models of customer behavior exact solution approaches could be used. However, for other models and/or when the size of problem is too high to solve exactly, heuristic algorithms may be used. The solution of discrete competitive facility location problems using genetic algorithms is considered in this paper. The new strategies for dynamic adjustment of some parameters of genetic algorithm, such as probabilities for the crossover and mutation operations are proposed and applied to improve the canonical genetic algorithm. The algorithm is also specially adopted to solve discrete competitive facility location problems by proposing a strategy for selection of the most promising values of the variables in the mutation procedure. The developed genetic algorithm is demonstrated by solving instances of competitive facility location problems for an entering firm.