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

Introduction

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.