Load and Wind Aware Routing of Delivery Drones
Delivery drones have been attracting attention as one of the promising technologies to deliver packages. Several research studies on routing problems specifically for drone delivery scenarios have extended Vehicle Routing Problems (VRPs). Most existing VRPs are based on Traveling Salesman Problems (...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2022-02-01
|
| Series: | Drones |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2504-446X/6/2/50 |
| _version_ | 1827655568156786688 |
|---|---|
| author | Satoshi Ito Keishi Akaiwa Yusuke Funabashi Hiroki Nishikawa Xiangbo Kong Ittetsu Taniguchi Hiroyuki Tomiyama |
| author_facet | Satoshi Ito Keishi Akaiwa Yusuke Funabashi Hiroki Nishikawa Xiangbo Kong Ittetsu Taniguchi Hiroyuki Tomiyama |
| author_sort | Satoshi Ito |
| collection | DOAJ |
| description | Delivery drones have been attracting attention as one of the promising technologies to deliver packages. Several research studies on routing problems specifically for drone delivery scenarios have extended Vehicle Routing Problems (VRPs). Most existing VRPs are based on Traveling Salesman Problems (TSPs) for minimizing the overall distance. On the other hand, VRPs for drone delivery have been aware of energy consumption due to the consideration of battery capacity. Despite hovering motions with loading packages accounting for a large portion of energy consumption since delivery drones need to hover with several packages, little research has been conducted on drone routing problems that aim at the minimization of overall flight times. In addition, flight time is strongly influenced by windy conditions such as headwinds and tailwinds. In this paper, we propose a VRP for drone delivery in which flight time is dependent on the weight of packages in a windy environment, called Flight Speed-aware Vehicle Routing Problem with Load and Wind (FSVRPLW). In this paper, flight speed changes depending on the load and wind. Specifically, a heavier package slows down flight speeds and a lighter package speeds up flight speeds. In addition, a headwind slows down flight speeds and a tailwind speed up flight speeds. We mathematically derived the problem and developed a dynamic programming algorithm to solve the problem. In the experiments, we investigate how much impact both the weight of packages and the wind have on the flight time. The experimental results indicate that taking loads and wind into account is very effective in reducing flight times. Moreover, the results of comparing the effects of load and wind indicate that flight time largely depends on the weight of packages. |
| first_indexed | 2024-03-09T22:08:34Z |
| format | Article |
| id | doaj.art-83a64be35c0c4bf5916eabae9be7122d |
| institution | Directory Open Access Journal |
| issn | 2504-446X |
| language | English |
| last_indexed | 2024-03-09T22:08:34Z |
| publishDate | 2022-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Drones |
| spelling | doaj.art-83a64be35c0c4bf5916eabae9be7122d2023-11-23T19:36:03ZengMDPI AGDrones2504-446X2022-02-01625010.3390/drones6020050Load and Wind Aware Routing of Delivery DronesSatoshi Ito0Keishi Akaiwa1Yusuke Funabashi2Hiroki Nishikawa3Xiangbo Kong4Ittetsu Taniguchi5Hiroyuki Tomiyama6Graduate School of Science and Engineering, Ritsumeikan University, Kusatsu, Shiga 525-8577, JapanDepartment of Science and Engineering, Ritsumeikan University, Kusatsu, Shiga 525-8577, JapanGraduate School of Science and Engineering, Ritsumeikan University, Kusatsu, Shiga 525-8577, JapanGraduate School of Science and Engineering, Ritsumeikan University, Kusatsu, Shiga 525-8577, JapanGraduate School of Science and Engineering, Ritsumeikan University, Kusatsu, Shiga 525-8577, JapanGraduate School of Information Science and Technology, Osaka University, Suita, Osaka 565-0871, JapanGraduate School of Science and Engineering, Ritsumeikan University, Kusatsu, Shiga 525-8577, JapanDelivery drones have been attracting attention as one of the promising technologies to deliver packages. Several research studies on routing problems specifically for drone delivery scenarios have extended Vehicle Routing Problems (VRPs). Most existing VRPs are based on Traveling Salesman Problems (TSPs) for minimizing the overall distance. On the other hand, VRPs for drone delivery have been aware of energy consumption due to the consideration of battery capacity. Despite hovering motions with loading packages accounting for a large portion of energy consumption since delivery drones need to hover with several packages, little research has been conducted on drone routing problems that aim at the minimization of overall flight times. In addition, flight time is strongly influenced by windy conditions such as headwinds and tailwinds. In this paper, we propose a VRP for drone delivery in which flight time is dependent on the weight of packages in a windy environment, called Flight Speed-aware Vehicle Routing Problem with Load and Wind (FSVRPLW). In this paper, flight speed changes depending on the load and wind. Specifically, a heavier package slows down flight speeds and a lighter package speeds up flight speeds. In addition, a headwind slows down flight speeds and a tailwind speed up flight speeds. We mathematically derived the problem and developed a dynamic programming algorithm to solve the problem. In the experiments, we investigate how much impact both the weight of packages and the wind have on the flight time. The experimental results indicate that taking loads and wind into account is very effective in reducing flight times. Moreover, the results of comparing the effects of load and wind indicate that flight time largely depends on the weight of packages.https://www.mdpi.com/2504-446X/6/2/50drone routing problemflight speed-aware vehicle routing problemdynamic programming algorithmdrone |
| spellingShingle | Satoshi Ito Keishi Akaiwa Yusuke Funabashi Hiroki Nishikawa Xiangbo Kong Ittetsu Taniguchi Hiroyuki Tomiyama Load and Wind Aware Routing of Delivery Drones Drones drone routing problem flight speed-aware vehicle routing problem dynamic programming algorithm drone |
| title | Load and Wind Aware Routing of Delivery Drones |
| title_full | Load and Wind Aware Routing of Delivery Drones |
| title_fullStr | Load and Wind Aware Routing of Delivery Drones |
| title_full_unstemmed | Load and Wind Aware Routing of Delivery Drones |
| title_short | Load and Wind Aware Routing of Delivery Drones |
| title_sort | load and wind aware routing of delivery drones |
| topic | drone routing problem flight speed-aware vehicle routing problem dynamic programming algorithm drone |
| url | https://www.mdpi.com/2504-446X/6/2/50 |
| work_keys_str_mv | AT satoshiito loadandwindawareroutingofdeliverydrones AT keishiakaiwa loadandwindawareroutingofdeliverydrones AT yusukefunabashi loadandwindawareroutingofdeliverydrones AT hirokinishikawa loadandwindawareroutingofdeliverydrones AT xiangbokong loadandwindawareroutingofdeliverydrones AT ittetsutaniguchi loadandwindawareroutingofdeliverydrones AT hiroyukitomiyama loadandwindawareroutingofdeliverydrones |