基于电子商务竞标结构的分布式作战资源调度

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

摘要/Abstract

摘要：

针对现代战争作战任务规划问题, 提出一种基于电子商务多轮竞标结构的作战资源调度方法, 以异步、分散的方式让多个供应商协调来自多个消费者的任务资源请求。每个任务关联一个时间窗口, 有些任务需要不同类的多个资源同步服务。招标由消费者发起, 供应商对各资源请求发起投标, 消费者根据投标结果中任务的3种状态, 采取不同策略, 并向供应商发送中标信息以执行任务或启动下一轮竞标。建立供应商和消费者调度问题数学模型, 针对供应商资源调度非确定性多项式(nondeterministic polynomial, NP)完全问题特点, 提出基于改进节约算法和自适应大邻域搜索算法的两阶段启发式求解方法; 消费者模型使用混合整数线性规划来选择成本最低的投标组合, 以满足任务需求。算例分析验证了所提方法的有效性。

关键词: 电子商务, 时间窗, 供应商调度问题, 同步约束, 自适应大邻域搜索

Abstract:

A combat resource scheduling method based on e-commerce multi-round bidding structure is proposed for modern warfare mission planning, which enables multiple suppliers to coordinate task resource requests from multiple consumers in an asynchronous and decentralized manner. Each task is associated with a time window, and some tasks require multiple resource synchronization services of different types. The bidding is initiated by consumers, and suppliers initiate bids for various resource requests. Consumers adopt different strategies based on the three states of tasks in the bidding results, and send bid winning information to suppliers to execute tasks or initiate the next round of bidding. A mathematical model for supplier and consumer scheduling problems is established, and a two-stage heuristic solution method is proposed based on an improved saving algorithm and an adaptive large neighborhood search (ALNS) algorithm for the nondeterministic polynomial (NP) complete problem of supplier resource scheduling. The consumer model uses mixed integer linear programming to select the lowest cost bid combination to meet task requirements. The effectiveness of the proposed method is verified through case analysis.

Key words: e-commerce, time window, supplier scheduling problem, synchronization constraint, adaptive large neighborhood search

中图分类号:

TP391.7

颜骥, 刘丙杰, 陈建华. 基于电子商务竞标结构的分布式作战资源调度[J]. 系统工程与电子技术, 2023, 46(1): 227-236.

Ji YAN, Bingjie LIU, Jianhua CHEN. Decentralized operational resource scheduling based on e-commerce bidding structure[J]. Systems Engineering and Electronics, 2023, 46(1): 227-236.

图/表 7

图1

图2

图3

图4

图5

表1

表2

参考文献 21

1	DHARINI D. Multi-robot task allocation and scheduling with spatio-temporal and energy constraints[D]. Cambridge: Massachusetts Institute of Technology, 2019.
2	VAN D M, MINASA P. The cooperative orienteering problem with time windows[EB/OL]. [2022-09-09]. http://www.optimization-online.org/DB_HTML/2014/04/4316.html.
3	GUNAWAN A, YU V F, SUTANTO A N. Set team orienteering problem with time windows[C]//Proc. of the 15th International Conference on Learning and Intelligent Optimization, 2021: 142-149.
4	ELISEO M, LAURA S. Team orienteering problem with time windows and variable profit[C]//Proc. of the 17th Conference on Computer Science and Intelligence Systems, 2022: 347-350.
5	SOHAIB A , DANG D C , AZIZ M . Heuristic solutions for the vehicle routing problem with time windows and synchronized visits[J]. Optimization Letters, 2016, 10 (3): 511- 525. doi: 10.1007/s11590-015-0878-3
6	JALEL E , SALAH Z , LAMRI L . A hybrid approach to solve the vehicle routing problem with time windows and synchronized visits in home health care[J]. Arabian Journal for Science and Engineering, 2020, 45, 10637- 10652. doi: 10.1007/s13369-020-04828-5
7	MATEUSZ P , ANNALISA R , KEREM A . A multistage optimization algorithm for the large vehicle routing problem with time windows and synchronized visits[J]. Journal of the Operational Research Society, 2021, 72 (11): 2396- 2411. doi: 10.1080/01605682.2020.1792365
8	ARIELLA M, SANDEEP M, MACHARET G. Multi-robot scheduling for environmental monitoring as a team orienteering problem[C]//Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2021: 6398-6404.
9	IMAN R , HEARNE J W , DELARAM P . A solution approach to the orienteering problem with time windows and synchronization constraints[J]. Heliyon, 2020, 6 (6): e04202. doi: 10.1016/j.heliyon.2020.e04202
10	ROOZBEH I , OZLEN M H . An adaptive large neighborhood search for asset protection during escaped wildfires[J]. Computers and Operations Research, 2018, 97, 125- 134. doi: 10.1016/j.cor.2018.05.002
11	IMAN R, MELIH O, HEARNE J W. A heuristic scheme for the cooperative team orienteering problem with time windows[EB/OL]. [2022-10-05]. https://arxiv.org/abs/1608.05485.
12	KIM R G. Operational planning for theater anti-submarine warfare[D]. Monterey: Naval Postgraduate School, 2017.
13	CORINE M L , ANA I B , BOUCHERIE R J . Optimal deployment for anti-submarine operations with time-dependent strategies[J]. Journal of Defense Modeling and Simulation: Applications, Methodology, Technology, 2019, 17 (4): 419- 434.
14	IŠORAITĖ M , MINIOTIENĖ N . Electronic commerce: theory and practice[J]. Integrated Journal of Business and Economics, 2018, 2, 73- 79. doi: 10.33019/ijbe.v2i2.78
15	LIU R , TAO Y Y , XIE X L . An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits[J]. Computers & Operations Research, 2018, 101, 250- 262.
16	MESQUITA M, MURTA A, PAIAS A. TSP with multiple time-windows and selective cities[C]//Proc. of the 4th International Conference on Computational Logistics, 2013: 158-172.
17	KONSTANTINA M. Resource scheduling and optimization in dynamic and complex transportation settings[D]. Cambridge: Massachusetts Institute of Technology, 2019.
18	GREGOR H . Adaptive large neighborhood search for mixed integer programming[J]. Mathematical Programming Computation, 2022, 14, 185- 221. doi: 10.1007/s12532-021-00209-7
19	李珍萍, 赵羽薇, 张煜炜, 等. 共同配送选址-路径问题及大邻域搜索算法[J]. 系统仿真学报, 2021, 33 (10): 2518- 2530.
	LI Z P , ZHAO Y W , ZHANG Y W , et al. Joint distribution location-routing problem and large neighborhood search algorithm[J]. Jounal of System Simulation, 2021, 33 (10): 2518- 2530.
