An Integer Programming Approach to Multi-Trip Routing of Delivery Drones at Load-Dependent Flight Speed

Nishira, Mao; Nishikawa, Hiroki; Kong, Xiangbo; Tomiyama, Hiroyuki

doi:10.35534/dav.2024.10008

Drones and Autonomous Vehicles

Submit to DAV

Article Open Access

An Integer Programming Approach to Multi-Trip Routing of Delivery Drones at Load-Dependent Flight Speed

Mao Nishira ¹ Hiroki Nishikawa ² Xiangbo Kong ³ Hiroyuki Tomiyama ^1,*

Author Information

Graduate School of Science and Engineering, Ritsumeikan University, Kusatsu 525-8577, Japan

Graduate School of Information Science and Technology, Osaka University, Suita 565-0871, Japan

Faculty of Information Engineering, Toyama Prefectural University, Imizu 939-0398, Japan

Authors to whom correspondence should be addressed.

Views:1063

Downloads:134

Drones and Autonomous Vehicles 2024, 1 (3), 10008; https://doi.org/10.35534/dav.2024.10008

Received: 11 May 2024 Accepted: 21 June 2024 Published: 24 June 2024

ABSTRACT: In recent years, there has been a growing interest in utilizing drones for parcel delivery among companies, aiming to address logistical challenges. However, effective optimization of delivery routes is essential. A theoretical framework termed the Flight Speed-aware Vehicle Routing Problem (FSVRP) has emerged to address the variability in drone flight speed based on payload weight. Several approximate methods have been proposed to solve the FSVRP. Our research endeavors to optimize parcel delivery efficiency and reduce delivery times by introducing a novel delivery problem. This problem accounts for multiple deliveries while considering the variability in flight speed due to diverse payloads. Through experimentation, we evaluate the efficacy of our proposed method compared to existing approaches. Specifically, we assess total flight distance and flight time. Our findings indicate that even in cases where the payload exceeds maximum capacity, all parcels can be delivered through multiple trips. Furthermore, employing a multi-trip FSVRP approach results in an average reduction of 10% in total flight time, even when payload capacities are not exceeded.

Keywords: Delivery drones; Vehicle routing problem; Multi-trip routing

1. Introduction

Drone delivery has emerged as a transformative force within modern logistics and distribution sectors. Offering rapid and efficient on-demand delivery, drones markedly diminish the necessity for physical store visits and waiting times, providing consumers with unparalleled convenience compared to conventional delivery methods. Their capacity to reach remote and infrastructure-limited areas holds promise for substantial enhancements in material supply, particularly in rural or emergency contexts. Operating around the clock, drones offer flexible and expeditious services to both daily life and business operations. Moreover, given that the majority of drones operate on electricity, they notably curtail carbon emissions in comparison to traditional fuel-powered delivery vehicles, thus making a significant contribution to environmental conservation [1]. In enhancing accessibility, drones facilitate the delivery of basic goods, such as medical supplies and food, to remote or underserved areas, thereby easing the acquisition of necessary materials for residents in these regions. In natural disasters or other emergencies, their rapid response capabilities and delivery of essential goods strengthen relief efforts. Drones are also utilized in assessing and surveying disaster-stricken areas, aiding in the efficiency of rescue operations [2,3,4]. From an economic perspective, the drone delivery industry is anticipated to create millions of new jobs in manufacturing, maintenance, and operation. The industry is expected to promote online shopping and support the growth of e-commerce businesses while further streamlining logistics and supply chains across various industries, ultimately leading to cost reductions and increased efficiency. Numerous studies have reviewed the literature on package delivery drones [5,6,7,8,9]. However, challenges such as safety concerns, privacy issues, noise pollution, the need for regulatory and legislative measures, and batteries also exist. Extensive research in the domain of delivery drones has delved into numerous facets of their operation and utility, as highlighted in various studies [10,11,12]. In the field of package delivery, many studies have focused on arc routing [13,14]. Furthermore, there are studies pertaining to hybrid truck-drone delivery systems [15,16]. In the context of orchestrating deliveries to multiple consumers, the Vehicle Routing Problem (VRP) has been put forth as a viable framework. VRP is a family of optimization problems that deal with finding the most efficient routes for vehicles, given a set of customer locations to be visited and constraints such as vehicle capacity and travel time. Various variations of VRP exist and are not well-defined [17]. However, the predominant focus of VRP research has traditionally been on vehicular deliveries, specifically trucks, casting doubts on its direct applicability to drone-based delivery systems. Considering this, Poikonen et al. have pioneered an alternative approach specifically tailored for delivery drones, with an emphasis on minimizing delivery time [18]. While there are other contributions in the field of delivery drone routing, they generally presuppose a uniform flight speed for the drones [19,20,21,22,23]. This assumption presents a discrepancy from the dynamics observed in real-world delivery scenarios, where flight speed varies considerably. To address these limitations, Funabashi et al. devised the Flight Speed-aware Vehicle Routing Problem (FSVRP), which incorporates considerations for variations in flight speed attributable to differing payload weights and formulated a dynamic programming strategy to tackle FSVRP [24,25]. The implementation of additional constraints within this algorithm could necessitate substantial modifications. Furthermore, Furthermore, due to its high expressiveness in formulating complex constraints and objectives [26,27,28], an Integer Programming methodology was introduced for FSVRP. This approach enables the solving of the problem through the application of a standard mathematical optimization solver, offering a generalized solution framework [29]. The primary objective of this problem is to ascertain the most optimal route for drones, encompassing their journey from the base to the customers and subsequently returning to the base. This optimization process is specifically geared towards minimizing flight time by meticulously considering the speed variations induced by different payload weights. The methodologies proposed thus far have significantly contributed to the expansion of the FSVRP framework. Nevertheless, a common assumption in these models is that a solitary drone is capable of delivering all parcels within a single journey. This poses a limitation when the aggregate weight of the parcels surpasses the drone’s maximum payload capacity, resulting in the inability to deliver all packages in one trip. In our research, we introduce an advanced delivery drone routing model that accommodates multiple delivery rounds, taking into account the variations in flight speed due to varying payload weights. The multi-delivery strategy proposed herein is capable of transporting a greater volume of parcels as compared to the FSVRP-Single-trip delineated in [29]. Additionally, it is noteworthy that the FSVRP single trip typically involves a lesser number of parcels per trip. Enhancing the drone’s flight speed while simultaneously reducing total flight duration can lead to a notable decrease in energy consumption. Therefore, in this context, minimizing flight time is synonymous with minimizing energy usage. The structure of this paper is delineated as follows. In Section 2, we detail the FSVRP and elaborate on an integer programming-based method tailored for FSVRP. Section 3 is dedicated to introducing the FSVRP framework extended to encompass multiple deliveries. Section 4 outlines the experimental methodology employed in our study and discusses the findings from our evaluation experiments. Finally, Section 5 serves as the conclusion of this paper, summarizing key insights and contributions.

2. FSVRP

This section describes the Flight Speed-aware Vehicle Routing Problem (FSVRP) defined in [24,25]. Central to FSVRP is the concept of optimizing drone routing by accounting for fluctuations in flight speed, which are contingent upon the payload. The primary objective of this problem is to ascertain the most optimal route for drones, encompassing their journey from the base to the customers and subsequently returning to the base. This optimization process is specifically geared towards minimizing flight time by meticulously considering the speed variations induced by different payload weights. Referencing the scenario depicted in Figure 1a, the node labeled “0” represents the depot, with the remaining three nodes symbolizing the customers. The values enclosed within the boxes at each node specify the weight of the packages designated for delivery, and the numerals alongside the connecting lines denote the distances between these locations. As illustrated in Figure 1b, the optimal route as per the Travelling Salesman Problem (TSP) accumulates a total distance of 197 units, calculated as 33 + 51 + 65 + 48. However, this route is not as efficient in terms of time. Figure 1c demonstrates that the time required for traversing this TSP-optimal route amounts to 44 time units, calculated as 9 + 12 + 14 + 9.

Figure 1. An example of FSVRP. (a) An example; (b) Flight distance of TSP-optimal route; (c) Flight time of TSP-optimal route; (d) Flight distance of FSVRP-optimal route; (e) Flight time of FSVRP-optimal route.

Transitioning to the FSVRP, Figure 1d,e reveal the optimal route under this framework. Here, the FSVRP-optimal route encompasses a total distance of 244 units, detailed as 27 + 65 + 77 + 75. This distance is comparable to that of the TSP-optimal route, though it could potentially exceed it under different conditions. Importantly, the FSVRP-optimal route requires only 43 time-units, calculated as 6 + 14 + 15 + 8, which is less than that of the TSP-optimal route. It is pertinent to note that the speed of the drone inversely correlates with the payload weight. For instance, in the TSP scenario (Figure 1b,c), the drone departs the depot with a total payload of 108, first delivering the lightest 12-unit package to customer 1 and then continuing with a reduced payload of 96. Conversely, in the FSVRP scenario (Figure 1d,e), the drone initially visits customer 2 to offload the heaviest 72-unit package, thereby enabling a higher flight speed for the remainder of the journey. This comparison exemplifies that the TSP-optimal route may not always coincide with the FSVRP-optimal route in terms of efficiency. In the framework of this problem, a total of N parcels are earmarked for delivery. For ease of explanation, we suggest that a single parcel is allocated to a customer. This leads to a situation where the number of customers is equivalent to N. Each parcel is systematically numbered from 1 to N, with the customer intended for the i-th parcel (1 ≤ i ≤ N) being identified as customer i. The starting point, or the depot, is labeled as 0, as shown in Figure 1a. The premise of this research is grounded in the deployment of parcels through a drone under an FSVRP singletrip. The drone is loaded with all parcels at the depot before embarking on its delivery route. In scenarios where the collective weight of the parcels exceeds the carrying capacity of the drone, a preliminary grouping of the parcels is necessitated for efficient routing and delivery. However, the detailed methodology for such parcel partitioning is beyond the purview of this current study. In our proposed approach, the distance between two customers, i1 and i2, is represented by the notation d(i1,i2). Furthermore, the notation x(j) is employed to denote the j-th visited customer, serving as a pivotal decision variable in the context of the routing problem. Taking into account that each route both originates from and culminates at the depot, we set forth the following definition for the purposes of this study:

```latexx(0)=x(N+1)=0```

(1)

```latex1\leq x(j)\leq N(1\leq j\leq N)```

(2)

```latexx(j_1)\neq x(j_2)(1\leq j_1,j_2\leq N,j_1\neq j_2)```

(3)

Additionally, for the purposes of this study, it is explicitly stipulated that each customer is to be visited precisely once, thereby ensuring the uniqueness of each customer’s visit within the proposed routing framework. In this formulation, w(i) is utilized to signify the weight of the i-th parcel. The notation W(j) is employed to represent the cumulative payload of the drone as it departs from the j-th point of visitation. Considering the initial condition where all parcels are loaded onto the drone at the outset of its journey, the subsequent equation is derived to reflect this scenario:

```latexW(0)=\sum\nolimits_{i=1}^Nw(i)```

(4)

As the drone arrives at the j-th stop (1 ≤ j ≤ N) at the location of customer x(j), it proceeds to unload a parcel weighing w(x(j)). Accordingly, the total payload carried by the drone upon its departure from the premises of customer x(j) can be precisely defined as follows:

```latexW(j)=W(j-1)-w(x(j))```

(5)

In this model, the notation t(i1,i2) is used to represent the flight time between customers i1 and i2. The travel duration for the drone’s journey from i1 to i2 is calculated by dividing the distance, d(i1,i2), by the drone’s flight speed, denoted as v. It is critical to recognize that the value of v depends on the drone’s current payload. Therefore, the flight time between the j-th and (j + 1)-th customers, as visited in the sequence, is formally defined as follows:

```latext(x(j),x(j+1))=\frac{d(x(j),x(j+1))}{v(W(j))}```

(6)

The primary goal of the FSVRP is to determine the route that minimizes the cumulative flight time. The objective of FSVRP is formally articulated as follows:

```latex\text{Minimize:}\sum\nolimits_{j=0}^N\frac{d(x(j),x(j+1))}{v(W(j))}```

(7)

In this analysis, it is recognized that the velocity of a drone varies with each model. Moreover, the drone’s speed is influenced by several factors, including the parcel’s weight and other relevant considerations. As depicted in Figure 2a, drones are typically observed flying with their bodies inclined at an angle. In this context, the symbol P represents the drone’s propelling force, while W_d signifies the drone’s inherent weight. To ensure aerial stability and counteract gravitational pull, the vertical component of the propelling force, P_y, must balance with the gravitational force, expressed as W_d∙g. The pitch angle at which P_y effectively balances the force of gravity as indicated by θ. Conversely, the horizontal component of the propelling force, P_x, which propels the drone towards its destination, is balanced by air resistance, represented as k∙v(0), where k is a drone-specific coefficient.

Figure 2. Forces on a drone with payload. (a) A drone without on-board payload; (b) A drone with payload w.

In scenarios involving payload carriage, such as transporting a parcel weighing w, achieving the necessary tilt angle becomes more challenging due to the additional requirement for a vertical force component equivalent to w∙g. This necessitates a reduced pitch angle, denoted as $$θ^{\prime}$$, which must be smaller than θ. Consequently, the horizontal component of the propelling force under these conditions, $$P_x^{\prime}$$, is less than P_x. As delineated in Figure 2, the variable v(w), representing the velocity as a function of weight, is defined in Equation (8). For more comprehensive information and context, readers are referred to [24,25].

```latexv(w)=k\cdot P\cdot\sin\left(\arccos\left(\frac{(W_d+w)\cdot g}{P}\right)\right)```

(8)

In the study referenced as [26], the reciprocal of the function v(w), which describes velocity as a function of weight, is approximated in a linear form as follows.

```latex1/v(w)=1/\left(k\cdot P\cdot\sin\left(arccos\left(\frac{(W_d+w)\cdot g}{P}\right)\right)\right)=a\cdot W(j)+b```

(9)

3. Multi-Trip FSVRP

In the subsequent analysis, we expand upon the methodologies introduced in Section 2, adapting them for scenarios involving concurrent deliveries. The developed framework for handling multiple deliveries accounts for changes in drone flight speed attributable to varying payload weights. This involves scheduling multiple departures from the central depot to ensure the efficient delivery of all parcels. Upon completion of these deliveries, the framework prioritizes the identification of an optimal return path to the depot. The central challenge addressed in this study is the adjustment of flight paths in response to payload-induced speed variations, with the objective of minimizing the overall flight duration. 3.1. An Example We explain a routing conundrum faced by delivery drones, which is predicated on the load-dependent variation in flight speed and encompasses multiple deliveries, as demonstrated through a particular example. Figure 3a delineates the spatial interconnections between the central depot and the customer locations. In alignment with the framework presented in Section 2, the nodes marked as “0” are indicative of delivery hubs, whereas the nodes numbered 1 to 4 denote customer locations. The figures enclosed within the nodes specify the parcel weights and the numerical values on the connecting lines between the nodes represent the respective distances. Given that drones navigate aerially, they are unimpeded by terrestrial constraints, thus enabling direct transit between any two customer points. Further, as depicted in Figure 3b,c, when orchestrating deliveries within a singular circuit, the arrow-marked trajectory denotes the most efficient path as per the FSVRP. The path for the FSVRP is illustrated in Figure 3b,c, wherein the cumulative distance of the trajectory is calculated to be 272 units, derived as follows: 57 + 80 + 27 + 63 + 45. Concurrently, the aggregate flight duration for the optimal FSVRP path is 40 units, calculated as 15 + 11 + 3 + 6 + 5. Conversely, in scenarios where deliveries are executed across several journeys, the trajectory delineated by arrows in the diagrams signifies the most efficient route as determined by the FSVRP with Multiple Trips. This particular route configuration is illustrated in Figure 3d,e, revealing a total traversal distance of 289 units, calculated as (35 + 27 + 80 + 57) + (45 + 45). Notably, this distance exceeds the sum of 272 units observed for the single-trip optimal route in the standard FSVRP framework. Nevertheless, the cumulative flight time for the optimal multi-trip route in FSVRP is calculated to be 33 units, broken down as (6 + 3 + 9 + 5) + (5 + 5), thereby presenting a shorter duration in comparison to the single-trip FSVRP. In the scenario depicted in Figure 3b,c, the drone initiates its journey from the central depot, carrying a total payload of 368 units. Its first destination is customer 3, where it delivers a parcel of 150 units, thereby reducing its payload to 218 units. Following this, the drone navigates to customer 2. Upon reaching customer 2, it offloads a 45-unit parcel, which further decreases its payload to 173 units. Subsequently, the drone’s path leads to customer 1, where it dispenses a 120-unit parcel, culminating in a reduced payload of 53 units. The final leg of its route involves a visit to customer 4, where it delivers the remaining 35-unit parcel, effectively emptying its payload. Having completed its delivery circuit, the drone then returns to the depot, now without any parcel. In the instance illustrated in Figure 3d,e, the drone embarks on its initial delivery sortie from the central depot, bearing a payload of 315 units. The first stop in this route is at customer 1, where it delivers a 120-unit parcel, thereby reducing its payload to 248 units. Subsequently, the drone advances towards customer 2. Upon arrival at customer 2, it dispenses a 45-unit parcel, further diminishing its payload to 203 units. The next destination is customer 3, where it offloads a 150-unit parcel, resulting in a complete depletion of its payload. Post this delivery, the drone makes its way back to the depot.

Figure 3. An example of multi-trip FSVRP. (a) An example; (b) Flight distance of FSVRP-optimal route with a single trip; (c) Flight time of FSVRP-optimal route with a single trip; (d) Flight distance of FSVRP-optimal route with multiple trips; (e) Flight time of FSVRP-optimal route with multiple trips.

For the ensuing delivery, the drone sets off again from the depot, this time with a payload of 53 units. Its sole delivery in this round is to customer 4, where it unloads a 53-unit parcel, once again reducing its payload to zero, and then it makes its return to the depot. This illustration elucidates that segmenting the delivery load into multiple journeys enables the drone to transport a greater quantity of parcels. Additionally, this segmented approach facilitates an increase in flight velocity. As a consequence, there is a notable diminution in the overall delivery duration when compared to the strategy of conveying all parcels in a singular circuit. This finding underscores the efficiency gains achievable through the strategic distribution of delivery loads across multiple trips. 3.2. Integer Programming Formulation This section describes the integer linear formulation of the FSVRP with multiple trips. Within this framework, we suggest that there exist N customers requiring service. Each parcel intended for delivery to customer i is designated as parcel i. This study contemplates scenarios wherein the drone is capable of delivering all assigned parcels in a single flight, as well as situations where such a single-flight delivery is not feasible. Initially, the variable x_i,j,p is introduced as a binary decision variable, indicating whether the drone travels from customer i to customer j during trip p. In this context, i and j belong to the set {0, 1,...,N,N + 1}, with 0 and (N + 1) signifying the depot. In our study, we have not defined i ≠ j. The variable p spans the range {1, 2,...,T}. As articulated in Equation (10), this formulation ensures that the drone does not revisit the same location within a single trip.

```latex\sum_{p=1}^T\sum_{i=0}^{N+1}x_{i,i,p}=0```

(10)

Within each tour, it is a stipulated condition that the drone must visit each customer precisely one time. This requirement is formally established as follows:

```latex\sum_{p=1}^{T}\sum_{i=0,i\neq j}^{N+1}x_{i,j,p}=1(1\leq j\leq N)```

(11)

```latex\sum_{p=1}^{T}\sum_{j=0,i\neq j}^{N+1}x_{i,j,p}=1(1\leq i\leq N)```

(12)

The number of trips originating from the depot (denoted as 0) is constrained to be equal to or less than T. This constraint is formally defined as follows:

```latex\sum_{p=1}^T\sum_{j=0}^{N+1}x_{0,j,p}\leq T```

(13)

In the established framework of the trip, it is defined that the drone does not return to the depot (0) until the completion of the trip. This condition is formally specified as follows:

```latex\sum_{p=1}^{T}\sum_{i=0}^{N+1}x_{i,0,p}=0```

(14)

This model requires that the number of tours concluding at the depot (denoted as N + 1) shall not exceed T. This constraint is formally defined as follows:

```latex\sum_{p=1}^T\sum_{i=0}^{N+1}x_{i,N+1,p}\leq T```

(15)

In the proposed approach, it is explicitly defined that the drone does not initiate a departure from the depot (marked as N + 1) during the course of a trip. This specification is formally expressed as follows:

```latex\sum_{p=1}^{T}\sum_{j=0}^{N+1}x_{N+1,j,p}=0```

(16)

In the outlined framework of the study, it is established as a mandatory condition that the drone is prohibited from travelling directly from the initial depot (0) to the final depot (N + 1). This rule is formally defined as follows:

```latexx_{0,N+1,p}=0 \,(1\leq p\leq T)```

(17)

The constraints for eliminating partial tours are introduced in the following manner, wherein the variable u_i,p is defined as an integer variable. This variable is designated to represent the sequence in which location i is visited during tour p:

```latexu_{i,p}+u_{j,p}+(N+1)x_{i,j,p}\leq N```

(18)

In the established approach, the depot (identified as 0) is excluded from the sequence of visitation. Moreover, the order in which visits occur must adhere to a sequence ranging from 1 up to the total number of destinations. This is defined as follows:

```latexu_{0,p}=0\quad (1\leq p\leq T)```

(19)

```latex1\leq u_{i,p}\leq N+1 \,(1\leq i\leq N+1,1\leq p\leq T)```

(20)

Additionally, within this framework, the variable a_i,j,p is used to denote the total weight borne by the drone when it departs from customer i and proceeds to customer j during trip p, inclusive of the drone’s weight. It is imperative that the variable a_i,j,p does not exceed the weight specified by the customer i. This requirement is formally defined as follows:

```latexa_{i,j,p}\leq(C+W-w_{i})\times x_{i,j,p} \,(1\leq i,j\leq N+1,1\leq p\leq T)```

(21)

Furthermore, it is stipulated that the variable a should be equal to or exceed the weight specified by customer j. This constraint is formally established as follows:

```latexa_{i,j,p}\geq\begin{pmatrix}W+w_j\end{pmatrix}\times x_{i,j,p} \,(1\leq i,j\leq N+1,1\leq p\leq T)```

(22)

Upon reaching a customer’s location, it is a mandatory requirement that the drone completes the delivery of a parcel to that specific customer. This requirement is stated in the following manner:

```latex\sum_{i=0}^{N+1}a_{i,h,p}-\sum_{j=0}^{N+1}a_{h,j,p}=\sum_{j=0}^{N+1}w_{h}\times x_{h,j,p} \,(1\leq h\leq N)```

(23)

Moreover, within each individual trip, it is stipulated that both the number of departures from the initial depot (denoted as 0) and the number of arrivals at the final depot (marked as N + 1) must not exceed one. This specific constraint is formally defined as follows:

```latex\sum_{j=1}^{N}x_{0,j,p}\leq1 \,(1\leq p\leq T)```

(24)

```latex\displaystyle\sum_{i=1}^Nx_{i,N+1,p}\leq1 \,(1\leq p\leq T)```

(25)

The primary objective of the problem explored in this Section is to identify the route that minimizes the overall flight time. Accordingly, the objective function is defined to reflect this goal. It is noteworthy, however, that minimizing flight time is inherently synonymous with reducing energy consumption. Therefore, the focus of this paper is predominantly oriented towards the minimization of energy consumption in drone routing.

```latex\text{Minimize:}\sum_{p=1}^{T}\sum_{i=0}^{N+1}\sum_{j=0}^{N+1}\frac{d_{i,j}\times x_{i,j,p}}{v(a_{i,j,p})}```

(26)

For the purpose of this study, the reciprocal of the function can be approximated in a linear form in the same manner presented in Equation (9).

```latex\frac{1}{v(a_{i,j,p})}=\alpha\times a_{i,j,p}+\beta```

(27)

The multi-trip FSVRP is now formally formulated as an integer programming problem, which can be solved with general-purpose mathematical optimization software.

4. Experiments

In this section, the efficacy of our proposed approach is validated through experiments. Within the scope of this paper, experiments were conducted under two distinct scenarios. The first scenario encompasses situations where the total weight of the parcels surpasses the maximum payload capacity of the drone. The second scenario examines cases where the payload remains within the drone’s maximum capacity. For the purpose of these experiments, we established benchmarks comprising various delivery destination counts, ranging from 5 to 20. This led to the generation of a comprehensive set of 320 problems, allocating 20 problems to each delivery destination count. The geographical positions of these delivery destinations were algorithmically determined, with each being randomly located within a 500-meter radius of the central delivery hub. A time constraint of one hour was imposed on the solution-finding process. In instances where optimization was not achieved within this timeframe, the most favorable solution obtained within the hour was used for subsequent comparative analysis. We have mathematically formalized the problem and solved it using a general-purpose mathematical optimization solver. The experimental setup included a computational platform powered by an AMD Ryzen 7 PRO 4750G processor, featuring 8 cores and 16 threads, and equipped with 64GB of RAM. Additionally, IBM ILOG CPLEX Optimization Studio 20.1 was employed for the computation of solutions. 4.1. Scenarios Where Total Payload Is within Drone’s Capacity In our study, we conducted experiments under conditions where the cumulative payload remained within the drone’s maximum capacity limit. Specifically, the weight of the parcels designated for each delivery destination was randomly determined, ensuring that their total did not exceed 27 kilograms. Figure 4a presents the comparative analysis of the total flight distances normalized against the FSVRP-Single-trip. The vertical axis quantifies the normalized total flight distances, while the horizontal axis categorizes the experiments by the number of delivery destinations. The experimental data reveal that, on average, the FSVRP-Multi-trip exhibited an increase of about 9% in total flight distance compared to the FSVRP-Single-trip. This increment is attributed to the multiple return trips to the delivery base inherent in the FSVRP-Multi-trip. Conversely, Figure 4b illustrates the total flight times, again normalized in relation to the FSVRP-Single-trip. Here, the vertical axis denotes the normalized total flight times, with the horizontal axis representing the number of delivery destinations. TSP-Multi-trip is designed to address the problem of minimizing flight distance, thus demonstrating that it is challenging for TSP-Multi-trip to identify the optimal route from the perspective of flight time. The results clearly demonstrate that the FSVRP-Multi-trip accomplished an average reduction in total flight time by approximately 10% when compared to the FSVRP-Single-trip. This decrease in flight duration can be ascribed to the reduced carrying capacity per trip in the FSVRP-Multi-trip, consequently allowing for increased flight speeds and, thus, a shorter overall flight time.

Figure 4. Results of scenarios where total payload is within drone’s capacity. (a) Normalized total flight distance; (b) Normalized total flight time.

4.2. Scenarios Where Total Payload Exceeds Drone’s Capacity In this section, we conduct experiments in scenarios where the payload surpasses the maximum carrying capacity of the drones. Specifically, the total weight of the parcels for each delivery destination was randomly set to exceed 27 kilograms. Figure 5a displays the results for total flight distance, while Figure 5b illustrates the total flight time. The horizontal axis in both figures represents the number of delivery destinations. The experimental results demonstrate that when the payload surpasses the maximum capacity, the conventional FSVRP (FSVRP-Single-trip) is unable to transport all the parcels. In contrast, employing Multi-trip approach allows for the delivery of all loads.

Figure 5. Results of scenarios where total payload exceeds drone’s capacity. (a) Normalized total flight distance; (b) Normalized total flight time.

5. Conclusions

In this study, we introduced the concept of the FSVRP tailored to scenarios involving multiple deliveries. By segmenting deliveries across several trips, our approach not only augments the capacity for deliverable loads but also yields a decrease in overall delivery time. To evaluate the efficacy of our proposed methodology, we conducted a series of experimental analyses, contrasting it against traditional methods across a diverse set of 320 problem scenarios. The empirical data revealed that, in instances where the parcels were within the payload capacity, the FSVRP-Multi-trip approach resulted in a reduction of total flight time by approximately 10%. Looking forward, our research will venture into exploring the application of multiple drones in addressing routing problems that consider load-dependent variations in flight speed.

Acknowledgments

Not applicable.

Author Contributions

Conceptualization, M.N. and H.T.; Methodology, M.N., H.N., X.K. and H.T.; Software, M.N.; Validation, M.N.; Formal Analysis, M.N.; Investigation, M.N.; Resources, H.T.; Data Curation, M.N.; Writing—Original Draft Preparation, M.N.; Writing—Review & Editing, M.N., H.N., X.K. and H.T.; Visualization, M.N.; Supervision, H.T.; Project Administration, H.T.; Funding Acquisition, H.T.

Ethics Statement

Not applicable.

Informed Consent Statement

Funding

This work is partly supported by Japan Society for the Promotion of Science (KAKENHI Grant Number 20H04160) and partly commissioned by New Energy and Industrial Technology Development Organization (Project Number JPNP22006).

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

References

Joshuah KS, Constantine S, Emma RO’N, Alia L, Alexandra SM, Daniel C. Energy use and life cycle greenhouse gas emissions of drones for commercial package delivery. Nat. Commun. 2018, 9, 1–13. [Google Scholar]

Ma Y-H, Shieh T-H, Hung L-C, Tsai L-C. Research on the new drones design to improve transportation of supplies and medical care for remote mountain area in Taiwan. In Proceedings of the 2021 9th International Conference on Orange Technology (ICOT), Tainan, Taiwan, 16–17 December 2021.

Maximilian K, Christian W. Containing the COVID-19 pandemic with drones—Feasibility of a drone enabled back-up transport system. Transp. Policy 2021, 106, 141–152. [Google Scholar]

Ehsan R, Seyyed MHM, Roya S, Ashkan H. Assessing the sustainability of using drone technology for last-mile delivery in a blood supply chain. J. Modell. Manag. 2021, 16, 1376–1402. [Google Scholar]

Hossein E, Enkhsaikhan B. Last-mile drone delivery: Past, present, and future. Drones 2023, 7, 77. [Google Scholar]

Mohammad M-J, Matthias W. Applications and research avenues for drone-based models in logistics: A classification and review. Expert Syst. Appl. 2021, 177, 114854. [Google Scholar]

Jonathan B, Gertz SD, Ariel F, Tarif B, Hagay F, Chen J, et al. The promising future of drones in prehospital medical care and its application to battlefield medicine. J. Trauma Acute Care Surg. 2019, 87, S28–S34. [Google Scholar]

Alok R, Bhawesh S. Analyzing critical success factors for implementation of drones in the logistics sector using grey-DEMATEL based approach. Comput. Ind. Eng. 2019, 138, 106118. [Google Scholar]

Paula M, Claudia ASA. Delivering blood components through drones: A lean approach to the blood supply chain. Supply Chain Forum Int. J. 2022, 23, 113–123. [Google Scholar]

