多类型需求流的截流选址问题研究和算法实现

运筹与管理 ›› 2011, Vol. 20 ›› Issue (6): 51-58.

多类型需求流的截流选址问题研究和算法实现

张曦¹, 杨超², 黄松²

1.武汉工程大学管理学院, 湖北武汉 430205;
2.华中科技大学管理学院, 湖北武汉 430074

收稿日期:2010-06-29 出版日期:2011-12-25
作者简介:张曦(1980-),女,河北南宫人,博士,讲师,研究方向为选址和网络优化等方面研究。
基金资助:
国家自然科学基金资助项目(70871044)

Model and Algorithm of FIP Location with Multi-type Demand Flows

ZHANG Xi¹, YANG Chao², HUANG Song²

1. Department of Management Science,Wuhan Institute of Technology, Wuhan 430074, China;
2. Department of Management Science, Huazhong University of Science and Technology, Wuhan 430074, China

Received:2010-06-29 Online:2011-12-25

摘要/Abstract

摘要： 本文研究了网络上固定的O-D对上存在不同类型的需求流的选址问题。在基本截流模型的基础上提出了多类型需求流多目标截流选址问题的模型,将模型转化为多目标模糊规划问题,运用混合遗传算法求解模型,最后给出了算例,并与分支定界法相比,证明了混合遗传算法可以有效的求解此模型。

关键词: 运筹学, 选址, 模糊规划, 算法

Abstract: We consider the location problem of different type demand flow on the origin and destination(O-D)pairs of network. Based on the basic flow interception problem(FIP)model, we give the multi-objective FIP location model with multi-type demand flows. The model is transformed into multi-objective fuzzy programming problem, and the hybrid genetic algorithm is introduced to solve the model. The computational experiments demonstrate the efficiency of our HGA.

Key words: operational research, location, fuzzy programming, algorithm

中图分类号:

O221

张曦, 杨超, 黄松. 多类型需求流的截流选址问题研究和算法实现[J]. 运筹与管理, 2011, 20(6): 51-58.

ZHANG Xi, YANG Chao, HUANG Song. Model and Algorithm of FIP Location with Multi-type Demand Flows[J]. Operations Research and Management Science, 2011, 20(6): 51-58.

参考文献

[1] Berman O, Huang R B. The minisum multipurpose trip location problem on networks[J]. Transportation science, 2007,41: 500-515.
[2] Gzara F, Erkut E. A lagerangian relaxation approach to large-scale flow interception problems[J]. European Journal of Operational Research, 2008, 24(8): 1-7.
[3] Boccia M, Sforza A, Sterle C. Flow intercepting facility location: problems, models and heuristics[J]. J Math Model Algor, 20098: 35-79.
[4] Berman O, Fouska N, Larson R C. Optimal location of discretionary service facilities[J]. Transportation Science, 1992, 26(3): 201-211.
[5] Berman O, Hodgson J, Krass D. Flow interception problem. in: drezner, Z(Ed.), Facility Location:A Survey of Apllication and Methods[M]. Springer, Berlin, 1995. 389-426.
[6] 杨珺,张敏,陈新.一类带服务半径的服务站截流选址——分配问题[J].系统工程理论与实践,2006,45(1):117-122.
[7] Berman O, Bertsimas D, Larson R C. Locating discretionary service facility. II: minimizing inconvenience[J]. Operations Research, 1995, 43(4):623-632.
[8] Wu T H, Lin J N. Solving the competitive discretionary service facility location problem[J]. European Journal of Operational Research, 2003, 144(2): 366-378.
[9] Berman O. Flow intercepting spatial interaction model: a new approach to optimal location of competitive facilities[J]. Location science, 1998, 6: 41-65.
[10] Yang J, Zhang M, He B, Yang C. Bi-level programming model and hybrid genetic algorithm for flow interception problem with customer choice[J]. Computers and Mathematics with Applications, 2009, 57(7): 1985-1994.
[11] Huynh N, Chiu Y C, Mahmassani H S. Finding near-optimal locations for variable message signs for real-time network traffic management[J]. J. Transp. Res. Board, 2003, 1856: 34-53.
[12] Yang H, Yang C, Liping G. Models and algorithms for the screen line-based trafic-counting location problems[J]. Comput. Oper. Res, 2006, 33(3): 836-858.
[13] Uno T, Katagiri H. Single- and multi-objective defensive location problems on a network[J]. European Journal of Operational Research, 2008, 188(1): 76-84.
[14] Cantieni R G, Iannaccone G, Barakat C, et al. Reformulating the monitor placement problem: optimal network-wide sampling[C]. Information sciences and systems. In: Proceedings of CoNEXT, Lisbon, December, 2006
[15] Suh K, Guo Y, Kurose J, et al. Locating network monitors: complexity, heuristics, and coverage[J]. Comput. Commun, 2006, 29(10): 1564-1577.
[16] Hu C, Liu B, Liu Z, et al. Optimal deployment of distributed passivemeasurement monitors[C]. In: International Conference on Communication, ICC’06,IEEE, Piscataway, 2006, 2: 621-626.
[17] Boyles S D, Waller S T. Optimal information location for adaptive routing[J]. Networks and Spatial Economic, 2009, 67(10): 108-130.
[18] Yang J, Yang C. Model and algorithm for the pq-FIP with two kinds of facilities[C]. In: Proceedings of 2004 Inter-national Conference on Management Science & Engineering, Harbin: Harbin Institute of Technology Press, 2004. 487-491.
[19] 摩特·爱尔玛拉巴.运筹学手册[M].上海,上海科学技术出版社,1987.
[20] Bellman R, Zadeh L. Decision making in a fuzzy environment, management[J]. Science, 1970, 16(6): 141-146.
[21] 玄光男,程润伟.遗传算法与工程优化[M].北京,清华大学出版社,2004.
[22] Mirchandani P B, Rebello R, Agnetis A. The inspection station location problem in hazardous materials transportation: some heuristics and bound[J]. INFOR, 1995, 33: 100-113.