|
|||||
|
|
p-Median and p-dispersion problems: A bi-criteria analysis |
|
| Affiliation: | 1. SAS Institute, Inc., 100 SAS Campus Drive, Cary, NC 27513, United States;2. Industrial and Systems Engineering, North Carolina State University, Raleigh, NC 27695, United States;1. School of Sciences, Information Technology and Engineering, Federation University Australia, Mt Helen, VIC 3353, Australia;2. Research School of Engineering, Australian National University, Canberra, Australia;1. Department of Computing, Imperial College London, United Kingdom;2. Department of Information Studies, University College London, United Kingdom;1. Departamento de Ciencias de la Computación, Universidad Rey Juan Carlos, Spain;2. Network Evolution Research Department, AT&T Labs Research, 200 S. Laurel Avenue, Room A5-1F34, Middletown, NJ 07748, USA;3. OptTek Systems, Inc., Boulder, CO, USA;4. Departamento de Estadística e Investigación Operativa, Universidad de Valencia, Spain |
| Abstract: | Given a collection of n locations and a symmetric measure of distance (difference) between each pair of locations, we seek to identify (select) a subset of p locations so as to achieve two distinct objectives. The first objective is to use the selected locations as centers (medians) of p groups that would partition the entire collection and minimize the total distance between the locations and their respective group medians. The second objective is to maximize the minimum distance (diversity) among the selected locations themselves. We study this problem as a multi-objective optimization problem and propose an iterative algorithm to obtain its non-dominated frontier. At each iteration we construct and solve a 0–1 integer programming problem. Through a computational experiment we show that this algorithm is computationally effective for small to medium size instances of the problem. We also propose a Lagrangian heuristic algorithm for solving larger instances of this problem. |
| Keywords: | Location theory Max–min diversity Integer programming Lagrangian heuristic |
| 本文献已被 ScienceDirect 等数据库收录！ | |