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

Xiang Li, Christophe Claramunt, Xihui Zhang and Yingping Huang
Additional contact information
Xiang Li: East China Normal University, China
Christophe Claramunt: Naval Academy Research Institute, France
Xihui Zhang: University of North Alabama, USA
Yingping Huang: University of North Alabama, USA

International Journal of Operations Research and Information Systems (IJORIS), 2012, vol. 3, issue 3, 1-14

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

Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/joris.2012070101 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:joris0:v:3:y:2012:i:3:p:1-14

Access Statistics for this article

International Journal of Operations Research and Information Systems (IJORIS) is currently edited by John Wang

More articles in International Journal of Operations Research and Information Systems (IJORIS) from IGI Global
Bibliographic data for series maintained by Journal Editor ().