随机多需求环境下远程中继保障网络设计优化问题建模与求解

doi:10.12305/j.issn.1001-506X.2021.07.15

摘要/Abstract

摘要：

为保障海域安全稳定, 当远海海域发生紧急安全问题时, 需要派遣飞机从大陆保障基地出发进行远程支援。本文研究了在随机多需求环境下, 中继保障网络的最优化设计问题, 给出了规范化的问题描述以及问题的混合整数规划模型, 根据事发点发生意外事件的频率以及保障需求量作为需求的权重建立目标函数。模型以中继保障点的位置以及最优支援路线作为决策变量, 以保障资源作为约束条件, 实现了连续与离散相结合的选址方法来优化中继保障点, 并运用几何近似方法将模型中的欧式距离非线性约束转化为线性约束。所建模型可应用数学模型建模语言和求解器进行最优化求解, 直接获得多种不确定需求环境下的期望最优网络设计及支援路径。基于给定的3种任务类型, 经过模拟案例验证, 所建立模型可满足对实际规模的中继保障网络优化设计。

关键词: 中继保障网络设计, 最低成本路径, 离散连续选址

Abstract:

In order to ensure the safety and stability of sea area, when an emergency security event occurs in the offshore area, it is often necessary to send aircraft from the mainland base to support and secure the event remotely. The optimal design problem of relay support network under stochastic and multi-demand environment is studied, the normalized problem description and mixed integer programming(MILP) model of the problem are given, and the objective function is established according to the frequency of unexpected events at the incident point and the support demand as the weight of demand. Taking the location of relay support points and the optimal support route as decision variables and the support resources as constraints, the MILP model realizes the location method combining continuous and discrete to optimize the selection of relay points, and uses the geometric approximation method to transform the Euclidian distance nonlinear constraint into linear constraint. The proposed MILP model can be optimized by using mathematical modeling language and solver, and the desired optimal network design and support path can be obtained directly under various uncertain demand environments. Based on the given three types of tasks, the simulation computation show that the proposed MILP model can meet the actual scale of the network design problem with relay.

Key words: network design with relay, least cost route, discrete and continuous location

中图分类号:

杨培, 肖依永, 王宏宇. 随机多需求环境下远程中继保障网络设计优化问题建模与求解[J]. 系统工程与电子技术, 2021, 43(7): 1838-1847.

Pei YANG, Yiyong XIAO, Hongyu WANG. Modeling and solution of the romote support network design problem with relays in an environment with multiple uncertainty demands[J]. Systems Engineering and Electronics, 2021, 43(7): 1838-1847.

图/表 8

图1

图2

图3

表1

表2

图4

图5

图6

参考文献 31

1	任兆瑞, 龚传信, 樊延平. 岛上城市进攻作战装备保障面临的问题及对策[J]. 装备指挥技术学院学报, 2004, 15 (6): 29- 32. doi: 10.3783/j.issn.1673-0127.2004.06.008
	REN Z R , GONG C X , FAN Y P . Problems and counter mea-sures of equipment support in island city offensive operations[J]. Journal of Equipment Command Technology College, 2004, 15 (6): 29- 32. doi: 10.3783/j.issn.1673-0127.2004.06.008
2	段祺麟. 东海岛屿文化安全现状分析与对策研究[D]. 舟山: 浙江海洋学院, 2015.
	DUAN Q L. Analysis on the current situation of cultural security of islands in the East China Sea and countermeasures[D]. Zhoushan: Zhejiang Ocean University, 2015.
3	刘增勇, 崔益烽, 张春润. 近岸岛屿联合作战船艇装备保障力量部署方法[J]. 兵工自动化, 2010, 29 (4): 58- 60, 62. doi: 10.3969/j.issn.1006-1576.2010.04.018
	LIU Z Y , CUI Y F , ZHANG C R . Deployment method of ship equipment support force in coastal island joint operation[J]. Ordnance Automation, 2010, 29 (4): 58- 60, 62. doi: 10.3969/j.issn.1006-1576.2010.04.018
4	任骥, 郑晓蕾. 战场不确定环境下考虑敌方打击的后勤供应网络设计[J]. 火力与指挥控制, 2014, 39 (6): 126- 130. doi: 10.3969/j.issn.1002-0640.2014.06.033
	REN J , ZHENG X L . Design of logistics supply network considering enemy attack in uncertain battlefield environment[J]. Fire Control and Command Control, 2014, 39 (6): 126- 130. doi: 10.3969/j.issn.1002-0640.2014.06.033
