LIPIcs.ISAAC.2022.49.pdf
- Filesize: 0.91 MB
- 16 pages
Document
Package Delivery Using Drones with Restricted Movement Areas
Authors
Thomas Erlebach 
,
Kelin Luo ,
Frits C.R. Spieksma
-
Part of:
Volume:
33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-12-14
File
Document Identifiers
Author Details
Cite As Get BibTex
Thomas Erlebach, Kelin Luo, and Frits C.R. Spieksma. Package Delivery Using Drones with Restricted Movement Areas. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.49
Abstract
For the problem of delivering a package from a source node to a destination node in a graph using a set of drones, we study the setting where the movements of each drone are restricted to a certain subgraph of the given graph. We consider the objectives of minimizing the delivery time (problem DDT) and of minimizing the total energy consumption (problem DDC). For general graphs, we show a strong inapproximability result and a matching approximation algorithm for DDT as well as NP-hardness and a 2-approximation algorithm for DDC. For the special case of a path, we show that DDT is NP-hard if the drones have different speeds. For trees, we give optimal algorithms under the assumption that all drones have the same speed or the same energy consumption rate. The results for trees extend to arbitrary graphs if the subgraph of each drone is isometric.
Subject Classification
ACM Subject Classification
- Theory of computation → Design and analysis of algorithms
Keywords
- Mobile agents
- approximation algorithm
- inapproximability
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Amazon Staff. Amazon Prime Air prepares for drone deliveries. https://www.aboutamazon.com/news/transportation/amazon-prime-air-prepares-for-drone-deliveries, 13 june 2022. Accessed: 2022-06-19.
- Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Barbara Geissmann, Daniel Graf, Arnaud Labourel, and Matús Mihalák. Collaborative delivery with energy-constrained mobile robots. Theor. Comput. Sci., 810:2-14, 2020. URL: https://doi.org/10.1016/j.tcs.2017.04.018.
- Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Daniel Graf, Jan Hackfeld, and Paolo Penna. Energy-efficient delivery by heterogeneous mobile agents. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs, pages 10:1-10:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.STACS.2017.10.
- Andreas Bärtschi, Daniel Graf, and Matús Mihalák. Collective fast delivery by energy-efficient agents. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, volume 117 of LIPIcs, pages 56:1-56:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.56.
- Andreas Bärtschi and Thomas Tschager. Energy-efficient fast delivery by mobile agents. In Ralf Klasing and Marc Zeitoun, editors, Fundamentals of Computation Theory - 21st International Symposium, FCT 2017, Bordeaux, France, September 11-13, 2017, Proceedings, volume 10472 of Lecture Notes in Computer Science, pages 82-95. Springer, 2017. URL: https://doi.org/10.1007/978-3-662-55751-8_8.
- Iago A. Carvalho, Thomas Erlebach, and Kleitos Papadopoulos. On the fast delivery problem with one or two packages. J. Comput. Syst. Sci., 115:246-263, 2021. URL: https://doi.org/10.1016/j.jcss.2020.09.002.
- Jérémie Chalopin, Shantanu Das, Yann Disser, Arnaud Labourel, and Matús Mihalák. Collaborative delivery on a fixed path with homogeneous energy-constrained agents. Theor. Comput. Sci., 868:87-96, 2021. URL: https://doi.org/10.1016/j.tcs.2021.04.004.
- Jérémie Chalopin, Shantanu Das, Matúš Mihalák, Paolo Penna, and Peter Widmayer. Data delivery by energy-constrained mobile agents. In International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS 2013), volume 8243 of Lecture Notes in Computer Science, pages 111-122. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-45346-5_9.
- Jérémie Chalopin, Riko Jacob, Matúš Mihalák, and Peter Widmayer. Data delivery by energy-constrained mobile agents on a line. In 41st International Colloquium on Automata, Languages, and Programming (ICALP 2014), volume 8573 of Lecture Notes in Computer Science, pages 423-434. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43951-7_36.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 4th Edition. MIT Press, 2022. URL: https://mitpress.mit.edu/books/introduction-algorithms-fourth-edition.
- Thomas Erlebach, Kelin Luo, and Frits C.R. Spieksma. Package delivery using drones with restricted movement areas. CoRR, abs/2209.12314, 2022. URL: https://doi.org/10.48550/arXiv.2209.12314.
-
M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
