连续时间的网络截流选址模型与算法——以防御性醉酒驾驶的拦截问题为例

科研管理 ›› 2012, Vol. 33 ›› Issue (11): 89-95.

连续时间的网络截流选址模型与算法——以防御性醉酒驾驶的拦截问题为例

朱华桂, 乔联宝

南京大学工程管理学院,江苏南京 210093

收稿日期:2012-08-06 修回日期:2012-09-28 出版日期:2012-11-27 发布日期:2012-11-21
基金资助:
国家自然科学基金项目(编号:71273127);教育部人文社科规划项目(编号:11YJA630222)。

Continuous time based network flow interception model and algorithm——A case study of preventive drunk driving interception problem

Zhu Huagui, Qiao Lianbao

School of Management and Engineering, Nanjing University, Nanjing 210093, China

Received:2012-08-06 Revised:2012-09-28 Online:2012-11-27 Published:2012-11-21

摘要/Abstract

摘要： 首先提出了连续时间的网络截流选址问题,并以保护整个道路交通网络为目标,建立了防御性醉酒驾驶拦截问题的模型。根据问题的特征,分别设计了基于时间的迭代改进算法和离散选址问题的拉格朗日启发式算法,并通过随机实例对算法进行了测试。结果表明:连续时间的同步拦截问题可以通过分离连续的时间变量和离散的选址变量的方法,多次求解覆盖问题而有效解决,并且迭代改进算法对时间的搜索性更强,从而能够用较少的迭代次数解决原问题。

关键词: 截流问题, 防御性选址, 算法, 连续时间

Abstract: A continuous time typed network flow interception problem has been proposed; a preventive drunk driving interception model has been developed with the goal for protecting entire traffic network. According to the characteristics of the problem, a time based iterative improved algorithm and Lagrange heuristic algorithm for discrete site selection problem are devised, respectively, they are applied to the random instances in order to test the performance. The computational result indicates that by separating the continuous time variable from the discrete site selection variable, the original problem could finally be resolved by solving a series of covering problems. The iterative improved algorithm is more powerful in time search, therefore the problem is able to solve in few iteration times.

Key words: flow interception problem, preventive site selection, algorithm, continuous time

中图分类号:

C934

朱华桂, 乔联宝. 连续时间的网络截流选址模型与算法——以防御性醉酒驾驶的拦截问题为例[J]. 科研管理, 2012, 33(11): 89-95.

Zhu Huagui, Qiao Lianbao. Continuous time based network flow interception model and algorithm——A case study of preventive drunk driving interception problem[J]. Science Research Management, 2012, 33(11): 89-95.

参考文献

[1] Hodgson M. J. The location of public facilities intermediate to the journey to work[J]. European Journal of Operational Research 1981, 6: 199-204.
[2] Hodgson M. J. A flow-capturing location-allocation model[J]. Geographical Analysis 1990, 22(3): 270-279.
[3] Berman O., Krass D., Xu C.W. Locating flow-intercepting facilities: New approaches and results[J]. Annals of Operations Research 1995, 60: 121-1143.
[4] Mirchandani P.B., Rebello R., Agnetis A. The inspection location problem in hazardous material transportation: some heuristics and bounds[J]. Information System & Operational Research 1995, 2(33): 100-113.
[5] Berman O., Krass D. Flow intercepting spatial interaction model: a new approach to optimal location of competitive facilities[J]. Location Science 1998, 6: 41-65.
[6] Hodgson M.J., Rosing K.E., Zhang J.J. Locating vehicle inspection stations to protect a transportation network[J]. Geographical Analysis 1996, 4(28): 299-314.
[7] Gendreau M., Laprote G., Parent I.Heuristics for the location of inspection stations on a network[J]. Naval Research Logistics 2000, 47: 287-303.
[8] Gzara F., Erkut E. A Lagrangian relaxation approach to large-scale flow interception problems[J]. European Journal of Operational Research 2009, 198: 405-411.
[9] Boccia M., Sforza A., Strle C. Flow intercepting facility location: problems, models and heuristics[J]. Journal of Mathematical Modelling and Algorithms 2009, 8: 35-79.
[10] Zeng W., Castillo I., Hodgson M.J. A generalized model for locating facilities on a network with flow-based demand[J]. Networks and Spatial Economics 2010, 10:579 611.
[11] 马满,杨超,胡丹丹.竞争环境中的截流选址与设计问题[J]. 工业工程与管理,2010,15(3):111-114.
[12] 胡丹丹,杨超.α-鲁棒随机截流选址问题的模型和算法[J].中国管理科学,2008,16(6):87-94.
[13] 马云峰,刘勇,杨超.一类带时间和容量约束的截流选址问题[J]. 武汉科技大学学报(自然科学版),2007,30(2):217-219.
[14] 杨珺,杨超,吴云.带危险度瓶颈限制的服务站截流选址一分配模型研究[J].数学物理学报,2007,27A(5):955-960.
[15] 杨珺,张敏,陈新.一类带服务半径的服务站截流选址一分配问题[J].系统工程理论与实践,2006(1):117-122.