The Development of an Optimal Operation Algorithm for Food Delivery Using Drones Considering Time Interval between Deliveries

Abstract

These days, many attempts are being made worldwide to use drones for food delivery. Especially in the case of food, fast delivery is required, while maintaining its temperature and taste to the maximum. Therefore, using drones is suitable for food delivery because they can move through the air without being affected by traffic congestion. In this study, the purpose is to develop an optimal algorithm that can complete the delivery of customer food orders in the shortest time using drones. We have applied mathematical-model-based optimization techniques to develop an algorithm that reflects the given problem situation. Since the delivery capacity of drones is limited, and especially small, multiple drones may be used to deliver the food ordered by a particular customer. What is important here is that the drones assigned to one customer must arrive consecutively within a short period of time. This fact is reflected in this mathematical model. In the numerical example, it can be confirmed that the proposed algorithm operates optimally by comparing a case where the arrival time of multiple drones assigned to one customer is limited to a certain time and a case when it is not.

1. Introduction

As COVID-19 becomes endemic, traditional industries, such as production, manufacturing, distribution, and tourism, are recovering, but labor shortages are deepening as digital transformation spreads and various types of jobs increase. In addition, the market for food delivery through app/web has rapidly expanded, due to the unavailability of face-to-face services during the COVID-19 pandemic, and many people who lost their jobs in other industries became engaged in food delivery. However, since the end of the COVID-19 pandemic, many people who were engaged in food delivery have moved to other industries, leading to a shortage of people willing to deliver food. Ultimately, food delivery has faced the problem of labor shortages, like traditional industries [1,2,3].

As a solution to this labor shortage, various efforts are being made to use robots instead of humans. Manufacturing plants are expanding the application of industrial robots that have been used in the past, and processes previously performed by humans, such as inspection, are being performed using artificial intelligence (AI) [4]. In the case of cleaning, like the use of household robot vacuum cleaners, industrial cleaning robots equipped with artificial intelligence are also used to clean airports and ports [5]. Similarly, in the logistics industry, self-driving logistics robots have spread and are now commonly used, and various efforts are being made to solve labor shortages through robots [6].

Recently, DoorDash, an American food delivery platform in San Francisco, United States, is said to be starting drone delivery in the United States, together with Wing, a drone company based in Palo Alto, United Statesoperated by Google’s parent company, Alphabet, based in Mountain View, United States. In March 2024, DoorDash announced a partnership with Wing to deliver food from the American fast food chain Wendy’s by drone. DoorDash has already piloted drone delivery in Australia with Wing. DoorDash subscribers can choose drone delivery as an option when ordering food from certain Wendy’s stores in Virginia, with delivery typically being completed within 30 min. At this time, in order to receive food delivery, there must be a small open space within 2 m of the customer’s house, and there must be no obstacles such as trees. Additionally, due to limitations in the weight that drones can deliver at once, up to three drones are said to be matched to one order.

To deliver food using drones, an operating system should be established based on an optimization algorithm so that an appropriate number of drones can efficiently carry out food delivery orders. In this study, we aim to develop an optimal algorithm for food delivery using drones that can process customers’ food delivery orders in the minimum completion time possible.

A variety of industries are using drones to perform logistics and delivery tasks [7], which are greatly helpful in improving existing infrastructure and increasing efficiency [8]. Delivery using drones differs from conventional truck delivery, in that drones have a limited payload weight and battery capacity and can travel at a constant speed (high speed) regardless of traffic congestion. Therefore, a distinguished operational approach is required to manage drone-based delivery systems [9]. Sajid et al. [10] dealt with the routing and scheduling (the sequence of route operations) problem using mixed-integer linear programming. The payload and battery capacity of the UAV were considered, and a hybrid genetic and simulated annealing (HGSA) approach was presented to solve the problem. Yu et al. [11] introduced the scheduling problem of multiple drones, assuming a situation where customer demand occurs stochastically. It was difficult to determine the number of individual drone deliveries when demand was not deterministic, because the capacity of drones is limited. The performance of the proposed algorithm was verified through simulation. Nishira et al. [12] addressed the FSTSP (Flight-Speed-Aware Traveling Salesman Problem), which included the assumption that the flight speed of a delivery drone changes depending on the load. This problem is generally difficult to solve with a conventional solver application, because the function of drone flight speed is complex. Accordingly, they approximated the function of drone flight speed and converted the problem into integer programming that could be solved with a general-purpose solver. Delivery with drones is an effective way to increase efficiency and reduce costs. However, drones have a limited delivery range due to the fact that their battery capacity and payload is not large. Due to these limitations, studies on integrating conventional trucks and drones in delivery are underway [13]. The cooperation between trucks and drones can shorten delivery times and reduce fuel consumption [14]. Delivery using drones has the advantage of being environmentally friendly compared to delivery using conventional trucks. From this sustainability perspective, research has also been conducted to derive delivery routes that can minimize carbon emissions when deliveries are performed using both trucks and drones [15]. Ko et al. [16] conducted a study on restricting drone flight paths to mitigate the risk of accidental falling. The integrated operations of UGVs (unmanned ground vehicles) and UAVs (unmanned aerial vehicles) differentiate the delivery methods based on the types of goods being delivered and the topographical characteristics. Lu et al. [17] proposed a drone–rider joint delivery mode through multi-distribution center collaboration in the takeout delivery process. They showed that the efficiency can be improved by using the affinity propagation clustering algorithm and the improved tabu search algorithm.

