Approximation Algorithms for the Team Orienteering Problem

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

International Standard Serial Number (ISSN)

0743-166X

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

01 Jul 2020

Link to Full Text

Share

 
COinS