Skip to main content
Article
Approximation Algorithms for the Team Orienteering Problem
Proceedings - IEEE INFOCOM
  • Wenzheng Xu
  • Zichuan Xu
  • Jian Peng
  • Weifa Liang
  • Tang Liu
  • Xiaohua Jia
  • Sajal K. Das, Missouri University of Science and Technology
Abstract

In this paper we study a team orienteering problem, which is to find service paths for multiple 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 IoT 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 paper, we first formulate the team orienteering problem, where different vehicles are different types, each node can be served by multiple 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 + \varepsilon }}}}} \right) approximation algorithm for the problem, where ϵ is a given constant with 0 < ϵ≤ 1 and e is the base of the natural logarithm. In particular, the approximation ratio is no less than 0.32 when ϵ= 0.5. In addition, for a special team orienteering problem with the same type of vehicles and the profits of serving a node once and multiple times being the same, we devise an improved approximation algorithm. Finally, we evaluate the proposed algorithms with simulation experiments, and the results of which are very promising. Precisely, the profit sums delivered by the proposed algorithms are approximately 12.5% to 17.5% higher than those by existing algorithms.

Meeting Name
IEEE INFOCOM
Department(s)
Computer Science
Research Center/Lab(s)
Center for High Performance Computing Research
Comments
National Science Foundation, Grant 2019KJT0015-2018GZ0098
Keywords and Phrases
  • approximation algorithms,
  • Index Terms - Multiple vehicle scheduling,
  • submodular function.,
  • team orienteering problem
International Standard Book Number (ISBN)
978-172816412-0
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2020 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.
Publication Date
7-1-2020
Publication Date
01 Jul 2020
Disciplines
Citation Information
Wenzheng Xu, Zichuan Xu, Jian Peng, Weifa Liang, et al.. "Approximation Algorithms for the Team Orienteering Problem" Proceedings - IEEE INFOCOM (2020) p. 1389 - 1398 ISSN: 0743-166X
Available at: http://works.bepress.com/sajal-das/199/