带投资约束且p不确定的推广p-中位问题

运筹学学报 ›› 2013, Vol. 17 ›› Issue (4): 69-79.

带投资约束且p不确定的推广p-中位问题

蒋建林^1,*, 李雪¹, ASSANI Saeed¹, 吴仆¹, 王璨璨¹

1. 南京航空航天大学理学院，南京 211100;

出版日期:2013-12-15 发布日期:2013-12-15
通讯作者: 蒋建林 E-mail:jiangjianlin_nju@yahoo.com
基金资助:
国家自然科学基金 (No. 11101211)，江苏省自然科学基金 (No. BK2011719)，中央高校基本科研业务费专项资金 (No. NZ2012306)，第46批留学回国人员科研启动基金

An extended p-median problem with investment constraint and uncertain p

JIANG Jianlin^1,*, LI Xue¹, ASSANI Saeed¹, WU Pu¹, WANG Cancan¹

1. College of Science, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China

Online:2013-12-15 Published:2013-12-15

摘要/Abstract

摘要： p-中位问题是设施选址中的一个经典模型，在交通、物流等领域有着广泛应用. 在经典p-中位问题的基础上提出一种p不确定的推广p-中位问题，并且加上总投资约束，使得此推广模型更加实用. 针对此推广模型，提出三种启发式算法：简单启发式算法、变邻域搜索算法和改进的遗传算法. 数值实验结果表明变邻域搜索算法和改进的遗传算法在求解此推广模型时是有效的.

关键词: 运筹学, 设施选址, 推广p-中位问题, 变邻域搜索算法, 改进遗传算法

Abstract: p-median problem is a classical model in facility location and it has vast applications in related areas such as transportation and logistics. An extended p-median problem is investigated in this paper, in which the number of facilities to be located is uncertain and an investment constraint is considered. This makes the extended problem more applicable in the real lifes. Three heuristics are proposed for solving this extended p-median problem: the first is a simple heuristic algorithm; the second is a variable neighborhood search algorithm; and the third is an improved genetic algorithm. Experimental results show that the variable neighborhood search algorithm and the improved genetic algorithm are efficient for solving this problem.

Key words: operations research, facility location, extended p-median problem, variable neighborhood search algorithm, improved genetic algorithm

中图分类号:

O221.4

蒋建林, 李雪, ASSANI Saeed, 吴仆, 王璨璨. 带投资约束且p不确定的推广p-中位问题[J]. 运筹学学报, 2013, 17(4): 69-79.

JIANG Jianlin, LI Xue, ASSANI Saeed, WU Pu, WANG Cancan. An extended p-median problem with investment constraint and uncertain p[J]. Operations Research Transactions, 2013, 17(4): 69-79.

参考文献

Berman O, Drezner Z. The p-median problem under uncertainty [J]. European Journal of Operational Research, 2008, 189: 19-30.

Elloumi S. A tighter formulation of the p-median problem [J]. Journal of Combinatorial Optimization, 2010, 19(1): 69-83.

Fleszar K, Hindi K S. An effective VNS for the capacitated p-median problem [J]. European Journal of Operational Research, 2008, 191(3): 612-622.

Garcia S, Labbe M, Mar A. Solving large p-median problems with a radius formulation [J]. Informs Journal on Computing, 2011, 23(4): 546-556.

Mladenovic N, Brimberg J, Hansen P, et al. The p-median problem: a survey of metaheuristic approaches [J]. European Journal of Operational Research, 2007, 179: 927-939.

Hakimi S. Optimum location of switching centers and the absolute centers and medians of a graph [J]. Operations Research, 1964, 12: 450-459.

Hakimi S. Optimum location of switching centers in a communications network and some related graph theoretic problems [J]. Operations Research, 1965, 13: 462-475.

Kariv O, Hakimi S L. An algorithmic approach to network location problems [J]. SIAM Journal on Applied Mathematics, 1979, 37: 539-560.

