A Genetic Algorithm for Solving a Capacitated p-Median Problem

Facility-location problems have several applications, such as telecommunications, industrial transportation and distribution. One of the most well-known facility-location problems is the p-median problem. This work addresses an application of the capacitated p-median problem to a real-world problem. We propose a genetic algorithm (GA) to solve the capacitated p-median problem. The proposed GA uses not only conventional genetic operators, but also a new heuristic “hypermutation” operator suggested in this work. The proposed GA is compared with a tabu search algorithm.     

Heuristic Solution Methods for Two Location Problems with Unreliable Facilities

In this paper, the p-median and p-centre problems are generalized by considering the possibility that one or more of the facilities may become inactive. The unreliable p-median problem is defined by introducing the probability that a facility becomes inactive. The (p, q)-centre problem is defined when p facilities need to be located but up to q of them may become unavailable at the same time. An heuristic procedure is presented for each problem. A rigorous procedure is discussed for the (p, q)-centre problem. Computational results are presented.     

Local networks for computer communications: A. WEST and P. JANSON (Eds.) Proceedings of the IFIP Working Group 6.4, International Workshop on Local Networks,Zürich,Switzerland, August 27–29, 1980, North-Holland,Amsterdam, 1981, xiii + 470 pages,Dfl.125.00

In this paper we present two lower bounds for the p-median problem, the problem of locating p facilities (medians) on a network. These bounds are based on two separate lagrangean relaxations of a zero-one formulation of the problem with subgradient optimisation being used to maximise these bounds. Penalty tests based on these lower bounds and a heuristically determined upper bound to the problem are developed and shown to result in a large reduction in problem size. The incorporation of the lower bounds and the penalty tests into a tree search procedure is described and computational results are given for problems with an arbitrary number of medians and having up to 200 vertices. A comparison is also made between these algorithms and the dual-based algorithm of Erlenkotter.     

Worst-case analysis of demand point aggregation for the Euclidean p-median problem

Solving large-scale p-median problems is usually time consuming. People often aggregate the demand points in a large-scale p-median problem to reduce its problem size and make it easier to solve. Most traditional research on demand point aggregation is either experimental or assuming uniformly distributed demand points in analytical studies. In this paper, we study demand point aggregation for planar p-median problem when demand points are arbitrarily distributed. Efficient demand aggregation approaches are proposed with the corresponding attainable worst-case aggregation error bounds measured. We demonstrate that these demand aggregation approaches introduce smaller worst-case aggregation error bounds than that of the honeycomb heuristic [Papadimitriou, C.H., 1981. Worst-case and probabilistic analysis of a geometric location problem. SIAM Journal on Computing 10, 542–557] when demand points are arbitrarily distributed. We also conduct numerical experiments to show their effectiveness.     

A note on solving large p-median problems

In a previous paper we presented a tree search algorithm for the p-median problem, the problem of locating p facilities (medians) on a network, which was based upon La grangean relaxation and subgradient optimisation. That algorithm solved (optimally) problems with an arbitrary number of medians and having up to 200 vertices.In this note we show that it is possible to enhance that algorithm to solve (optimally) problems having up to 900 vertices using the Cray-1S computer.     

‘Multidimensional’ extensions and a nested dual approach for the m-median problem

A general framework for modeling median type locational decisions, where (i) travel costs and demands may be stochastic, (ii) multiple services or commodities need to be considered, and/or (iii) multiple median type objectives might exist, is presented—using the concept of “multidimensional networks”. The classical m-median problem, the stochastic m-median problem, the multicommodity m-median problem and and multiobjective m-median problem are defined within this framework.By an appropriate transformation of variables, the multidimensional m-median problem simplifies to the classical m-median problem but with a K-fold increase in the number of nodes, where K is the number of dimensions of the network. A nested dual approach to solve the resulting classical m-median problem, that uses Erlenkotter's facility location scheme as a subroutine, is presented. Computational results indicate that the procedure may perhaps be the best available one to solve the m-median problem exactly.     

The gravity p-median model