5	童声, 郭建胜, 郑明发. 不确定环境下的战场物资供应任务规划[J]. 空军工程大学学报(自然科学版), 2014, 15 (5): 88- 91. doi: 10.3969/j.issn.1009-3516.2014.05.020
	TONG S , GUO J S , ZEHNG M F , et al. Battlefield material supply task planning under uncertain environment[J]. Journal of Air Force Engineering University (Natural Science Edition), 2014, 15 (5): 88- 91. doi: 10.3969/j.issn.1009-3516.2014.05.020
6	韩维泽, 彭强中. 聚焦美军"聚焦后勤"[J]. 军事经济研究, 2002, 23 (10): 75.
	HAN W Z , PENG Q Z . Focusing on US military and "focusing on logistics"[J]. Military Economic Research, 2002, 23 (10): 75.
7	李伟, 熊德禹, 姚伟. "聚焦后勤"理论及其对我军实现精准后勤的启示[J]. 军事经济学院学报, 2005, 12 (3): 29- 30.
	LI W , XIONG D Y , YAO W . The theory of "focusing on logistics" and its enlightenment on the realization of precision logistics in our army[J]. Journal of Military Economic College, 2005, 12 (3): 29- 30.
8	王京海. 适于作战的感知与反应后勤[M]. 北京: 军事科学出版社, 2005.
	WANG J H . Perception and response logistics suitable for combat[M]. Beijing: Military Science Press, 2005.
9	HANSON M A . Air-sea battle strategy: the army on the defensive[J]. Officer, 2013, 89 (6): 50.
10	DINLER D , TURAL M K , IYIGUN C . Heuristics for a continuous multi-facility location problem with demand regions[J]. Computers & Operations Research, 2015, 62, 237- 256.
11	MEIRA A A L , MIYAZAWA K F . Clustering through continuous facility location problems[J]. Theoretical Computer Science, 2017, 657 (B): 137- 145.
12	YUN L F , FAN H Q , LI X P . Reliable facility location design with round-trip transportation under imperfect information part Ⅱ: a continuous model[J]. Transportation Research Part B: Methodological, 2019, 124, 44- 59. doi: 10.1016/j.trb.2019.04.002
13	LEVANOVA T V , GNUSAREV A Y . Simulated annealing for competitive p-median facility location problem[J]. Journal of Physics Conference Series, 2018, 1050 (1): 12- 44.
14	XIE Y , ZHOU S H , XIAO Y Y , et al. A β-accurate linearization method of Euclidean distance for the facility layout problem with heterogeneous distance metrics[J]. European Journal of Operational Research, 2018, 265 (1): 26- 38. doi: 10.1016/j.ejor.2017.07.052
15	YANG P , XIAO Y Y , ZHANG Y , et al. The continuous maximal covering location problem in large-scale natural disaster rescue scenes[J]. Computers & Industrial Engineering, 2020, 146, 106608.
16	ADEL B U , HIFI M . A hybrid descent method for the two-edge disjoint survivable network design problem with relays[J]. Computers & Industrial Engineering, 2016, 112, 645- 653.
17	CHEN P , NIE Y . Stochastic optimal path problem with relays[J]. Transportation Research Procedia, 2015, 7, 129- 148. doi: 10.1016/j.trpro.2015.06.008
18	MARKUS L , LJUBIC I , RIEDLER M , et al. Exact approaches for the directed network design problem with relays[J]. Omega, 2020, 91, 102005. doi: 10.1016/j.omega.2018.11.014
19	ZHOU C Y , MAZUMDER A , DAS A , et al. Relay node placement under budget constraint[J]. Pervasive and Mobile Computing, 2018, 53, 1- 12.
20	CUI J , HU B , CHEN S Z . Resource allocation and location decision of a UAV-relay for reliable emergency indoor communication[J]. Computer Communications, 2020, 159, 15- 25. doi: 10.1016/j.comcom.2020.05.019
21	LU H , WEI X L . A cost-efficient elastic UAV relay network construction method with guaranteed QoS[J]. Ad Hoc Networks, 2020, 107, 102219. doi: 10.1016/j.adhoc.2020.102219
22	ZHANG D , LIU Y , HE S C . Vehicle assignment and relays for one-way electric car-sharing systems[J]. Transportation Research Part B, 2019, 120, 125- 146. doi: 10.1016/j.trb.2018.12.004
23	LI X Y , LIN S C , CHEN S , et al. An iterated metaheuristic for the directed network design problem with relays[J]. Computers & Industrial Engineering, 2017, 113, 35- 45.
24	MA C F , LI Y , YANG B , et al. Relay node placement for building wireless sensor networks with reconfigurability provision[J]. Ad Hoc Networks, 2020, 107, 102263. doi: 10.1016/j.adhoc.2020.102263
25	BASTUEK I , CHEN Y F , ALOUINI S M . Energy-efficient communication for user-relay aided cellular networks with OFDMA[J]. Physical Communication, 2019, 33, 153- 164. doi: 10.1016/j.phycom.2018.12.021
26	SARIEDDINE K , CHARAF M , AYAD M , ARTAIL H . A framework for mobile relay node selection for serving outdoor cell edge users[J]. Computer Networks, 2020, 178, 107359. doi: 10.1016/j.comnet.2020.107359
27	KHAN B S , JANGSHER S , QURESHI K H , et al. Predicted mobility based profitable relay selection in cooperative cellular network with mobile relays[J]. Physical Communication, 2019, 37, 100808. doi: 10.1016/j.phycom.2019.100808
28	XIAO Y Y , KONAK A . A variable neighborhood search for the network design problem with relays[J]. Journal of Heuristics, 2017, 23, 137- 164. doi: 10.1007/s10732-017-9332-2
29	KONAK A . Network design problem with relays: a genetic algorithm with a path-based crossover and a set covering formulation[J]. European Journal of Operational Research, 2012, 218, 829- 837. doi: 10.1016/j.ejor.2011.11.046
30	KONAK A . Two-edge disjoint survivable network design problem with relays: a hybrid genetic algorithm and Lagrangian heuristic approach[J]. Optimization and Engineering, 2014, 46 (1): 130- 145. doi: 10.1080/0305215X.2012.753436
31	KABADURMUS O , SMITH A E . Multi-commodity k-splittable survivable network design problem with relays[J]. Telecommunication Systems, 2016, 62, 123- 133. doi: 10.1007/s11235-015-0067-9

