The En Route Truck-Drone Delivery Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914663587905536 |
|---|---|
| author | Krizanc, Danny Narayanan, Lata Opatrny, Jaroslav Pankratov, Denis |
| author_facet | Krizanc, Danny Narayanan, Lata Opatrny, Jaroslav Pankratov, Denis |
| contents | We study the truck-drone cooperative delivery problem in a setting where a single truck carrying a drone travels at constant speed on a straight-line trajectory/street. Delivery to clients located in the plane and not on the truck's trajectory is performed by the drone, which has limited carrying capacity and flying range, and whose battery can be recharged when on the truck. We show that the problem of maximizing the number of deliveries is strongly NP-hard even in this simple setting. We present a 2-approximation algorithm for the problem, and an optimal algorithm for a non-trivial family of instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_00829 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The En Route Truck-Drone Delivery Problem Krizanc, Danny Narayanan, Lata Opatrny, Jaroslav Pankratov, Denis Data Structures and Algorithms We study the truck-drone cooperative delivery problem in a setting where a single truck carrying a drone travels at constant speed on a straight-line trajectory/street. Delivery to clients located in the plane and not on the truck's trajectory is performed by the drone, which has limited carrying capacity and flying range, and whose battery can be recharged when on the truck. We show that the problem of maximizing the number of deliveries is strongly NP-hard even in this simple setting. We present a 2-approximation algorithm for the problem, and an optimal algorithm for a non-trivial family of instances. |
| title | The En Route Truck-Drone Delivery Problem |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.00829 |