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

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

Abstract

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

CLC Number:

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.

Figures/Tables 8

Fig.1

Fig.2

Fig.3

Table 1

Table 2

Fig.4

Fig.5

Fig.6

References 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]	Yang YOU, Guang JIN, Zhengqiang PAN, Rui GUO. Nearly-orthogonal space-filling experimental design method for constrained spaces [J]. Systems Engineering and Electronics, 2021, 43(7): 1831-1837.
[2]	Xiaoli DU, Kairong LIANG, Dengfeng LI. Biform game approach to strategy optimization of bilateral link formation based on CIS value [J]. Systems Engineering and Electronics, 2020, 42(7): 1550-1557.
[3]	ZHU Jian-jun, LIU Si-feng, HU Hong-yu. Aggregation approach to bivariate of incomplete preference information [J]. Journal of Systems Engineering and Electronics, 2009, 31(8): 1887-1891.

Modeling and solution of the romote support network design problem with relays in an environment with multiple uncertainty demands

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 8

References 31

Related Articles 3

Recommended Articles

Metrics

Comments