Kuehn A A, Hamburger M J. A heuristic program for locating warehouse [J]. Management Science, 1963, 9(4): 643-666.

Mladenovic N, Hansen P. Variable neighborhood search [J]. Computers and Operational Research, 2007, 24: 1097-1100.

Hansen P, Mladenovic N. Variable neighborhood search: principles and applications [J]. European Journal of Operational Research, 2001, 130: 449-579.

Garcia-Lopez F, Melian-Batista B, Jose A, et al. The parallel variable neighborhood search~for the p-median problem [J]. Journal of Heuristic, 2002, 8: 375-388.

Baker J. Adaptive selection methods for genetic algorithms [C]// Proceedings of the First International Conference on Genetic Algorithm, Hillsdale: Lawrence Erlbaum Associates, 1985, 100-111.

王宁，刘黎明，刘玲玲. 混沌遗传算法 [J]. 运筹学学报, 2001, 5(3): 1-10.

黄晓霞. 随机环境下资金预算问题的机会约束整数规划模型 [J]. 运筹学学报，2006, 10(3): 59-65.

雷英杰，张善文，李续武等. MATLAB 遗传算法工具箱及应用 [M]. 西安：西安电子科技大学出版社, 2005: 74-76.

Beasley J E. Lagrangean heuristics for location problems [J]. European Journal of Operational Research, 1993, 65: 383-399.

Beasley J E. Lagrangean heuristics for location problems [J]. European Journal of Operational Research, 1993, 65: 383-399.

[1]	杨沐明, 黄亚魁, 戴彧虹. 一类多商品设施选址问题的基于线性松弛解的启发式方法[J]. 运筹学学报, 2019, 23(3): 15-26.
[2]	姜燕君, 徐大川, 张冬梅. 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018, 22(3): 49-58.
[3]	安邦, 程朋. 基于分支割平面的一类无容量限制设施选址问题求解算法[J]. 运筹学学报, 2015, 19(4): 1-13.
[4]	张惠珍, 魏欣, 马良. 求解无容量设施选址问题的半拉格朗日松弛新方法[J]. 运筹学学报, 2015, 19(4): 37-47.
[5]	王颖, 王凤敏, 徐大川, 徐文青. 带次模惩罚的优先设施选址问题的近似算法[J]. 运筹学学报, 2015, 19(2): 1-14.
[6]	徐大川, 万玮, 吴晨晨, 徐文青. 随机容错设施选址问题的原始-对偶近似算法[J]. 运筹学学报, 2014, 18(2): 17-28.
[7]	柏庆国, 徐健腾, 张玉忠, 徐贤浩. 带时变生产成本的易变质经济批量模型的最优策略分析[J]. 运筹学学报, 2013, 17(4): 109-122.
[8]	李改弟，王真，吴裕林. 带有惩罚和软容量约束的下界设施选址问题的双标准近似算法研究[J]. 运筹学学报, 2013, 17(1): 117-126.
[9]	邵国培，徐学文，刘奇志，何俊. 军事运筹学的过去、现在和未来[J]. 运筹学学报, 2013, 17(1): 10-16.
[10]	刘旭旺, 汪定伟. 博弈论视角的多属性逆向拍卖评标行为研究[J]. 运筹学学报, 2012, 16(4): 11-20.
[11]	中国运筹学会. 中国运筹学发展研究报告[J]. 运筹学学报, 2012, 16(3): 1-48.
[12]	徐健腾, 张玉忠, 柏庆国. 多供应商多零售商下经济批量问题的多项式时间算法研究[J]. 运筹学学报, 2011, 15(4): 102-114.
[13]	张丽丽, 李建宇, 李兴斯. 全局优化问题的一类积分型最优性条件 (英)[J]. 运筹学学报, 2011, 15(1): 1-10.
[14]	刘浩, 钱小燕, 倪勤. 解非线性单调方程组的投影自调比对称秩1拟牛顿法[J]. 运筹学学报, 2010, 14(3): 64-72.