2026-07-24T10:25:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21195 2024-10-07T04:59:11Z ddc:004 open_access

Improved Algorithms for the Capacitated Team Orienteering Problem D'Angelo, Gianlorenzo D'Emidio, Mattia Delfaraz, Esmaeil Di Stefano, Gabriele Vehicle Routing Approximation algorithms Algorithm Engineering We study the Capacitated Team Orienteering Problem, where a fleet of vehicles with capacities have to meet customers with known demands and prizes for a single commodity. The objective is to maximize the total prize and to assign a sequence of customers to each vehicle while keeping the total distance traveled within a given budget and such that the total demand served by each vehicle does not exceed its capacity. The problem has been widely studied both from a theoretical and a practical point of view. The contribution of this paper is twofold: (1) We advance the theoretical knowledge on the problem by providing new approximation algorithms that achieve, under some natural assumption, improved approximation ratios compared to the current best algorithms; (2) We propose four efficient heuristics that outperform the current state-of-the-art practical methods in the sense that they compute solutions that collect nearly the same prize in a significantly smaller running time. We also experimentally test the scalability of the new heuristics, showing that their running time increases approximately linearly with the size of the input, allowing us to process large graphs which were not possible to analyze before. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gianlorenzo D'Angelo and Mattia D'Emidio and Esmaeil Delfaraz and Gabriele Di Stefano 2024 Is Part Of OASIcs, Volume 123, 24th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2024.7 urn:nbn:de:0030-drops-211957 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2024.7 eng https://creativecommons.org/licenses/by/4.0/legalcode