Authors: F. Antonio Medrano*, University of California
Topics: Spatial Analysis & Modeling
Keywords: p-center, covering methods, exact algorigthm
Session Type: Paper
Start / End Time: 10:00 AM / 11:40 AM
Room: Studio 8, Marriott, 2nd Floor
Presentation File: No File Uploaded
The vertex p-Center problem consists of locating p facilities that cover all n demands in order to minimize the maximum distance between a demand and the facility that covers it. In other words, it is equivalent to finding the minimum coverage radius r and locations of p facilities capable of covering all demands. Originally formulated by Hakimi (1965), this problem is NP-Hard, and the standard formulation has proven to be particularly challenging for IP solvers on large problems. Thus, most solution approaches use heuristics or relaxations (Minieka 1970, Tansel et al. 1983, Mladenović et al. 2003, Elloumi et al. 2004). The complete p-Center problem extends the formulation to solve the for all p-values from 1 to N, where N is the number of nodes to cover. This provides a complete coverage trade-off curve between number of facilities and coverage radius.
This talk proposes an approach for solving the Complete Vertex p-Center Problem using an iterative location set covering approach with selecting only r-values that have the potential to be exact solutions. Experiments on a variety of data sets demonstrate that this new iterative covering method is faster than approaches using traditional p-Center formulations.