In this paper we propose a new model for the p-median problem. In the standard p-median problem it is assumed that each demand point is served by the closest facility. In many situations (for example, when demand points are communities of customers and each customer makes his own selection of the facility) demand is divided among the facilities. Each customer selects a facility which is not necessarily the closest one. In the gravity p-median problem it is assumed that customers divide their patronage among the facilities with the probability that a customer patronizes a facility being proportional to the attractiveness of that facility and to a decreasing utility function of the distance to the facility.     

An Algorithm for Solving Capacitated Multicommodity <Emphasis Type="Italic">p</Emphasis>-median Transportation Problems

An algorithm for solving a special capacitated multicommodity p-median transportation problem (CMPMTP), which arises in container terminal management, is presented. There are some algorithms to solve similar kinds of problems. The formulation here is different from the existing modelling of the p-median or some related location problems. We extend the existing work by applying a Lagrangean relaxation to the CMPMTP. In order to obtain a satisfactory solution, a heuristic branch-and-bound algorithm is designed to search for a better solution, if one is possible. A comparison is also made with different algorithms.     

Heuristic Procedures for Solving the Discrete Ordered Median Problem

We present two heuristic methods for solving the Discrete Ordered Median Problem (DOMP), for which no such approaches have been developed so far. The DOMP generalizes classical discrete facility location problems, such as the p-median and p-center. The first procedure proposed in this paper is based on a genetic algorithm developed by Moreno Vega (1996) for p-median and p-center problems. Additionally, a second heuristic approach based on the Variable Neighborhood Search metaheuristic (VNS) proposed by Hansen and Mladenović (1997) for the p-median problem is described. An extensive numerical study is presented to show the efficiency of both heuristics and compare them.     

A new heuristic approach for the P-median problem

The Euclidean p-median problem is concerned with the decision of the locations for public service centres. Existing methods for the planar Euclidean p-median problems are capable of efficiently solving problems of relatively small scale. This paper proposes two new heuristic algorithms aiming at problems of large scale. Firstly, to reflect the different degrees of proximity to optimality, a new kind of local optimum called level-m optimum is defined. For a level-m optimum of a p-median problem, where m<p, each of its subsets containing m of the p partitions is a global optimum of the corresponding m-median subproblem. Starting from a conventional local optimum, the first new algorithm efficiently improves it to a level-2 optimum by applying an existing exact algorithm for solving the 2-median problem. The second new algorithm further improves it to a level-3 optimum by applying a new exact algorithm for solving the 3-median problem. Comparison based on experimental results confirms that the proposed algorithms are superior to the existing heuristics, especially in terms of solution quality.     

The connected <Emphasis Type="Italic">p</Emphasis>-median problem on block graphs

In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G.     

The directional p-median problem: Definition,complexity, and algorithms

An instance of a p-median problem gives n demand points. The objective is to locate p supply points in order to minimize the total distance of the demand points to their nearest supply point. p-Median is polynomially solvable in one dimension but NP-hard in two or more dimensions, when either the Euclidean or the rectilinear distance measure is used. In this paper, we treat the p-median problem under a new distance measure, the directional rectilinear distance, which requires the assigned supply point for a given demand point to lie above and to the right of it. In a previous work, we showed that the directional p-median problem is polynomially solvable in one dimension; we give here an improved solution through reformulating the problem as a special case of the constrained shortest path problem. We have previously proven that the problem is NP-complete in two or more dimensions; we present here an efficient heuristic to solve it. Compared to the robust Teitz and Bart heuristic, our heuristic enjoys substantial speedup while sacrificing little in terms of solution quality, making it an ideal choice for real-world applications with thousands of demand points.     

A Lagrangian search method for the <Emphasis Type="Italic">P</Emphasis>-median problem

In this paper, we propose a novel algorithm for solving the classical P-median problem. The essential aim is to identify the optimal extended Lagrangian multipliers corresponding to the optimal solution of the underlying problem. For this, we first explore the structure of the data matrix in P-median problem to recast it as another equivalent global optimization problem over the space of the extended Lagrangian multipliers. Then we present a stochastic search algorithm to find the extended Lagrangian multipliers corresponding to the optimal solution of the original P-median problem. Numerical experiments illustrate that the proposed algorithm can effectively find a global optimal or very good suboptimal solution to the underlying P-median problem, especially for the computationally challenging subclass of P-median problems with a large gap between the optimal solution of the original problem and that of its Lagrangian relaxation.     

