.png){kind=icon}
返回
Approximation Algorithms for the Generalized Team Orienteering Problem and its Applications
.png){kind=icon}
OA
AI
DOI：10.1109/TNET.2020.3027434.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this article we study a generalized team orienteering problem (GTOP), which is to find service paths for multiple homogeneous vehicles in a network such that the profit sum of serving the nodes in the paths is maximized, subject to the cost budget of each vehicle. This problem has many potential applications in IoTs and smart cities, such as dispatching energy-constrained mobile chargers to charge as many energy-critical sensors as possible to prolong the network lifetime. In this article, we first formulate the GTOP problem, where each node can be served by different vehicles, and the profit of serving the node is a submodular function of the number of vehicles serving it. We then propose a novel (1-(1/epsilon)1/2+epsilon)-approximation algorithm for the problem, where epsilon is a given constant with 0 < epsilon <= 1 and e is the base of the natural logarithm. In particular, the approximation ratio is about 0.33 when epsilon = 0.5. In addition, we devise an improved approximation algorithm for a special case of the problem where the profit is the same by serving a node once and multiple times. We finally evaluate the proposed algorithms with simulation experiments, and the results of which are very promising. Especially, the profit sums delivered by the proposed algorithms are up to 14% higher than those by existing algorithms, and about 93.6% of the optimal solutions.
Keyword:
Approximation algorithms
Dispatching
Monitoring
Electronic mail
Intelligent sensors
Multiple vehicle scheduling
the generalized team orienteering problem
approximation algorithms
submodular function
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
I
IF:
3.6
论文数:
4.4K
被引数:
9.5K
机构
引用论文
.png){kind=icon}
Maximizing Sensor Lifetime with the Minimal Service Cost of a Mobile Charger in Wireless Sensor Networks在无线传感器网络中以移动充电器的最小服务成本最大化传感器寿命
PREAI
分享收藏分享收藏Approximation Algorithms for the Min-Max Cycle Cover Problem With Neighborhoods具有邻域的最小-最大循环覆盖问题的近似算法OAAI
OAAI分享收藏Hierarchical Heuristic Search Using a Gaussian Mixture Model for UAV Coverage Planning基于高斯混合模型的分层启发式搜索无人机覆盖规划
PREAI
分享收藏
查看更多内容