最小最大后悔准则下新增设施选址策略研究

doi:10.12005/orms.2021.0139

运筹与管理 ›› 2021, Vol. 30 ›› Issue (5): 15-20.DOI: 10.12005/orms.2021.0139

最小最大后悔准则下新增设施选址策略研究

于江霞¹, 赵阳¹, 罗太波¹, 李红梅²

1.西安电子科技大学经济与管理学院,陕西西安 710126;
2.西北大学经济管理学院,陕西西安 710127

收稿日期:2019-08-15 出版日期:2021-05-25
通讯作者: 李红梅(1989-),女,四川广元人,副教授,博士,研究方向:应急管理。
作者简介:于江霞(1976-),女,山东潍坊人,副教授,博士,研究方向:系统评估与优化;赵阳(1995-),男,河南许昌人,硕士研究生,研究方向:供应链管理;罗太波(1989-),男,江西南康人,讲师,博士,研究方向:调度优化。
基金资助:
教育部人文社科项目(18YJC630114,20YJAZH123);国家自然科学基金(71701162);陕西省自然科学基金(2019JQ-079,2019JQ-154,2020JM-211);中国博士后科学基金(2017M613192);教育部基本科研业务费资助项目(JB210603);西安市科技计划项目(20RKX0047)

The Study on New Facility Location Strategy under Minmax Regret Criterion

YU Jiang-xia¹, ZHAO Yang¹, LUO Tai-bo¹, LI Hong-mei²

1. School of Economics and Management, Xidian University, Xi'an 710126, China;
2. School of Economics and Management, Northwest University, Xi'an 710127, China

Received:2019-08-15 Online:2021-05-25

摘要/Abstract

摘要： 基于新增设施选址问题,考虑网络节点权重不确定性,以设施中最大负荷量最小为目标,提出最小最大后悔准则下的新增设施选址问题。在网络节点权重确定时,通过证明将网络图中无穷多个备选点离散为有限个设施候选点,设计了时间复杂度为O(mn²)的多项式算法;在节点权重为区间值时,通过分析最大后悔值对应的最坏情境权重结构,进而确定最大后悔值最小的选址,提出时间复杂度为O(2ⁿm²n³)的求解算法;最后给出数值算例。

关键词: 设施选址, 最大负荷量, 最小最大后悔值, 算法设计

Abstract: In this paper, we consider the new facility location problem in a general network with positive edge lengths and interval vertex weights. There are some facilities in the network already, and a new facility should be located so that the maximum load of all the facilities is minimized. When the vertex weights are determined, the network graph can be discretized into finite facility candidate points, and a polynomial algorithm with a time complexity of is designed. When the vertex weights are given as interval values, a particular assignment of a weight to each vertex is called a scenario. The problem requires that a point should be determined as the new facility location on the graph, such that the maximum regret of the objective function for all possible scenarios is minimized. By analyzing the structure of the worst scenarios corresponding to the maximum regret value, an algorithm with a time complexity of is proposed to solve the problem. Finally, a numerical example is given.

Key words: facility location, maximum load, minmax regret, algorithm design

中图分类号:

O224
TP399

于江霞, 赵阳, 罗太波, 李红梅. 最小最大后悔准则下新增设施选址策略研究[J]. 运筹与管理, 2021, 30(5): 15-20.

YU Jiang-xia, ZHAO Yang, LUO Tai-bo, LI Hong-mei. The Study on New Facility Location Strategy under Minmax Regret Criterion[J]. Operations Research and Management Science, 2021, 30(5): 15-20.

参考文献