ε	θ	n
5.00%	0.523 6	3
1.00%	0.261 8	6
0.50%	0.196 3	8
0.10%	0.087 3	18
0.05%	0.062 8	25
0.01%	0.028 0	56

节点	横坐标	纵坐标	节点类型	保障点名称
1	37.79	117.94	1	基地级A
2	46.97	80.20	1	基地级B
3	60.84	99.99	1	基地级C
4	70.79	80.59	1	基地级D
5	77.49	68.34	2	中继级岛礁
6	83.59	65.35	2	中继级岛礁
7	67.98	60.16	2	中继级岛礁
8	37.15	61.35	2	中继级岛礁
9	105.44	63.24	2	中继级岛礁
10	52.90	64.93	2	中继级岛礁
11	34.74	65.33	2	中继级岛礁
12	72.10	64.86	2	中继级岛礁
13	21.43	62.65	2	中继级岛礁
14	38.68	62.50	2	中继级岛礁
15	41.33	67.10	2	中继级岛礁
16	49.59	64.02	2	中继级岛礁
17	26.58	63.70	2	中继级岛礁
18	47.45	59.37	2	中继级岛礁
19	15.97	64.27	2	中继级岛礁
20	43.46	67.93	2	中继级岛礁
21	104.95	63.09	2	中继级岛礁
22	67.95	69.15	2	中继级岛礁
23	23.79	59.74	2	中继级岛礁
24	94.66	60.61	2	中继级岛礁
25	38.77	19.58	4	事发点1
26	25.28	21.12	4	事发点2
27	59.12	0.30	4	事发点3
28	80.22	18.93	4	事发点4
29	0	0	3	中继级浮岛
30	0	0	3	中继级浮岛

[1]	尤杨, 金光, 潘正强, 郭芮. 约束空间近似正交的空间填充试验设计方法[J]. 系统工程与电子技术, 2021, 43(7): 1831-1837.
[2]	杜晓丽, 梁开荣, 李登峰. 基于CIS值的双边链路形成策略优化两型博弈方法[J]. 系统工程与电子技术, 2020, 42(7): 1550-1557.
[3]	朱建军, 刘思峰, 胡宏宇. 基于二元不完全偏好的群决策方法[J]. Journal of Systems Engineering and Electronics, 2009, 31(8): 1887-1891.