A graph theoretical bound for the p-median problem

The p-median problem is a minisium network location problem that seeks to find the optimal location of p centres in a network. In the present paper a graph-theoretical bound is developed for the problem. This bound is based on shortest spanning trees and arborescences and other graphical properties of the problem. It is shown that the graph-theoretical bound dominates a bound based on shortest distances.     

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.     

On the exponential cardinality of FDS for the ordered p-median problem

We study finite dominating sets (FDS) for the ordered median problem. This kind of problems allows to deal simultaneously with a large number of models. We show that there is no valid polynomial size FDS for the general multifacility version of this problem even on path networks.     

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.     

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 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.     

Complexity of local search for the p-median problem

We study the complexity of finding local minima for the p-median problem. The relationship between Swap local optima, 0–1 local saddle points, and classical Karush–Kuhn–Tucker conditions is presented. It is shown that the local search problems with some neighborhoods are tight PLS-complete. Moreover, the standard local descent algorithm takes exponential number of iterations in the worst case regardless of the tie-breaking and pivoting rules used. To illustrate this property, we present a family of instances where some local minima may be hard to find. Computational results with different pivoting rules for random and Euclidean test instances are discussed. These empirical results show that the standard local descent algorithm is polynomial in average for some pivoting rules.     

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.     

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.     

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 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.     

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.     

Minmax regret location–allocation problem on a network under uncertainty

We consider a robust location–allocation problem with uncertainty in demand coefficients. Specifically, for each demand point, only an interval estimate of its demand is known and we consider the problem of determining where to locate a new service when a given fraction of these demand points must be served by the utility. The optimal solution of this problem is determined by the “minimax regret” location, i.e., the point that minimizes the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. For the case where the demand points are vertices of a network we show that the robust location–allocation problem can be solved in O(min{p, n − p}n³m) time, where n is the number of demand points, p (p < n) is the fixed number of demand points that must be served by the new service and m is the number of edges of the network.     

The biobjective absolute center problem

This paper deals with the problem of determining the absolute center of a network, taking into account two objective functions. These functions consist of minimizing the maximum of the distances from any point on the network to the vertices, using two independent lengths on each edge. We propose an algorithm in polynomial time to obtain the non-dominated location points on the network, using the Kariv and Hakimi method (1979). This work was partially supported by project number 93/108 from the Dirección General de Universidades e Investigación del Gobierno de Canarias.     

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.     

The variable radius covering problem

In this paper we propose a covering problem where the covering radius of a facility is controlled by the decision-maker; the cost of achieving a certain covering distance is assumed to be a monotonically increasing function of the distance (i.e., it costs more to establish a facility with a greater covering radius). The problem is to cover all demand points at a minimum cost by finding optimal number, locations and coverage radii for the facilities. Both, the planar and discrete versions of the model are considered. Heuristic approaches are suggested for solving large problems in the plane. These methods were tested on a set of planar problems. Mathematical programming formulations are proposed for the discrete problem, and a solution approach is suggested and tested.     

Dynamic journeying under uncertainty

We introduce a journey planning problem in multi-modal transportation networks under uncertainty. The goal is to find a journey, possibly involving transfers between different transport services, from a given origin to a given destination within a specified time horizon. Due to uncertainty in travel times, the arrival times of transport services at public transport stops are modeled as random variables. If a transfer between two services is rendered unsuccessful, the commuter has to reconsider the remaining path to the destination. The problem is modeled as a Markov decision process in which states are defined as paths in the transport network. The main contribution is a backward induction method that generates an optimal policy for traversing the public transport network in terms of maximizing the probability of reaching the destination in time. By assuming history independence and independence of successful transfers between services we obtain approximate methods for the same problem. Analysis and numerical experiments suggest that while solving the path dependent model requires the enumeration of all paths from the origin to the destination, the proposed approximations may be useful for practical purposes due to their computational simplicity. In addition to on-time arrival probability, we show how travel and overdue costs can be taken into account, making the model applicable to freight transportation problems.     

The p-hub center allocation problem

The p-hub center problem is to locate p hubs and to allocate non-hub nodes to hub nodes such that the maximum travel time (or distance) between any origin–destination pair is minimized. We address the p-hub center allocation problem, a subproblem of the location problem, where hub locations are given. We present complexity results and IP formulations for several versions of the problem. We establish that some special cases are polynomially solvable.     

Location choices under quality uncertainty

We examine a linear city duopoly where firms choose their locations to maximize expected profits, uncertain about how consumers will assess the relative quality of their products. Equilibrium locations depend on the ratio of the expected quality superiority and the strength of horizontal differentiation. When this ratio is small, firms locate at opposite endpoints. As it becomes larger, agglomeration also emerges as an equilibrium with both firms choosing the same location within an interval around the center. Eventually, when the ratio is large enough, agglomeration becomes the only equilibrium and can occur at any point of the linear city.     

Programming under uncertainty: The complete problem

We define the complete problem of a two-stage linear programming under uncertainty, to be:

$$\begin{gathered} Minimize z(x) = E_\xi \{ cx + q^ + y^ + + q^ - y^ - \} \hfill \\ subject to Ax = b \hfill \\ Tx + Iy^ + + Iy^ - = \xi \hfill \\ x \geqq 0,y^ + \geqq 0,y^ - \geqq 0 \hfill \\ \end{gathered} $$