[1] Chen R. Conditional minisum and minimax location-allocation problems in euclidean space[J]. Transportation Science, 1988, 22(2): 157-160.
[2] Berman O, Drezner Z. A new formulation for the conditional p-median and p-center problems[J]. Operations Research Letters, 2008, 36(4): 481-483.
[3] Chen D, Chen R. A relaxation-based algorithm for solving the conditional p-center problem[J]. Operations Research Letters, 2010, 38(3): 215-217.
[4] Fernández J, Pelegrin B, Plastria F, Tóth B. Solving a Huff-like competitive location and design model for profit maximization in the plane[J]. European Journal of Operational Research, 2007, 179(3): 1274-1287.
[5] Blanquero R, Carrizosa E, Nogales-Gómez A, Plastria F. Single-facility huff location problems on networks[J]. Annals of Operations Research, 2014, 222(1): 175-195.
[6] Grohmann S, Uroševic D, Carrizosa E, Mladenovic N. Solving multifacility huff location models on networks using metaheuristic and exact approaches[J]. Computers & Operations Research, 2017, 78(C): 537-546.
[7] Marianov V, Eiselt H. On agglomeration in competitive location models[J]. Annals of Operations Research, 2016, 246: 31-55.
[8] Farahani R, Fallah S, Ruiz R, Hosseini S, Asgari N. OR models in urban service facility location: a critical review of applications and future developments[J]. European Journal of Operational Research, 2019, 276(1): 1-27.
[9] Yu H I, Lin T C, Wang B F. Improved algorithms for the minmax-regret 1-center and 1-median problems[J]. ACM Transactions on Algorithms, 2008, 4(3): 1-27.
[10] Averbakh I, Berman O. Minmax regret median location on a network under uncertainty[J]. INFORMS Journal on Computing, 2000, 12(2): 104-110.
[11] Li H, Luo T, Xu Y, Xu J. Minimax regret vertex centdian location problem in general dynamic networks[J]. Omega, 2018, 75: 87-96.
[12] Berman O, Wang J. The minmax regret gradual covering location problem on a network with incomplete information of demand weights[J]. European Journal of Operational Research, 2011, 208(3): 233-238.
[13] Drezner T. Location of retail facilities under conditions of uncertainty[J]. Annals of Operations Research, 2009, 167(1): 107-120.
[14] Arumugam G P, Augustine J, Golin M J, et al. Minmax regret k-sink location on a dynamic path network with uniform capacities[J]. Algorithmica, 2019, 81(9): 3534-3585.
[15] Wang S, Chen Z, Liu T. Distributionally robust hub location[J]. Transportation Science, 2020, 54(5): 1189-1210.
[16] Sarhadi H, Naoum-Sawaya J, Verma M. A robust optimization approach to locating and stockpiling marine oil-spill response facilities[J]. Transportation Research Part E, 2020, 141: 102005.
[17] Cheng C, Adulyasak Y, Rousseau L. Robust facility location under demand uncertainty and facility disruptions[J]. Omega, 2021, https://doi.org/10.1016/j.omega.2021.102429, In press.

最小最大后悔准则下新增设施选址策略研究

The Study on New Facility Location Strategy under Minmax Regret Criterion

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈煜婷, 张惠珍. 双层级医疗设施选址问题及禁忌搜索算法[J]. 运筹与管理, 2021, 30(9): 56-63.
[2]	于冬梅, 高雷阜, 赵世杰. 考虑应急设施中断风险与防御的可靠性选址模型研究[J]. 运筹与管理, 2020, 29(9): 53-61.
[3]	吴晨晨, 王丽, 徐春明, 徐大川. 鲁棒动态设施选址问题的近似算法[J]. 运筹与管理, 2020, 29(5): 61-66.
[4]	郭换换, 王飞跃, 裴甲坤, 杨宸宇. 化工园区应急设施区间规划选址模型研究[J]. 运筹与管理, 2020, 29(5): 67-73.
[5]	张苏, 吴晨晨, 蒋建林, 吕一兵. 连续设施选址:模型、方法与应用[J]. 运筹与管理, 2020, 29(5): 84-95.
[6]	李海君, 张耀文, 杨月巧. 考虑回收-补偿约束的卫星城镇生活垃圾中转站选址研究[J]. 运筹与管理, 2020, 29(4): 30-35.
[7]	宋艳, 滕辰妹. 基于现存设施布局的设施选址:应对恐怖袭击[J]. 运筹与管理, 2019, 28(10): 5-12.
[8]	何永梅, 宁爱兵, 彭大江, 尚春剑, 张惠珍. 无容量限制设施选址问题的降阶回溯算法[J]. 运筹与管理, 2018, 27(9): 17-21.
[9]	彭春, 李金林, 冉伦, 王珊珊. 需求不确定下应急医疗服务站鲁棒配置模型与算法[J]. 运筹与管理, 2017, 26(9): 21-28.
[10]	刘慧, 杨超. 需求不确定的服务设施网络设计模型鲁棒性研究[J]. 运筹与管理, 2016, 25(1): 117-125.
[11]	申瑞玲, 霍佳震, 王茜. 竞争环境下截流问题的选址-价格模型[J]. 运筹与管理, 2015, 24(4): 122-127.
[12]	周愉峰, 马祖军, 王恪铭. 有容量限制的可靠性固定费用选址问题[J]. 运筹与管理, 2015, 24(3): 6-13.
[13]	付德强, 陈煜舟, 万晓榆. 自然灾害风险下区域应急储备设施选址可靠性研究[J]. 运筹与管理, 2015, 24(3): 14-19.
[14]	申瑞玲, 霍佳震. 竞争环境下截流设施选址问题[J]. 运筹与管理, 2013, 22(3): 97-101.
[15]	葛春景, 王霞, 关贤军. 重大突发事件应急设施多重覆盖选址模型及算法[J]. 运筹与管理, 2011, 20(5): 50-56.