Since customer demand for food delivery varies greatly depending on time and region, shortages or surpluses of delivery drivers can occur. Therefore, optimizing the delivery schedule of drivers for food delivery has been considered important. The studies introduced below have dealt with cases where food is delivered using ground transportation, such as cars or motorcycles. Xue et al. [18] introduced a two-stage model to address this issue. In the first stage, the delivery routes and the required number of delivery drivers of each sub-region during each time period were determined. Following that, the delivery drivers were allocated to specific sub-regions during specific time periods in the second stage. It was found that the delivery process can be completed more rapidly with a reduced number of delivery drivers. In regard to the food delivery issue, the main goal is fast and prompt delivery in order to maintain the freshness of the food. Therefore, most food delivery problems deal with minimizing the delivery time as an objective. In addition, studies were conducted with various goals, such as the fair distribution of delivery tasks, minimizing operating cost, delivery distance, or carbon emissions. Martínez-Sykora et al. [19] proposed a multi-objective problem with the additional goal of equitably distributing the delivery tasks to each delivery person. They developed an integer linear programming model and derived several pareto optimal solutions. Liao et al. [20] dealt with the green meal delivery routing problem (GMDRP), integrating the food delivery and vehicle routing problems. They proposed a multi-objective scheduling model, minimizing the operating costs and carbon emissions. In the first stage, the required number of delivery drivers was determined, and, in the second stage, the initial solution was improved to derive the optimal number of delivery drivers and delivery routes. As follows, the general food delivery services involve a delivery driver visiting one restaurant and delivering food to one or more customers. Steever et al. [21] addressed the issue where a single customer can order from multiple restaurants at once. They defined this new problem as the virtual food court delivery problem (VFCDP). Food ordered from multiple restaurants by a single customer might be delivered all at once by one delivery driver (non-split delivery) or might be delivered separately by multiple delivery drivers (split delivery). A mixed integer linear programming approach was formulated to solve this problem. Moreover, an auction-based heuristic method was developed to reflect dynamic situations. As a result of various numerical experiments, it was found that a non-split delivery method completes the delivery before the last food arrives in the case of split delivery.

Delivery processes by a person using ground transportation may encounter delays due to traffic congestion, unexpected accidents, and other logistical challenges. Following this, the utilization of drones for delivery presents a potential solution to these issues [22]. Therefore, the utilization of drones for delivery is being increasingly applied across various industries. Particularly in the food delivery industry, the emphasis on maintaining freshness and ensuring fast delivery has led to their significant utilization. Consequently, various studies are being conducted to efficiently manage and operate this aspect. Huang et al. [22] derived a UAV food delivery schedule with a minimized delay time. The delivery tasks were clustered according to the delivery destination, and the clustered delivery tasks were split into several groups according to the UAV capacity constraints in order to determine the delivery order. Liu [23] dealt with the dynamic, infinite-horizon vehicle routing problem with two types of food (hot meals and cold drinks), as well as different sizes of orders and drones. It was assumed that different types of food cannot be carried by the same drone, while multiple orders with the same type of food can be carried on the same drone. The objective was to minimize the lateness, which is calculated as the time between placing the order and its delivery subtracted by the time it took to cook. Pinto et al. [24] discussed a network model consisting of customers, restaurants, and drone charging stations. The number and location of drone charging stations was determined, given a limited maximum time that customer can wait. The goal was to maximize the number of customers served; moreover, the more charging stations installed, the more customers can be served. However, the cost for installing charging stations is high, so it was set as a constraint. Bi et al. [25] introduced the SLSM (shared logistics service mode) to the food delivery service to lower the logistics cost and fulfill customer demands. A third-party logistics company picks up the food from several restaurants and delivers it to the customers. They compared the proposed SLSM with the existing TLSM (traditional logistics service mode) through case analysis and showed that the SLSM can reduce the logistics cost and better meet customer needs than the TLSM. Lu et al. [26] established a multi-objective, chance-constrained programming model to minimize the transportation time and cost by comprehensively considering uncertainties due to seasonality and human factors. The efficiency, effectiveness, and reliability were demonstrated using a hybrid beetle swarm optimization algorithm.

