A Fast and Deterministic Approach to a Near Optimal Solution for the p-Median Problem

A Fast and Deterministic Approach to a Near Optimal Solution for the p-Median Problem

Xiang Li (East China Normal University, China), Christophe Claramunt (Naval Academy Research Institute, France), Xihui Zhang (University of North Alabama, USA) and Yingping Huang (University of North Alabama, USA)
DOI: 10.4018/joris.2012070101
OnDemand PDF Download:


Finding solutions for the p-median problem is one of the primary research issues in the field of location theory. Since the p-median problem has proved to be a NP-hard problem, several heuristic and approximation methods have been proposed to find near optimal solutions with acceptable computational time. This study introduces a computationally efficient and deterministic algorithm whose objective is to return a near optimal solution for the p-median problem. The merit of the proposed approach, called Relocation Median (RLM), lies in solving the p-median problem in superior computational time with a tiny percentage deviation from the optimal solution. This approach is especially relevant when the problem is enormous where, even when a heuristic method is applied, the computational time is quite high. RLM consists of two parts: The first part uses a greedy search method to find an initial solution; the second part sequentially substitutes medians in the initial solution with additional vertices to reduce the total travel cost. Experiments show that to solve the same p-median problem, the RLM approach can significantly shorten the computational time needed by a genetic algorithm based approach to obtain solutions with similar quality.
Article Preview


The p-median problem (PMP) has been extensively studied over the past years. It can be considered as one of the computational algorithm usually applied in location theory whose objective is to address the questions of what economic activities are located where and why. The objective of the p-median problem is to locate p medians that denote facilities in order to minimize the total travel cost for satisfying the demand of some customers at some given locations, hereafter considered as vertices, to their closest medians. Over the past few years, many location allocations of facilities have been formulated as instances of the PMP (e.g., Avella & Sassano, 2001; Avella & Sforza, 1999; Beasley, 1985; Berman, Krass, & Menezes, 2007; Church, 2003; Cooper, 1963). The PMP has proved to be a NP-hard problem (Kariv & Hakimi, 1979). Over the past years, a number of heuristic or approximation methods have been proposed to find near optimal solutions for a large-scale PMP with acceptable computational time, e.g., Lagrangean relaxation (Beasley, 1985; Christofides & Beasley, 1982; Cornuejols, Fisher, & Nemhauser, 1977), dual formulations (Gilmore & Gomory, 1961; Hanjoul & Peeters, 1985), branch-and-bound algorithms (Kuenne & Soland, 1972), simulated annealing (Murray & Church, 1996), tabu search (Brimberg & Mladenović, 1996), neighborhood search (Crainic, Gendreau, Hansen, & Mladenović, 2004; Hansen, Brimberg, Urosevic, & Mladenović, 2009), hybrid heuristic (Das, Hossain, & Gupta, 2010; Resende & Werneck, 2004), genetic algorithms (Alp, Erkut, & Drezner, 2003; Dibble & Densham, 1993; Hosage & Goodchild, 1986; Li & Yeh, 2005; Ye & Priebe, 2010). There are also other approaches to variants of PMP, such as capacitated PMP (Osman & Ahmadi, 2007; Sinha, 2009).

The research presented in this paper, instead of presenting a new approach producing more optimal solutions, introduces a fast and deterministic approach to a near optimal solution for the PMP. The approach has been applied to 40 PMPs taken from the OR Library (Beasley, 1990) with known optimal solutions, which are often used as a benchmark database for the p-median problem. Experimental results demonstrate that the average percentage deviation of the solutions produced by the approach is less than 2% from the optimal one. Additional experiments illustrate that, to solve the same p-median problem, the proposed approach can save more than 95% of the computational time needed by a genetic algorithm based approach without seriously compromising the quality of the emerging solutions.

The principle of the proposed approach and algorithm is briefly introduced below. First, a greedy search method is applied to find an initial optimal solution with p medians. Each median and its allocated vertices are saved in an allocation set. Then, in each allocation set, a screening procedure is applied to all vertices to search for a replacement of the current median to further reduce the total travel cost to the most extent. Finally, all the updated medians compose a final solution. The reminder of the paper is organized as follows. First, we introduce the formulation of the PMP. Then, we propose the fast and deterministic approach. Afterwards, a section evaluates the proposed approach and compares it with an existing genetic algorithm based approach with three datasets and finally, we conclude the paper and draws some perspectives.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing