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.     

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.     

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.     

An adaptive multiphase approach for large unconditional and conditional p-median problems

A multiphase approach that incorporates demand points aggregation, Variable Neighbourhood Search (VNS) and an exact method is proposed for the solution of large-scale unconditional and conditional p-median problems. The method consists of four phases. In the first phase several aggregated problems are solved with a “Local Search with Shaking” procedure to generate promising facility sites which are then used to solve a reduced problem in Phase 2 using VNS or an exact method. The new solution is then fed into an iterative learning process which tackles the aggregated problem (Phase 3). Phase 4 is a post optimisation phase applied to the original (disaggregated) problem. For the p-median problem, the method is tested on three types of datasets which consist of up to 89,600 demand points. The first two datasets are the BIRCH and the TSP datasets whereas the third is our newly geometrically constructed dataset that has guaranteed optimal solutions. The computational experiments show that the proposed approach produces very competitive results. The proposed approach is also adapted to cater for the conditional p-median problem with interesting results.     

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.     

Marginal analysis for the fuzzy p-median problem

The solutions to the fuzzy p-median problem make it possible to leave part of the demand uncovered in order to obtain significant reductions in costs. Moreover, the fuzzy formulation provides the decision-maker with many flexible solutions that he or she may prefer to the classical crisp solution. We introduce some marginal analysis techniques to study how solutions depend on membership functions. Taking into account the internal structure of the problem, we propose a practical criterion to fix the tolerances for the uncovered demand, which happens to be the most sensitive aspect of the fuzzy p-median.     

Lagrangean duals and exact solution to the capacitated p-center problem

In this work, we address the capacitated p-center problem (CpCP). We study two auxiliary problems, discuss their relation to CpCP, and analyze the lower bounds obtained with two different Lagrangean duals based on each of these auxiliary problems. We also compare two different strategies for solving exactly CpCP, based on binary search and sequential search, respectively. Various data sets from the literature have been used for evaluating the performance of the proposed algorithms.     

p-Laplacian problems with jumping nonlinearities

We consider the p-Laplacian boundary value problem

(1)     

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.     

On p-approximation properties for p-operator spaces

This paper has a two-fold purpose. Let 1<p<∞. We first introduce the p-operator space injective tensor product and study various properties related to this tensor product, including the p-operator space approximation property, for p-operator spaces on Lp-spaces. We then apply these properties to the study of the pseudofunction algebra PFp(G), the pseudomeasure algebra PMp(G), and the Figà-Talamanca-Herz algebra Ap(G) of a locally compact group G. We show that if G is a discrete group, then most of approximation properties for the reduced group C^∗-algebra , the group von Neumann algebra VN(G), and the Fourier algebra A(G) (related to amenability, weak amenability, and approximation property of G) have the natural p-analogues for PFp(G), PMp(G), and Ap(G), respectively. The p-completely bounded multiplier algebra McbAp(G) plays an important role in this work.     

Existence of positive solutions for the p-Laplacian with p-gradient term

In this paper, we study the existence of positive solutions for the p-Laplacian involving a p-gradient term. Due to the non-variational structure and the fact that the nonlinearity may be critical or supercritical, the variational method is no longer valid. Taking advantage of global C1,α estimates and the Liouville type theorems, we employ the blow-up argument to obtain the a priori estimates on solutions, and finally obtain the existence result based on the Krasnoselskii fixed point theorem.     

Two genetic algorithms for solving the uncapacitated single allocation p-hub median problem

This paper deals with the Uncapacitated Single Allocation p-Hub Median Problem (USApHMP). Two genetic algorithm (GA) approaches are proposed for solving this NP-hard problem. New encoding schemes are implemented with appropriate objective functions. Both approaches keep the feasibility of individuals by using specific representation and modified genetic operators. The numerical experiments were carried out on the standard ORLIB hub data set. Both methods proved to be robust and efficient in solving USApHMP with up to 200 nodes and 20 hubs. The second GA approach achieves all previously known optimal solutions and achieves the best-known solutions on large-scale instances.     

Some bounds on the p-domination number in trees

Let p be a positive integer and G=(V,E) a graph. A subset S of V is a p-dominating set if every vertex of V-S is dominated at least p times, and S is a p-dependent set of G if the subgraph induced by the vertices of S has maximum degree at most p-1. The minimum cardinality of a p-dominating set a of G is the p-domination number γ_p(G) and the maximum cardinality of a p-dependent set of G is the p-dependence number β_p(G). For every positive integer p?2, we show that for a bipartite graph G, γ_p(G) is bounded above by (|V|+|Y_p|)/2, where Y_p is the set of vertices of G of degree at most p-1, and for every tree T, γ_p(T) is bounded below by β_p-1(T). Moreover, we characterize the trees achieving equality in each bound.     

Residual methods for the large-scale matrix pth root and some related problems

The problem of finding the pth root of a matrix has received special attention in the last few years. Standard approaches for this problem include and combine some variations of Newton’s method, which in turn involve matrix factorizations that, in general, are not suitable for large-scale problems. Motivated by some recently developed low-cost iterative schemes for nonlinear problems, we consider and analyze specialized residual methods that only require a few matrix-matrix products per iteration, and hence are suitable for the large-scale case. As a by-product we also discuss the advantages of residual methods for general nonlinear problems whose variables separate. Preliminary and encouraging numerical results are presented for computing pth roots of large-scale symmetric and positive definite matrices, for different values of p.     

Resonance problems for the p-Laplacian systems

Two existence theorems of the solutions are obtained for the p-Laplacian systems at resonance under a Landesman-Lazer-type condition by critical point theory.     

On a class of singular p-Laplacian boundary value problems

We prove the existence and nonexistence of positive solutions for the boundary value problem

     

A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem

We present a new general variable neighborhood search approach for the uncapacitated single allocation p-hub median problem in networks. This NP hard problem is concerned with locating hub facilities in order to minimize the traffic between all origin-destination pairs. We use three neighborhoods and efficiently update data structures for calculating new total flow in the network. In addition to the usual sequential strategy, a new nested strategy is proposed in designing a deterministic variable neighborhood descent local search. Our experimentation shows that general variable neighborhood search based heuristics outperform the best-known heuristics in terms of solution quality and computational effort. Moreover, we improve the best-known objective values for some large Australia Post and PlanetLab instances. Results with the new nested variable neighborhood descent show the best performance in solving very large test instances.     

The Cauchy problems for evolutionary pseudo-differential equations over p-adic field and the wavelet theory

We solve the Cauchy problems for p-adic linear and semi-linear evolutionary pseudo-differential equations (the time-variable t∈R and the space-variable ). Among the equations under consideration there are the heat type equation and the Schrödinger type equations (linear and nonlinear). To solve these problems, we develop the “variable separation method” (an analog of the classical Fourier method) which reduces solving evolutionary pseudo-differential equations to solving ordinary differential equations with respect to real variable t. The problem of stabilization for solutions of the Cauchy problems as t→∞ is also studied. These results give significant advance in the theory of p-adic pseudo-differential equations and can be used in applications.     

Linear relations for p-harmonic functions

We discuss the p-harmonicity of the linear combination of p-harmonic functions in the Euclidean space and on a tree. If p≠2, the p-harmonicity is non-linear, i.e., the linear combination of p-harmonic functions need not be p-harmonic. In spite of this non-linear nature, we find some p-harmonic functions whose linear combinations become p-harmonic.     

Existence and multiplicity results for Dirichlet problems with p-Laplacian

In this paper we apply Morse theory to study the existence of nontrivial solutions of p-Laplacian type Dirichlet boundary value problems.