20	伍国华, 毛妮, 徐彬杰, 等. 基于自适应大规模领域搜索算法的多车辆与多无人机协同配送方法[J]. 控制与决策, 2023, 38 (1): 201- 210.
	WU G H , MAO N , XU B J , et al. The cooperative delivery of multiple vehicles and multiple drones based on adaptive large neighborhood search[J]. Control and Decision, 2023, 38 (1): 201- 210.
21	STEFAN R , PISINGER D . An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40 (4): 455- 472. doi: 10.1287/trsc.1050.0135

消费者任务数	RUS运行时间	MILP运行时间	消费者任务数	RUS运行时间	MILP运行时间
4	2.88	6.46	12	791.03	5 479.36
4	10.83	10.70	12	1 412.87	4 077.86
4	2.54	8.94	12	1 671.79	4 192.52
4	5.45	10.35	12	1 713.51	*
8	24.88	3 174.74	16	823.96	5 785.59
8	11.52	2 520.81	16	1 053.25	*
8	14.23	1 539.23	16	1 705.54	*
8	27.59	3 276.85	16	837.74	*

消费者任务数	RUS解	MILP解	最优值差异/%	消费者任务数	RUS解	MILP解	最优值差异/%
4	214	214	0	12	536	560	4
4	172	172	0	12	627	627	0
4	290	290	0	12	620	620	0
4	249	249	0	12	624	*	**
8	352	352	0	16	674	674	0
8	455	455	0	16	766	*	**
8	348	348	0	16	757	*	**
8	315	315	0	16	948	*	**

[1]	蔺瑞管, 王华伟, 车畅畅, 倪晓梅, 熊明兰. 基于LSTM分类器的航空发动机预测性维护模型[J]. 系统工程与电子技术, 2022, 44(3): 1052-1059.
[2]	刘彦, 陈春良, 陈伟龙, 郭一鸣. 基于Pareto改进VNS-MMAS的定点修理任务多目标动态调度[J]. 系统工程与电子技术, 2020, 42(2): 356-364.
[3]	张泉先, 曾斌, 李厚朴. 海况影响下的分布式海战补给路径规划方法[J]. 系统工程与电子技术, 2020, 42(10): 2312-2319.
[4]	许京伟, 兰岚, 朱圣棋, 廖桂生, 张玉洪. 相干频率分集阵雷达匹配滤波器设计[J]. 系统工程与电子技术, 2018, 40(8): 1720-1728.
[5]	崔亚妮, 任佳, 杜文才. 战场环境下多无人机时敏任务动态分配算法[J]. 系统工程与电子技术, 2016, 38(4): 828-835.
[6]	何磊, 刘晓路, 陈英武, 邢立宁. 面向敏捷卫星任务规划的云层建模及处理方法[J]. 系统工程与电子技术, 2016, 38(4): 852-858.
[7]	赵文飞, 周刚, 杨树杰, 董超. 带时间窗军事物资配送问题的NSGA-Ⅱ算法[J]. 系统工程与电子技术, 2015, 37(11): 2513-2519.
[8]	吴天羿，许继恒，刘建永，昝良. 求解有硬时间窗车辆路径问题的改进遗传算法[J]. 系统工程与电子技术, 2014, 36(4): 708-713.
[9]	荆武兴，李罗钢，高长生. 反导拦截飞行方案及时间窗口快速搜索算法[J]. Journal of Systems Engineering and Electronics, 2013, 35(6): 1256-1261.
[10]	胡训强，谢晓方，李德栋. 军用飞机智能起降调度技术研究[J]. Journal of Systems Engineering and Electronics, 2012, 34(11): 2280-2284.
[11]	汤新民，王玉婷，韩松臣. 基于DEDS的A-SMGCS航空器动态滑行路径规划[J]. Journal of Systems Engineering and Electronics, 2010, 32(12): 2669-2675.