10.

Marlin WU, Barrett WT. Same-day delivery with heterogeneous fleets of drones and vehicles. Networks 2018, 72, 475–505. [Google Scholar]

11.

Joshuah KS, Constantine S, Emma R.O’N, Alia L, Alexandra SM, Daniel C. Energy use and life cycle greenhouse gas emissions of drones for commercial package delivery. Nat. Commun. 2018, 9, 1–13. [Google Scholar]

12.

Valentina G, Fabrizio L, Gianluca P, Andrea S, Claudio D, Alberto L, et al. New frontiers of delivery services using drones: A prototype system exploiting a quadcopter for autonomous drug shipments. In Proceedings of the 2015 IEEE 39th Annual Computer Software and Applications Conference, Taichung, Taiwan, 1–5 July 2015, volume 2, pp. 920–927.

13.

Gianpaolo G, Gennaro I. An efficient transformation of the generalized vehicle routing problem. Eur. J. Op. Res. 2000, 122, 11–17. [Google Scholar]

14.

James FC, Ángel C, Isaac P, José MS, Paula S. Solving the length constrained K-drones rural postman problem. Veh. Routing Probl. 2021, 292, 60–72. [Google Scholar]

15.

Batool M, Malick N. Hybrid truck-drone delivery systems: A systematic literature review. IEEE Access 2022, 10, 92854–92878. [Google Scholar]

16.

Pedro LG-R, David C, Jose L.A-P, Marcos C, Jose M.L-B. Truck-drone team logistics: A heuristic approach to multi-drop route planning. Transp. Res. Part C Emerg. Technol. 2020, 114, 657–680. [Google Scholar]

17.

Paolo T, Daniele V. An overview of vehicle routing problems. Veh. Routing Probl. 2002, 9, 1–26. [Google Scholar]

18.

Stefan P, Wang X, Bruce G. The vehicle routing problem with drones: Extended models and connections. Networks 2017, 70, 34–43. [Google Scholar]

19.

Di Puglia Pugliese L, Giusy M, Francesca G. Trucks and drones cooperation in the last-mile delivery process. Networks 2021, 78, 371–399. [Google Scholar]

20.

Ho YJ, Byung DS, Lee S. Truck-drone hybrid delivery routing: Payload-energy dependency and No-Fly zones. Int. J. Prod. Econ. 2019, 214, 220–233. [Google Scholar]

21.

Kevin D, Jordan H, Geoffrey GM, Sebastian M. Vehicle routing problems for drone delivery. IEEE Trans. Syst. Man Cybern. Syst. 2017, 47, 70–85. [Google Scholar]

22.

Mario M, Leonardo C, Michele O, Dell’Orco M. En route truck–drone parcel delivery for optimal vehicle routing strategies. IET Intell. Transp. Syst. 2018, 12, 253–261. [Google Scholar]

23.

Sergio MF, Timothy H, Troy W, Robert S, Robert R. Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm. J. Ind. Eng. Man 2016, 9, 374–388. [Google Scholar]

24.

Yusuke F, Ittetsu T, Hiroyuki T. Work-in-progress: Routing of delivery drones with load-dependent flight speed. In Proceedings of the 2019 IEEE Real-Time Systems Symposium (RTSS), Hong Kong, China, 3–6 December 2019, pp. 520–523.

25.

Satoshi I, Keishi A, Yusuke F, Hiroki N, Xiangbo K, Ittetsu T, et al. Load and wind aware routing of delivery drones. Drones 2022, 6, 50. [Google Scholar]

26.

Minh LN, Siu CH, Alvis CMF. Large-Scale multiobjective static test generation for web-based testing with integer programming. In IEEE Transactions on Learning Technologies; IEEE: Piscataway, NJ, USA, 2013; Volume 6, pp. 46–59.

27.

Akito K, Tatsushi N. General conversion of integer programming problems into optimal firing sequence problem of Petri nets. In Proceedings of the 2016 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), Bali, Indonesia, 4–7 December 2016.

28.

Shitikantha D, Ranjana S, Balwinder S. An appliance load disaggregation scheme using automatic state detection enabled enhanced integer programming. In IEEE Transactions on Industrial Informatics; IEEE: Piscataway, NJ, USA, 2021; Volume 17, pp. 1176–1185.

29.

Mao N, Satoshi I, Hiroki N, Xiangbo K, Hiroyuki T. An integer programming based approach to delivery drone routing under load-dependent flight speed. Drones 2023, 7, 320. [Google Scholar]

Drones and Autonomous Vehicles