服务水平保证下应急抢修点选址模型及求解算法研究

中国管理科学 ›› 2014, Vol. 22 ›› Issue (3): 34-41.

服务水平保证下应急抢修点选址模型及求解算法研究

余鹏, 隽志才

上海交通大学安泰经济与管理学院, 上海 200052

收稿日期:2011-10-21 修回日期:2013-01-04 出版日期:2014-03-20 发布日期:2014-03-19
作者简介:余鹏（1975- ），男（汉族），湖北人，上海交通大学安泰经济管理学院博士生，研究方向：物流管理、运输系统规划与管理.
基金资助:
国家自然科学基金资助项目（50978163）

Service Level Guaranteed Emergency Repair Station Location Model and Solution

YU Peng, JUAN Zhi-cai

Antai College of Economics & Management, Shanghai Jiao Tong University, Shanghai 200052, Chian

Received:2011-10-21 Revised:2013-01-04 Online:2014-03-20 Published:2014-03-19

摘要/Abstract

摘要： 本文研究了一类故障率低但重要性较高设备的应急抢修点选址问题。设备的故障发生过程和从应急抢修点到故障设备的通行时间是随机的，每个设备被分配给一个应急抢修点进行抢修，并且整个应急抢修系统的服务水平要大于给定标准。本文以应急抢修点总开设成本最小作为目标，同时考虑了设备覆盖约束、抢修分配关系约束和抢修系统服务水平约束，在合理的假设下证明设备发生故障且应急抢修小组迟到的总次数服从泊松分布，最终将应急抢修点选址问题描述为一个0-1整数规划模型。通过对模型中的覆盖约束和抢修系统服务水平约束进行松弛，设计了相应的拉格朗日启发式算法。最后通过对大量随机算例进行计算，证明了该模型和算法的有效性。

关键词: 应急抢修点, 设施选址, 服务水平保证, 拉格朗日松弛法

Abstract: The problem of emergency repair station location for a kind of valuable equipments with low failure rate is investigated in this paper.Considering this problem, equipment failure frequencies and the travel time from emergency station to equipment are stochastic, and each equipment should be assigned to an emergency repair station, and the service level of entire emergency repair system should be above some standard level. The distribution of the total times of emergency repair teams be late when equipment be failed has been derived under several assumptions. The problem of emergency repair station location is characterized as 0-1 integer programming model, with minimization the whole setup cost of emergency repair stations as objective function, and equipments been covered, emergency repair assignment relation, entire system's service level as constraints. A lagrangian relaxation heuristic algorithm is proposed to solve the model by relaxing several constraints. The effective of the model and algorithm has been proved by calculating a large number of random examples.

Key words: emergency repair station, facility location, service level guarantee, lagrangian relaxation

中图分类号:

余鹏, 隽志才. 服务水平保证下应急抢修点选址模型及求解算法研究[J]. 中国管理科学, 2014, 22(3): 34-41.

YU Peng, JUAN Zhi-cai. Service Level Guaranteed Emergency Repair Station Location Model and Solution[J]. Chinese Journal of Management Science, 2014, 22(3): 34-41.

参考文献

[1] Brotcorne L, Laporte G, Semet F. Ambulance location and relocation models[J]. European Journal of Operational Research, 2003, 147(3): 451-463.

[2] Berman O, Drezner Z, Wang Jiamin, et al. The minimax and maximin location problems on a network with uniform distributed weights[J]. ⅡE Transactions, 2003, 35(11): 1017-1025.

[3] Chang M S, Tseng Y L, Chen Jingwen. A scenario planning approach for the flood emergency logistics preparation problem under uncertainty[J]. Transportation Re-search Part E: logistics and Transpor-tation Review, 2007, 43(6): 737-754.

[4] Alsalloum O I, Rand G K. Extensions to emergency vehicle location models[J]. Computers & Operations Research, 2006, 33(9): 2725-2743.

[5] Gendreau M, Laporte G, Semet F. The maximal expected coverage relocation problem for emergency vehicles[J]. Jour-nal of the Operational Research Society, 2005, 57(1): 22-28.

[6] Ingolfsson A, Budge S, Erkut E. Optimal ambulance location with random delays and travel times[J]. Health Care Management Science, 2008, 11(3): 262-274.

[7] Rawls C G, Turnquist M A. Preposi-tioning of emergency supplies for dis-aster response[J]. Transportation Re-search Part B: Methodological, 2010, 44(4), 521-534.

[8] Ball M O, Lin Fengling. A reliability model applied to emergency service vehicle location[J]. Operations Research, 1993, 41(1): 18-36.

[9] Beraldi P, Bruni M E. A probabilistic model applied to emergency service vehicle location[J]. European Journal of Operational Research, 2009, 196(1): 323——331.

[10] 陈志宗, 尤建新. 重大突发事件应急救援设施选址的多目标决策模型[J]. 管理科学, 2006, 19(4): 10-14.

[11] 张玲, 黄钧. 基于场景分析的应急资源布局模型研究[J]. 中国管理科学, 2008, 16(10), 164-167.

[12] Heung-Suk H. A stochastic set-covering location model for both ameliorating and deteriorating items[J]. Computers & In-dustrial Engineering, 2004, 46(2): 313-319.

[13] Nozick L K. The fixed charge facility location problem with coverage restric-tions[J]. Transportation Research Part E: Logistics and Transportation Review, 2001, 37(4): 281-296.

[14] Beraldi P, Bruni M E, Conforti D. Designing robust emergency medical ser-vice via stochastic programming[J]. European Journal of Operational Research, 2004, 158(1): 183-193.

[15] Lecluyse C, Van Woensel T, Peremans H. Vehicle routing with stochastic time-dependent travel times[J]. 4OR: A Quarterly Journal of Operations Research, 2009, 7(4): 363——377.

[16] 陈琨, 于雷. 基于对数正态和分布的路径行程时间可靠性模型[J]. 北京交通大学学报, 2009, 33(3): 35-39.

[17] 贺国芳, 孙芳. 现场可修系统的可靠性数据处理[J]. 北京航天航空大学学报, 1995, 21(4): 66-71.

[18] Ross S M. 应用随机过程—概率模型导论[M]. 北京:人民邮电出版社, 2007.

[19] Fisher M L. The Lagrangian relaxation method for solving integer programming problems[J]. Management science, 1981, 20(1): 1-18.

[20] Fisher M L. An applications oriented guide to Lagrangian relaxation[J]. In-terfaces, 1985, 20(1): 10-21.

[21] Daskin M S. Network and discrete loca-tion: models, algorithms, and applica-tions[M]. New York: Wiley, 1995.

[22] Snyder L V, Daskin M S. Reliability models for facility location: The expect-ed failure cost case[J]. Transportation Science, 2005, 39(3): 400-416.

[23] Zhu Zhanguo, Chu Fang, Sun Linyan. The capacitated plant location problem with customers and suppliers matching[J]. Transportation Research Part E: Logistics and Transportation Review, 2010, 46(3): 469-480.

[24] Wang S H. An improved stepsize of the subgradient algorithm for solving the lagrangian relaxation problem[J]. Computers & Electrical Engineering, 2003, 29(1): 245-249.