It is possible to think of the delivery scheduling problem with drones as being similar to the lateness problem and the job dispatch problem in a factory. Malve and Uzsoy [27] studied the problem of minimizing the maximum lateness on a parallel identical batch processing machine with dynamic job arrivals. Extensive computational experiments showed that the proposed GA provides a good tradeoff between solution time and performance. Chen [28] aimed to simultaneously optimize the average cycle time and maximum lateness in a wafer fabrication factory. The proposed methodology of the new rule was shown to be superior in reducing the average cycle time and maximum lateness simultaneously. Jun and Lee [29] addressed the dynamic single-machine scheduling problem to minimize the total weighted tardiness. They proposed a decision-tree-based approach for the generation of rules automatically with feature-construction- and tree-based learning. This proposed approach has been shown to outperform the existing dispatching rules. Minimizing lateness in the job dispatching problem is similar to minimizing the delivery completion time in a drone delivery system. However, in this study, we consider the maximum allowable time interval between the deliveries of a single order. To illustrate this, an order from a single customer can be thought of as a single process, and multiple processes make up the entire order. This study tries to show that, if a single process requires multiple tasks, ensuring that each of the required tasks is completed within a certain time does not have a significant impact on the overall schedule. This is an important difference between the job dispatch problem and this study.

Most of the studies on drone delivery systems have dealt with the vehicle routing problem, where one drone or multiple drones depart from a depot, visit one or several customers only once, and then return to the depot. However, since drones have limited payloads, it may not be possible to deliver all of the desired items in a single delivery. Therefore, this study addresses a drone delivery system that allows multiple drones to visit the same customer when delivery by a single drone is not possible due to the payload limitation. Especially for food delivery, it is important that multiple deliveries arrive at the same time as much as possible, therefore, this characteristic is considered to develop an optimal operation schedule for food delivery using drones.

2. Materials and Methods

2.1. Problem Description

The objective of this study is to devise an optimal algorithm for drone-based food delivery, aimed at minimizing the total completion time for delivering customers’ orders. There is a restaurant that utilizes drones for delivery services, and there are numerous customers surrounding the restaurant. The restaurant consolidates the received delivery orders and performs deliveries at regular time intervals. When a single customer orders a large amount of food that cannot be delivered by a single drone, the order is split and delivered by multiple drones. Previous research on optimal delivery scheduling using motorcycles or electric vehicles has considered the situation of picking up food from multiple restaurants or delivering food to multiple destinations. However, in the case of drones, the amount of food that can be delivered at a time is limited, so it is difficult to pick up and deliver food from multiple restaurants together. Therefore, this study focuses on a single restaurant.

Figure 1 illustrates the problem context of this study. The numbers within the gray rectangle are the customer numbers, and the numbers within the circles indicate the delivery sequence for each drone. The blue drone loads food from the restaurant and visits Customer 7 first. After completing the delivery to Customer 7 and returning to the restaurant, it loads food again and visits Customer 4, followed by Customer 3. Customers 1, 2, 5, 6, and 7 order a small amount of food, so one drone makes only one delivery. On the other hand, Customers 3 and 4 order a large amount of food that cannot be delivered by a single drone. Therefore, 2 drones make a delivery for Customer 3, and 3 drones for Customer 4. For example, for Customer 4, the blue and green drones each make a second delivery, while the red drone makes a third delivery, resulting in a total of three separate deliveries for Customer 4. Of course, the same drone can also make 2 deliveries in sequence.

Given the nature of food items, ensuring that multiple deliveries are consolidated and delivered simultaneously within a similar time period is important above all else. Therefore, in cases of split food delivery, there is an additional consideration to limit the maximum allowable time intervals between each delivery, enabling the customers to receive their food all at once, as much as possible. By doing so, the customers can enjoy the convenience of receiving their food orders, thereby enhancing their overall satisfaction with the service provided. This not only helps in optimizing the operational efficiency, but also contributes significantly to customer experience and loyalty.

2.2. Mathematical Model

• Set and Index

$I$	Set of customers
$J$	Set of delivery orders
$K$	Set of drones
$v$	Last element of set $J$

• Parameters

$d_i$	Demand (order volume) of customer $i$
$s$	Capacity of a drone
${to}_i$	Travel time from restaurant to customer $i$
$t_d$	Time for unloading food
$t_b$	Time for loading food
$t_m$	Maximum allowable time interval between deliveries for customer $i$
$M$	Positive large number

• Variables

$t_{i,j}^k$	Arrival time of drone $k$ at customer $i$ on $j^{th}$ visit
${ts}_j^k$	$j^{th}$ departure time of drone $k$ at restaurant
$t_{max}$	The time at which all drones complete their final customer service and return to the restaurant
$y_{i,j}^k$	$\mathrm{Binary} \mathrm{decision} \mathrm{variable}; \mathrm{it} \mathrm{is} \mathrm{equal} \mathrm{to} 1 \mathrm{if} \mathrm{a} \mathrm{drone} k\in K$ serves customer $i\in I$ on $j^{th}$ visit

Equation (1) is an objective function that minimizes the time at which all drones complete their final customer service and return to the restaurant.

$$\min \hspace{1em}\hspace{1em}{t}_{max}$$

(1)

Equation (2) represents a constraint where $t_{max}$ ensures the maximum value among the time that each drone returns to the restaurant after completing its delivery to a customer. In other words, it denotes the arrival time of the last drone returning to the restaurant. $t_{i,j}^k$ is the time that each drone arrives at the customer, $t_d$ is the time it takes to unload the food, and ${to}_i$ is the travel time from the customer to the restaurant. Therefore, the left-hand side of Equation (2) can take on many values, but it represents the time that each drone takes to arrive at the customer, unload the food, and return to the restaurant. The delivery completion time ($t_{max}$) should be equal to or greater than the sum of these values and will eventually equal the largest value of the time that each drone returned to the restaurant. Equation (3) limits the number of deliveries made by the drones to each customer. In cases where the demand exceeds the payload capacity of a single drone, an order is divided and delivered by multiple drones. Equation (4) means that the drone can deliver food to only one customer at a time. Equation (5) states that, for a drone to receive a delivery assignment in the next sequence, it should perform a delivery in the current sequence.

$$t_{i,j}^k+t_d+{to}_i\le t_{max} \forall i, \forall k$$

(2)

$$\frac{d_i}{s}\le \sum _{j\in J}\sum _{k\in K}{y}_{i,j}^k \forall i$$

(3)

$$\sum _{i\in I}{y}_{i,j}^k\le 1 \forall j, \forall k$$

(4)

$$\sum _{i\in I}{y}_{i,j}^k\ge \sum _{i\in I}{y}_{i,j+1}^k j\in J-\{v\}, \forall k$$

(5)

Equation (6) means that the initial departure time from the restaurant for all drones occurs after loading food. Equations (7)–(9) represent constraints regarding the departure time from the restaurant in a sequence of drone deliveries. The relationship between the current drone delivery departure time from the restaurant and the next departure time, as perceived from the restaurant’s perspective, and the relationship between the time of arrival at the current customer and the time of arrival at the next customer, as perceived from the drones’ perspective, are comprehensively addressed. The calculation for $t_{i,j}^k$ is expressed by Equations (8) and (9). Equation (8) indicates that the time that the drone arrives at the customer is after the sum of the time that the drone departs from the restaurant and the time it travels from the restaurant to the customer. Equation (9) indicates that the time that the drone departs from the restaurant to the customer is after the sum of the time that the drone arrives at the customer with the previous order, the time that it unloads the food, the time that it returns from the customer to the restaurant, and the time that it loads the new food.

$${ts}_1^k=t_b \forall k$$

(6)

$${ts}_{j+1}^k\ge {ts}_j^k+y_{i,j}^k·\left(2·{to}_i+t_d+t_b\right) \forall i, j\in J-\left\{v\right\}, \forall k$$

(7)

