TY - GEN

T1 - Approximation Algorithms for the Team Orienteering Problem

AU - Xu, Wenzheng

AU - Xu, Zichuan

AU - Peng, Jian

AU - Liang, Weifa

AU - Liu, Tang

AU - Jia, Xiaohua

AU - Das, Sajal K.

N1 - Publisher Copyright:
© 2020 IEEE.

PY - 2020/7

Y1 - 2020/7

N2 - 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.

AB - 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.

KW - Index Terms - Multiple vehicle scheduling

KW - approximation algorithms

KW - submodular function.

KW - team orienteering problem

UR - http://www.scopus.com/inward/record.url?scp=85090269832&partnerID=8YFLogxK

U2 - 10.1109/INFOCOM41043.2020.9155343

DO - 10.1109/INFOCOM41043.2020.9155343

M3 - Conference contribution

T3 - Proceedings - IEEE INFOCOM

SP - 1389

EP - 1398

BT - INFOCOM 2020 - IEEE Conference on Computer Communications

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 38th IEEE Conference on Computer Communications, INFOCOM 2020

Y2 - 6 July 2020 through 9 July 2020

ER -