Skip to main content
Article
Approximation Algorithms for the Generalized Team Orienteering Problem and its Applications
IEEE/ACM Transactions on Networking
  • Wenzheng Xu
  • Weifa Liang
  • Zichuan Xu
  • Jian Peng
  • Dezhong Peng
  • Tang Liu
  • Xiaohua Jia
  • Sajal K. Das, Missouri University of Science and Technology
Abstract

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 left(1-(1/e){frac {1}{2+epsilon }}right) -approximation algorithm for the problem, where epsilon is a given constant with 0 lt epsilon le 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.

Department(s)
Computer Science
Research Center/Lab(s)
Center for High Performance Computing Research
Second Research Center/Lab
Intelligent Systems Center
Comments

The work of Sajal K. Das was supported in part by NSF under Grant CCF-1725755, Grant CNS-1818942, and Grant CNS-1545050.

Keywords and Phrases
  • approximation algorithms,
  • Multiple vehicle scheduling,
  • submodular function,
  • the generalized team orienteering problem
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2021 Association for Computing Machinery (ACM), All rights reserved.
Publication Date
2-1-2021
Publication Date
01 Feb 2021
Disciplines
Citation Information
Wenzheng Xu, Weifa Liang, Zichuan Xu, Jian Peng, et al.. "Approximation Algorithms for the Generalized Team Orienteering Problem and its Applications" IEEE/ACM Transactions on Networking Vol. 29 Iss. 1 (2021) p. 176 - 189 ISSN: 1063-6692; 1558-2566
Available at: http://works.bepress.com/sajal-das/193/