$${ts}_j^k+{to}_i\le t_{i,j}^k+M·\left(1-y_{i,j}^k\right) \forall i, \forall j, \forall k$$

(8)

$$\begin{array}{c}{t}_{i,j}^k+t_d+{to}_i+t_b\le {ts}_{j+1}^k+M·\left(1-y_{i,j}^k\right) \forall i, \forall j\in J-\left\{v\right\}, \forall k\\ \forall i, \forall i^{\prime }, j\in J-\left\{v\right\}, \forall k\end{array}$$

(9)

Equation (10) is applied when considering the maximum allowable time interval between deliveries in cases where a single order needs to be split for delivery due to the payload capacity limit of the drone. Equation (11) is a non-negativity constraint.

$$\left|t_{i,j}^k-t_{i,j\prime }^{k^{\prime }}\right|\le ⌈\frac{d_i}{s}⌉·t_m+M·\left(2-y_{i,j}^k-y_{i,j^{\prime }}^{k^{\prime }}\right) \forall i, \forall j,\forall j^{\prime }, \forall k, \forall k\prime$$

(10)

$$t_{i,j}^k, {ts}_j^k, t_{max}\ge 0 \forall i, \forall j, \forall k$$

(11)

In this study, a mixed integer linear programming (MILP) algorithm is used. To derive the optimal solution, it utilizes IBM ILOG CPLEX Optimization Studio. This method is widely used in scheduling research in the field of logistics and smart factories, and it has been proven in many studies that the solutions derived are optimal.

3. Results

For the numerical experiments, there are total of 100 customers, with food demand for delivery occurring for 10 of them at a specific time. The locations of the restaurant and customers are shown in Figure 2. The blue circles represent customers with demand, and the numbers indicate the customer IDs. The gray circles mean customers with no demand. The food delivery demand per customer is as shown in

Table 1. Food demand for delivery.

Customer	1	2	3	4	5	6	7	8	9	10
Demand	1	1	2	2	3	3	4	4	5	5

.

It is assumed that delivery is possible to customers within 2 km east, west, north, and south of the restaurant. The speed of the drone is set to 36 km/h, referencing the top speed of Amazon’s delivery drones (80.5 km/h) [30], and the travel time is calculated based on that.

Table 2. System parameters.

$\mathit{I}$	$\mathit{J}$	$\mathit{K}$	$\mathit{s}$	${\mathit{t}}_{\mathit{d}}$	${\mathit{t}}_{\mathit{b}}$	${\mathit{t}}_{\mathit{m}}$	$\mathit{M}$
10	4	5	2	40 s	30 s	60 s	10,000

represents the system parameters for the numerical experiments.

The restaurant uses a total of five drones for food delivery and the payload of each drone is two. Therefore, one drone is assigned to Customers 1, 2, 3, and 4; two drones perform the delivery for Customers 5, 6, 7, and 8; and three drones are allocated for Customers 9 and 10. The loading of the food by a drone takes 40 s, while unloading takes 30 s.

Numerical experiments are performed for the following two cases considering the payload limit of a drone, where one order is allocated to multiple drones.

• Case 1: Without considering the maximum allowable time interval between deliveries.
• Case 2: Considering the maximum allowable time interval between deliveries.

The maximum allowable time interval between deliveries is set at 60 s. Therefore, according to Equation (11), the maximum time interval between the first and last delivery is 120 s for two deliveries, and 180 s for three deliveries. The proposed MILP is solved with the commercial mathematical optimization software CPLEX 22.1.

3.1. Case 1

For Case 1, the sequence of customer visits and arrival times for each drone are shown in

Table 3. Results for Case 1 when the number of drones is five.

Drone	Customer				Arrival Time (s)
1	10	5	8	5	187.64	522.60	923.80	1325.00
2	1	10	10	7	229.22	656.07	1041.34	1346.58
3	3	6	8		238.34	711.89	1200.96
4	9	4	9		261.59	698.42	1167.63
5	6	2	9	7	225.20	580.38	971.95	1351.14
Delivery completion time					1472.32

. Since 5 drones perform a total of 18 deliveries, 3 drones complete 4 deliveries each, while the remaining 2 drones complete 3 deliveries each. The time at which all of the drones complete their final customer service and return to the restaurant is 1472.32 s, and the last drone to return is Drone 1.

