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

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

CLC Number:

C934

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.

References

[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.