Approximation Algorithms for the Team Orienteering Problem

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review

8 Scopus Citations
View graph of relations

Author(s)

  • Wenzheng Xu
  • Zichuan Xu
  • Jian Peng
  • Tang Liu
  • Sajal K. Das

Related Research Unit(s)

Detail(s)

Original languageEnglish
Title of host publicationIEEE INFOCOM 2020 - IEEE Conference on Computer Communications
PublisherIEEE
Pages1389-1398
ISBN (Electronic)9781728164120
ISBN (Print)9781728164137
Publication statusPublished - Jul 2020

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X
ISSN (Electronic)2641-9874

Conference

Title39th IEEE International Conference on Computer Communications (IEEE INFOCOM 2020)
LocationVirtual
PlaceCanada
CityToronto
Period6 - 9 July 2020

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 ( 1 - (1/e)}1/2+ε)-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.

Research Area(s)

  • approximation algorithms, Index Terms - Multiple vehicle scheduling, submodular function, team orienteering problem

Citation Format(s)

Approximation Algorithms for the Team Orienteering Problem. / Xu, Wenzheng; Xu, Zichuan; Peng, Jian; Liang, Weifa; Liu, Tang; Jia, Xiaohua; Das, Sajal K.

IEEE INFOCOM 2020 - IEEE Conference on Computer Communications. IEEE, 2020. p. 1389-1398 9155343 (Proceedings - IEEE INFOCOM).

Research output: Chapters, Conference Papers, Creative and Literary Works (RGC: 12, 32, 41, 45)32_Refereed conference paper (with ISBN/ISSN)peer-review