For Customer 10, with a demand of five and a drone payload capacity of two, a total of three drones perform the delivery. The first food delivery occurs 261.59 s after the order is placed, followed by the second delivery 971.95 s later, and the final delivery is made at 1167.63 s later. Thus, there is an approximate 15-min waiting time between receiving the first delivery and the last delivery. Likewise, Customer 5 has a demand of three, requiring two drones for delivery. The initial food delivery takes place at 492.60 s after the order placement, with the final delivery being completed by 1325.00 s. Consequently, an approximate 13-min waiting time ensues between the deliveries. When an order, especially for food, is divided into multiple deliveries, the customers prefer these deliveries to occur at similar times, if possible.

3.2. Case 2

For Case 2, the sequence of customer visits and arrival times for each drone are detailed in

Table 4. Results for Case 2 when the number of drones is five.

Drone	Customer				Arrival Time (s)
1	6	9	7	5	225.20	721.99	1101.18	1356.12
2	6	3	2	5	225.20	698.75	1067.07	1334.38
3	4	1	7	10	197.62	634.46	981.28	1286.53
4	8	9	10		253.87	779.33	1238.55
5	8	9	10		253.87	779.33	1238.55
Delivery completion time					1503.44

. All of the drones conclude their final customer service and return to the restaurant at 1503.44 s after the first drone departs from the restaurant.

In this case, the time interval between the first and last deliveries should not exceed 180 s for Customers 9 and 10, who receive their deliveries in three separate shipments. Similarly, for Customers 5, 6, 7, and 8, who receive their delivery in two separate shipments, it is ensured that the maximum time interval should not exceed 120 s. Customers 6 and 8 receive all of their food deliveries simultaneously, with the two drones visiting them first. Accordingly, there is no waiting time incurred, despite the food deliveries being divided. For Customer 10, all of their deliveries are assigned to the final customer of Drones 3, 4, and 5, with only approximately 48 s of waiting time occurring between the two deliveries. Compared to the approximate 15-min waiting time in Case 1, there have been remarkably significant improvements. The time that the drone returned to the restaurant after serving the last customer is about 31 s later than that seen in Case 1.

3.3. Sensitivity Analysis

A sensitivity analysis was conducted to verify how the optimal operation schedule of drones changes as the number of drones for delivery changes.

Table 5. Results for Case 1 when the number of drones is six.

Drone	Customer			Arrival Time (s)
1	10	5	9	187.64	522.60	931.51
2	8	2	6	253.87	637.73	992.91
3	7	3	8	107.61	463.56	965.77
4	10	10	6	187.64	572.91	995.75
5	7	1	9	107.61	454.43	955.23
6	9	5	4	261.59	670.50	1015.45
Delivery completion time				1230.95

shows the results of Case 1 with six drones, where each drone made three deliveries. At this point, the last time that all of the drones completed their delivery tasks and returned to the restaurant was 1230.95 s, approximately 4 min faster than when there were five drones. Additionally, for Customer 10, the delivery was made in three separate shipments, with Drone 1 making the initial delivery and Drone 4 making consecutive deliveries twice. The first and second deliveries occurred at 187.64 s at the same time, while the final delivery was completed at 955.23 s, resulting in waiting time exceeding 11 min.

The results of Case 2 with six drones are shown in

Table 6. Results for Case 2 when the number of drones is six.

Drone	Customer			Arrival Time (s)
1	3	8	7	238.34	740.56	1112.04
2	5	9	10	137.33	546.24	1005.46
3	6	9	7	225.20	721.99	1101.18
4	1	8	2	229.22	722.30	1106.16
5	6	4	10	225.20	658.03	1053.29
6	5	9	10	137.33	546.24	1005.46
Delivery completion time				1250.92

. The time for the last drone to return after completing its delivery was 1250.92 s. Considering the maximum allowable time intervals between the deliveries in the split delivery scenario, the delivery was completed approximately 20 s later than that seen in Case 1. However, there are differences in the drone’s sequence of customer visits. In Case 1, Customer 9 was the last destination for Drone 1, the last for Drone 5, and the first for Drone 6. In Case 2, on the other hand, all three drones (Drone 2, 3, and 6) visited Customer 9 as their second destination. In this case, the waiting time between the first delivery and the last delivery for Customer 9 was less than 3 min. Thus, by optimizing the drone’s sequence of customer visits, it is possible to reduce the waiting time between the split deliveries without increasing the overall delivery completion time.

Table 7. Results for Case 1 when the number of drones is four.

