2026-08-25T18:47:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27153 2026-08-25T13:18:15Z ddc:004 open_access

Minimizing Total Travel Time for Collaborative Package Delivery with Heterogeneous Drones Erlebach, Thomas Luo, Kelin Zhang, Wen Approximation algorithms Primal-dual method Heterogeneous pickup and delivery problem Algorithm engineering Given a fleet of drones with different speeds and a set of package delivery requests, the collaborative delivery problem asks for a schedule for the drones to collaboratively carry out all package deliveries, with the objective of minimizing the total travel time of all drones. We show that the best non-preemptive schedule (where a package that is picked up at its source is immediately delivered to its destination by one drone) is within a factor of three of the best preemptive schedule (where several drones can participate in the delivery of a single package). Then, we present a constant-factor approximation algorithm for the problem of computing the best non-preemptive schedule. The algorithm reduces the problem to a tree combination problem and uses a primal-dual approach to solve the latter. We have implemented a version of the algorithm optimized for practical efficiency and report the results of experiments on large-scale instances with synthetic and real-world data, demonstrating that our algorithm is scalable and delivers schedules of excellent quality. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Erlebach and Kelin Luo and Wen Zhang 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.17 urn:nbn:de:0030-drops-271531 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.17 eng https://creativecommons.org/licenses/by/4.0/legalcode