Smart City Gnosys
Smart city article details
| Title | Approximation Algorithms For The Team Orienteering Problem |
|---|---|
| ID_Doc | 10234 |
| Authors | Xu W.; Xu Z.; Peng J.; Liang W.; Liu T.; Jia X.; Das S.K. |
| Year | 2020 |
| Published | Proceedings - IEEE INFOCOM, 2020-July |
| DOI | http://dx.doi.org/10.1109/INFOCOM41043.2020.9155343 |
| 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. © 2020 IEEE. |
| Author Keywords | approximation algorithms; Index Terms - Multiple vehicle scheduling; submodular function.; team orienteering problem |
Similar Articles
| Id | Similarity | Authors | Title | Published |
|---|---|---|---|---|
52291  | 0.916 | Panadero J.; Juan A.A.; Ghorbani E.; Faulin J.; Pagès-Bernaus A. | Solving The Stochastic Team Orienteering Problem: Comparing Simheuristics With The Sample Average Approximation Method | International Transactions in Operational Research, 31, 5 (2024) |
| 47093 | 0.867 | Juan A.A.; Freixes A.; Panadero J.; Serrat C.; Estrada-Moreno A. | Routing Drones In Smart Cities: A Biased-Randomized Algorithm For Solving The Team Orienteering Problem In Real Time | Transportation Research Procedia, 47 (2020) |
| 56095 | 0.864 | Luo K.; Agarwal C.; Das S.; Guo X. | The Multi-Vehicle Ride-Sharing Problem | WSDM 2022 - Proceedings of the 15th ACM International Conference on Web Search and Data Mining (2022) |
| 33579 | 0.861 | Li Y.; Peyman M.; Panadero J.; Juan A.A.; Xhafa F. | Iot Analytics And Agile Optimization For Solving Dynamic Team Orienteering Problems With Mandatory Visits | Mathematics, 10, 6 (2022) |
| 14855 | 0.852 | Herrera E.M.; Panadero J.; Juan A.A.; Carracedo P.; Perez-Bernabeu E.; De La Torre R. | Combining Survival Analysis And Simheuristics To Predict The Risk Of Delays In Urban Ridesharing Operations With Random Travel Times | Proceedings - Winter Simulation Conference, 2022-December (2022) |