Drone	Customer					Arrival Time (s)
1	10	10	5	2	9	187.64	572.91	907.87	1175.18	1566.75
2	6	7	4	8	7	225.20	568.01	883.24	1344.73	1716.21
3	9	3	9	5		261.59	771.51	1281.44	1690.36
4	8	6	1	10		253.87	742.95	1207.36	1634.22
Delivery completion time						1838.33

presents the results of Case 1 when operating four drones. Drones 1 and 2 each completed five deliveries, while Drone 3 and 4 each completed four deliveries, resulting in a delivery completion time of 1838.3 s. When compared to Case 1 with five drones, it increased by about 6 min. For Customer 10, the first food was delivered by Drone 1 at 187.64 s, and the last one was delivered by Drone 4 at 1643.22 s, resulting in a waiting time between deliveries of approximately 24 min.

Table 8. Results for Case 2 when the number of drones is four.

Drone	Customer					Arrival Time (s)
1	9	8	7	5	2	261.59	787.05	1158.52	1413.46	1680.77
2	3	6	7	5	10	238.34	711.89	1054.69	1309.63	1644.59
3	9	6	1	10		261.59	758.37	1222.79	1649.65
4	9	8	4	10		261.59	787.05	1248.54	1643.80
Delivery completion time						1847.28

shows the results for Case 2 when the number of drones was four. The completion time at which all of the drones finished their deliveries and returned to the restaurant was 1847.28 s. Among the customers receiving their deliveries separately, all except Customer 9 received their deliveries within one minute after receiving the first delivery. For Customers 4 and 6, there was a 104-s time interval between the first and last deliveries.

In this manner, when deliveries are divided due to drone payload limitations, setting the maximum allowable time interval between the first and last deliveries may increase the overall delivery completion time. However, considering the characteristics of food delivery, ensuring that the deliveries arrive together within a certain time period may enhance customer satisfaction.

4. Discussion

This study aims to derive an optimal operation schedule for food delivery using drones while minimizing the delivery completion time. Two cases are examined based on whether the maximum allowable time interval between deliveries is considered for multiple deliveries to a customer.

Table 9. Difference in delivery completion time ($t_{max}$) based on the number of drones.

Number of Drones	Case 1 (s)	Case 2 (s)	Difference (s)	Difference (%)
4	1838.33	1847.28	8.95	0.49%
5	1472.32	1503.44	31.12	2.16%
6	1230.95	1250.92	19.97	1.66%

represents how the delivery completion time changes depending on the number of drones operated. As the number of drones for deliveries increased by one, the delivery completion time decreased by approximately 4 to 6 min. The results show that increasing the number of drones in operation is effective in reducing the delivery completion time. However, in practice, increasing the number of drones for delivery will not only have the advantage of reducing the delivery completion time, but also disadvantages such as increased operating and management costs and increased environmental impact. It is important to balance these various factors in order to find the optimal delivery schedule using drones.

Considering the maximum allowable time interval between the deliveries, in Case 2, it was observed that the delivery completion time increases. However, when comparing Case 1, where the maximum allowable time interval between deliveries is not considered, with the scenario where there are four drones, the difference is minimal, being approximately around 9 s and up to about 31 s for five drones, representing a mere 2% variance. Given that the delivery completion time ranges from 20 to 30 min, depending on the number of drones in operation, this discrepancy appears to be quite insignificant. After analyzing these results, it becomes evident that the impact of the maximum allowable time interval between deliveries on the overall delivery completion time is relatively minor. This finding emphasizes the resilience of the delivery system to adapt to varying operational challenges. Furthermore, this indicates that the drone fleet can manage a delivery schedule even with slight adjustment in delivery completion times.

Table 10. The waiting time between deliveries.

Customer	4 Drones (s)		5 Drones (s)		6 Drones (s)
	Case 1	Case 2	Case 1	Case 2	Case 1	Case 2
5	782.48	103.83	802.40	21.74	147.90	0.00
6	517.74	46.49	486.68	0.00	2.84	0.00
7	1148.20	103.83	4.56	119.90	0.00	10.85
8	1090.86	0.00	277.16	0.00	711.90	18.25
9	1305.16	0.00	906.05	57.34	693.64	175.75
10	1446.58	5.85	853.70	47.97	385.27	47.82

