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.     

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.     

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.     

Modeling fuzzy capacitated p-hub center problem and a genetic algorithm solution

Hub and spoke networks are used to switch and transfer commodities between terminal nodes in distribution systems at minimum cost and/or time. The p-hub center allocation problem is to minimize maximum travel time in networks by locating p hubs from a set of candidate hub locations and allocating demand and supply nodes to hubs. The capacities of the hubs are given. In previous studies, authors usually considered only quantitative parameters such as cost and time to find the optimum location. But it seems not to be sufficient and often the critical role of qualitative parameters like quality of service, zone traffic, environmental issues, capability for development in the future and etc. that are critical for decision makers (DMs), have not been incorporated into models. In many real world situations qualitative parameters are as much important as quantitative ones. We present a hybrid approach to the p-hub center problem in which the location of hub facilities is determined by both parameters simultaneously. Dealing with qualitative and uncertain data, Fuzzy systems are used to cope with these conditions and they are used as the basis of this work. We use fuzzy VIKOR to model a hybrid solution to the hub location problem. Results are used by a genetic algorithm solution to successfully solve a number of problem instances. Furthermore, this method can be used to take into account more desired quantitative variables other than cost and time, like future market and potential customers easily.     

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 multicriteria p-facility median location problem on networks

In this paper we discuss the multicriteria p-facility median location problem on networks with positive and negative weights. We assume that the demand is located at the nodes and can be different for each criterion under consideration. The goal is to obtain the set of Pareto-optimal locations in the graph and the corresponding set of non-dominated objective values. To that end, we first characterize the linearity domains of the distance functions on the graph and compute the image of each linearity domain in the objective space. The lower envelope of a transformation of all these images then gives us the set of all non-dominated points in the objective space and its preimage corresponds to the set of all Pareto-optimal solutions on the graph. For the bicriteria 2-facility case we present a low order polynomial time algorithm. Also for the general case we propose an efficient algorithm, which is polynomial if the number of facilities and criteria is fixed.     

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.     

Multiple positive solutions to a three-point boundary value problem with p-Laplacian

Sufficient conditions are obtained that guarantee the existence of at least two positive solutions for the equation (g(u′(t)))′+a(t)f(u)=0 subject to boundary conditions, by a simple application of a new fixed-point theorem due to Avery and Henderson.     

Multiplicity results for a Neumann problem involving the p-Laplacian

In this paper, we establish some multiplicity results for the following Neumann problem:

     

The Cauchy problem for a class of pseudodifferential equations over p-adic field

In this paper, some classes much more general than the one in [N.M. Chuong, Yu.V. Egorov, A. Khrennikov, Y. Meyer, D. Mumford (Eds.), Harmonic, Wavelet and p-Adic Analysis, World Scientific, Singapore, 2007] of Cauchy problems for an interesting class of pseudodifferential equations over p-adic fields are studied. The used functions belong to mixed classes of real and p-adic functions. Even for p-adic partial differential equations such problems in such function spaces have not been discussed yet. The established mathematical foundation requires very complicated and very difficult proofs. Days after days, these equations occur increasingly in mathematical physics, quantum mechanics. Explicit solutions of such problems are very needed for specialists on applied mathematics, physics, and engineering.     

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.     

An eigenvalue Dirichlet problem involving the p-Laplacian with discontinuous nonlinearities

A multiplicity result for an eigenvalue Dirichlet problem involving the p-Laplacian with discontinuous nonlinearities is obtained. The proof is based on a three critical points theorem for nondifferentiable functionals.     

Up-to boundary regularity for a singular perturbation problem of p-Laplacian type

In this paper we are interested in establishing up-to boundary uniform estimates for the one phase singular perturbation problem involving a nonlinear singular/degenerate elliptic operator. Our main result states: if Ω⊂Rn is a C1,α domain, for some 0<α<1 and uε verifies

     

Infinitely many radial solutions for a p-Laplacian problem p-superlinear at the origin

We prove the existence of infinitely many radial solutions for a p-Laplacian Dirichlet problem which is p-superlinear at the origin. The main tool that we use is the shooting method. We extend for more general nonlinearities the results of J. Iaia in [J. Iaia, Radial solutions to a p-Laplacian Dirichlet problem, Appl. Anal. 58 (1995) 335-350]. Previous developments require a behavior of the nonlinearity at zero and infinity, while our main result only needs a condition of the nonlinearity at zero.     

Existence and iteration of positive solutions for a generalized right-focal boundary value problem with p-Laplacian operator

In the paper, we obtain the existence of positive solutions and establish a corresponding iterative scheme for the following third-order generalized right-focal boundary value problem with p-Laplacian operator:

     

On the Cauchy problem for the evolution p-Laplacian equations with gradient term and source

In this paper, the authors study the equation ut=div(|Du|^p−2Du)+|u|^q−1u−λl|Du| in RN with p>2. We first prove that for 1?l?p−1, the solution exists at least for a short time; then for , the existence and nonexistence of global (in time) solutions are studied in various situations.     

The limiting problem of the drift-diffusion-Poisson model with discontinuous p-n-junctions

In this paper, the authors consider the limiting problem of the drift-diffusion-Poisson model for semiconductors. Different from previous papers, the model considered involve some special doping profiles D which have the property that the function is allowed to have a jump-discontinuity and sign changing property but D² is required to be Lipschitz continuous. The existence, uniqueness and large-time asymptotic behavior of the global (in time) solutions are given.     

Robust weighted vertex p-center model considering uncertain data: An application to emergency management

This paper presents a generalized weighted vertex p-center (WVPC) model that represents uncertain nodal weights and edge lengths using prescribed intervals or ranges. The objective of the robust WVPC (RWVPC) model is to locate p facilities on a given set of candidate sites so as to minimize worst-case deviation in maximum weighted distance from the optimal solution. The RWVPC model is well-suited for locating urgent relief distribution centers (URDCs) in an emergency logistics system responding to quick-onset natural disasters in which precise estimates of relief demands from affected areas and travel times between URDCs and affected areas are not available. To reduce the computational complexity of solving the model, this work proposes a theorem that facilitates identification of the worst-case scenario for a given set of facility locations. Since the problem is NP-hard, a heuristic framework is developed to efficiently obtain robust solutions. Then, a specific implementation of the framework, based on simulated annealing, is developed to conduct numerical experiments. Experimental results show that the proposed heuristic is effective and efficient in obtaining robust solutions. We also examine the impact of the degree of data uncertainty on the selected performance measures and the tradeoff between solution quality and robustness. Additionally, this work applies the proposed RWVPC model to a real-world instance based on a massive earthquake that hit central Taiwan on September 21, 1999.     

An elliptic equation with perturbed p-Laplace operator

We consider an elliptic boundary value problem with perturbed p-Laplacian, p>1. The perturbation consists of a linear operator that dilates or compresses the argument of a function and is close to the identity. A weak existence theorem is obtained.     

On a superlinear elliptic p-Laplacian equation

We prove the existence of four solutions for the p-Laplacian equation