A GENERAL CONSTRUCT FOR THE ZONALLY CONSTRAINED P-MEDIAN PROBLEM

被引:6
作者
GERRARD, RA [1 ]
CHURCH, RL [1 ]
机构
[1] UNIV CALIF SANTA BARBARA,NATL CTR GEOG INFORMAT & ANAL,SANTA BARBARA,CA 93106
关键词
D O I
10.1068/b220213
中图分类号
X [环境科学、安全科学];
学科分类号
08 ; 0830 ;
摘要
The well-known p-median location model is designed to site p facilities with respect to population centers such that the average travel distance of facility users is minimized. Many locational applications would benefit from a median problem that distributes, according to the discretion of the model user, some or all of the p facilities among defined zones. The notion of this 'zonally constrained' p-median can be defined as: locate p facilities to achieve the minimum average user distance while ensuring that (in those zones with such requirements) each zone receives at least its allotted minimum number of facilities and no more than its allotted maximum number of facilities. Authors of three recent articles have defined subsets of this problem but have not developed a completely general form. Previous work falls short in one or more of the following respects: (I)defining a minimum facility limit for zones other than one, (2) including any kind of maximum facility limit for zones, (3) allowing demand to be assigned across zonal boundaries, and (4) allowing zones to overlap such that an eligible site for a facility can be a member of more than one zone. In this paper we present an integer-linear programming formulation that generalizes the concept of the zonally constrained p-median problem by incorporating properties (1)-(4) above. We denote this formulation ZOMP (zonal constraints with overlap for the median problem). A solution approach based on Lagrangian relaxation is proposed along with computational results. In addition, comparative computational results using mixed integer programming are offered. Our results are mostly derived from a computationally challenging application, unique to ZOMP, in which we generate a complete rank-ordered list of close to optimal solutions to the p-median problem.
引用
收藏
页码:213 / 236
页数:24
相关论文
共 50 条
[31]   An effective VNS for the capacitated p-median problem [J].
Fleszar, K. ;
Hindi, K. S. .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 191 (03) :612-622
[32]   An Efficient Genetic Algorithm for the p-Median Problem [J].
Osman Alp ;
Erhan Erkut ;
Zvi Drezner .
Annals of Operations Research, 2003, 122 :21-42
[33]   The connected p-median problem on block graphs [J].
Chang, Shun-Chieh ;
Yen, William Chung-Kung ;
Wang, Yue-Li ;
Liu, Jia-Jie .
OPTIMIZATION LETTERS, 2016, 10 (06) :1191-1201
[34]   A new heuristic approach for the P-median problem [J].
Dai, Z ;
Cheung, TY .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1997, 48 (09) :950-960
[35]   The Connected P-Median Problem on Cactus Graphs [J].
Bai, Chunsong ;
Zhou, Jianjie ;
Liang, Zuosong .
COMPUTATIONAL INTELLIGENCE AND NEUROSCIENCE, 2021, 2021
[36]   A dynamic programming heuristic for the P-median problem [J].
Hribar, M ;
Daskin, MS .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1997, 101 (03) :499-508
[37]   The dynamic p-median problem with mobile facilities [J].
Guden, Huseyin ;
Sural, Haldun .
COMPUTERS & INDUSTRIAL ENGINEERING, 2019, 135 :615-627
[38]   Complexity of local search for the p-median problem [J].
Alekseeva, Ekaterina ;
Kochetov, Yuri ;
Plyasunov, Alexander .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 191 (03) :736-752
[39]   Analysis of aggregation errors for the p-median problem [J].
Erkut, E ;
Bozkaya, B .
COMPUTERS & OPERATIONS RESEARCH, 1999, 26 (10-11) :1075-1096
[40]   A bionomic approach to the capacitated p-median problem [J].
Maniezzo, V ;
Mingozzi, A ;
Baldacci, R .
JOURNAL OF HEURISTICS, 1998, 4 (03) :263-280