<Emphasis Type="Italic">p</Emphasis>-Medians and Multi-Medians

The classical p-median problem is discussed, together with methods for its solution. The multi-median problem, a generalization of the p-median problem in which more than one type of facility is allowed, is introduced and methods of solution developed. Numerical results are presented.     

An effective VNS for the capacitated p-median problem

In the capacitated p-median problem (CPMP), a set of n customers is to be partitioned into p disjoint clusters, such that the total dissimilarity within each cluster is minimized subject to constraints on maximum cluster capacity. Dissimilarity of a cluster is the sum of the dissimilarities between each customer who belongs to the cluster and the median associated with the cluster. An effective variable neighbourhood search heuristic for this problem is proposed. The heuristic is characterized by the use of easily computed lower bounds to assess whether undertaking computationally expensive calculation of the worth of moves, within the neighbourhood search, is necessary. The small proportion of moves that need to be assessed fully are then evaluated by an exact solution of a relatively small subproblem. Computational results on five standard sets of benchmark problem instances show that the heuristic finds all the best-known solutions. For one instance, the previously best-known solution is improved, if only marginally.     

The p-median problem: A survey of metaheuristic approaches

The p-median problem is one of the basic models in discrete location theory. As with most location problems, it is classified as NP-hard, and so, heuristic methods are usually used to solve it. Metaheuristics are frameworks for building heuristics. In this survey, we examine the p-median, with the aim of providing an overview on advances in solving it using recent procedures based on metaheuristic rules.     

Some heuristic methods for solving p-median problems with a coverage constraint

The aim of this paper is to solve p-median problems with an additional coverage constraint. These problems arise in location applications, when the trade-off between distance and coverage is being calculated. Three kinds of heuristic algorithms are developed. First, local search procedures are designed both for constructing and improving feasible solutions. Second, a multistart GRASP heuristic is developed, based on the previous local search methods. Third, by employing Lagrangean relaxation methods, a very efficient Lagrangean heuristic algorithm is designed, which extends the well known algorithm of Handler and Zang, for constrained shortest path problems, to constrained p-median problems. Finally, a comparison of the computational efficiency of the developed methods is made between a variety of problems of different sizes.     

Hierarchical location-allocation problems: A classification scheme

In the literature, the p-median problem has been well studied. For the p-median problem our objective is to locate p facilities among n(? p) locations such that the total weighted travel distance is minimized. In the problem formulation, it is tacitly assumed that the facilities are of one type.In many practical situations, systems that provide products/services generally consist of k( ? 2) distinct types of facilities. In such problems, we would like to locate p_i type i facilities, i = 1, 2, … k, among n ( ? Σ_i^k = ₁p_i) available locations. Here also our objective may be to locate these facilities such that the ‘total weighted travel distance’ is minimized. What makes these problems difficult and interesting is that the extension of the p-median problem formulation and solution procedures to these problems is not always obvious, easy or straightforward. The problem formulation and solution procedures depend upon the hierarchical relationship among the facility types and the flow of goods and services allowed among them.In this paper we attemp to classify the hierarchical location-allocation problems.     

Approximate solution of the <Emphasis Type="Italic">p</Emphasis>-median minimization problem

A version of the facility location problem (the well-known p-median minimization problem) and its generalization—the problem of minimizing a supermodular set function—is studied. These problems are NP-hard, and they are approximately solved by a gradient algorithm that is a discrete analog of the steepest descent algorithm. A priori bounds on the worst-case behavior of the gradient algorithm for the problems under consideration are obtained. As a consequence, a bound on the performance guarantee of the gradient algorithm for the p-median minimization problem in terms of the production and transportation cost matrix is obtained.     

A compelling argument for the gravity p-median model

The p-median model is used to locate P facilities to serve a geographically distributed population. Conventionally, it is assumed that the population always travels to the nearest facility.  and  re-estate three arguments on why this assumption might be incorrect, and they introduce the gravity p-median model to relax the assumption. We favor the gravity p-median model, but we note that in an applied setting, the three arguments are incomplete. In this communication, we point at the existence of a fourth compelling argument for the gravity p-median model.