indicates the waiting time between the deliveries of each customer. Considering the maximum allowable time interval between the deliveries (Case 2), it is evident that the waiting time between the deliveries for most customers decreases. For example, when there are four drones, the waiting time between the deliveries for all customers significantly decreases. Customer 10, who, in Case 1, waits approximately 24 min between the deliveries of the first and last food, experiences deliveries spaced only 6 s apart in Case 2. Similarly, Customer 9, who, in Case 1, waits about 22 min to receive all foods, received all food simultaneously in Case 2. This demonstrates that, in Case 2, the quality of service can be improved from the customer’s perspective. Moreover, in Case 1, there is a larger variation in the waiting time between the deliveries for each customer compared to Case 2. Such disparity among customers can be a contributing factor to customer dissatisfaction and has a significant impact on the quality of customer service.

5. Conclusions

A food delivery system where a restaurant utilizes drones was addressed in this study. An optimal delivery schedule for the drone was determined, including minimizing the delivery completion time. One of the major differences between drones and traditional delivery vehicles like conventional trucks or motorcycles is their payload capacity. Generally, drones can carry a maximum weight of around 5 lbs, making it challenging to deliver large amounts of food orders with just one drone. Therefore, in such cases, two or more drones are utilized to perform split deliveries. While split deliveries may not pose significant issues for general goods, the nature of food items, as addressed in this study, emphasizes the importance of minimizing the waiting time between split deliveries to ensure that the customer receives their food together as much as possible. If a customer should wait for a certain amount of time between each split delivery, it could significantly impact customer satisfaction. This effect would be even more noticeable for hot food items. Reducing the wait time not only contributes to improved customer satisfaction, but also enhances the overall quality of the service provided by the food delivery system.

To address this problem, a mathematical model was developed, and the results were analyzed through numerical examples. The operation of five drones was assumed as the baseline, and a sensitivity analysis was performed for cases with four and six drones. When considering the maximum allowable time interval between split deliveries, there was a slight increase in the delivery completion time. Furthermore, when considering the maximum allowable time interval between split deliveries, there was a significant decrease in the waiting time between the first and last food deliveries for customers. Through this, it has been confirmed that it is possible to derive delivery schedules that can improve customer satisfaction without significantly increasing the delivery completion time. By optimizing the allocation and sequence of drones and considering the maximum allowable time interval between deliveries, a more efficient and customer-friendly delivery system can be established. This not only enhances the overall quality of the service, but also contributes to customer loyalty and retention. Therefore, implementing such refined delivery schedules holds great potential for fostering positive customer experience and sustaining a competitive advantage in the market.

The contribution of this study can be explained as follows: When considering the vehicle routing problem, commonly addressed in traditional delivery problems, it is difficult to adequately reflect the characteristics of drones, which are typically limited to carrying relatively lightweight items. This study aims to address this gap by considering the payload capacity restriction inherent to drones. Specifically, it considers where orders exceeding the drone’s capacity are split into multiple deliveries, thus providing a more realistic reflection of drone delivery operations. Moreover, the maximum allowable time interval between deliveries has been considered, reflecting the characteristics of food items in the delivery process. This allowed us to minimize the delivery completion time, while ensuring that the customers receive their food deliveries in a similar time period as much as possible. As a result, deriving the optimal food delivery schedule not only minimizes the delivery completion time, thereby efficiently operating the restaurant, but also enhances customer satisfaction.

The limitations of this study are, firstly, that it only focused on delivering food using drones. As further research, an integrated food delivery system that combines traditional manned vehicles like cars and motorcycles with unmanned vehicles like drones and UGVs will be discussed. Electric unmanned vehicles, such as UGVs, offer similar efficiency and environmental benefits to drones. Delivery conducted using cars or motorcycles is affected by road conditions and can have adverse effects on traffic systems, however, it offers the advantage of efficient delivery due to no capacity constraints. Additionally, UGVs can be deployed in areas that are inaccessible to cars or motorcycles for delivery. We have planned to conduct research on determining the optimal delivery schedule and the required number of each delivery vehicle when integrating various means of transportation for delivery. The second limitation is that the problem situation addressed did not reflect the real-world situation. This study focused on the fact that even if the maximum allowable time interval between deliveries is considered to improve the quality of customer service, it does not significantly affect the delivery completion time. As this is one of the first studies to use multiple drones in a single order, it is basic and does not reflect a variety of real-world situations. If real-world locations are used as a case study, different urban environments can affect the results. The same is true for battery issues and uncertain situations. In future works, we plan to conduct research in real-world locations, considering battery issues, such as battery life and management, and uncertain situations, such as delivery delays or unexpected obstacles.