Research on the optimization of delivery routes for vehicles with drones under no-fly zone restrictions

Abstract

With the rapid development of e-commerce, logistics and distribution systems face the dual pressures of efficiency improvement and cost control. Unmanned Aerial Vehicle (UAV) delivery, featuring flexibility, high efficiency, and low carbon emissions, has become an effective means to solve the “last-mile” problem. However, the widespread no-fly zones in urban environments (e.g., airports, government agencies, and high-voltage power lines) severely limit the application scope of UAVs and increase the complexity of path planning. Against this backdrop, the vehicle-assisted UAV collaborative delivery model has emerged: through the division of labor and collaboration between ground vehicles and UAVs, it not only expands the service radius of UAVs but also overcomes the constraints of no-fly zones, achieving dual improvements in delivery efficiency and service quality.This study focuses on the optimization of vehicle-assisted UAV delivery paths under no-fly zone constraints, aiming to construct a multi-objective optimization model that balances delivery costs, carbon emissions, and customer satisfaction, and to design an efficient solution algorithm for providing scientific decision support to logistics enterprises. First, the paper systematically sorts out the classification and definition of no-fly zones as well as their impact mechanisms on UAV path planning, and elaborates on the theoretical basis of vehicle-UAV collaborative delivery, including the constituent elements of the problem, methods for quantifying customer satisfaction, and the application framework of heuristic algorithms. On this basis, a mixed-integer programming model is built with the objectives of minimizing total cost, minimizing carbon emissions, and maximizing customer satisfaction. Given that this model falls into the category of NP-hard problems, we have designed a four-stage heuristic solution. First, an improved K-means algorithm (IKM) is used to cluster customer points under the constraint of the UAV’s maximum flight radius, so as to determine vehicle parking points. Second, a multi-objective genetic algorithm is applied to plan UAV delivery routes for customers in open areas. Next, the multi-objective genetic algorithm is continued to design initial routes for vehicles between parking points. Finally, the multi-objective genetic algorithm is utilized again to plan delivery routes for customers in no-fly zones, ultimately forming a complete collaborative “vehicle-UAV” delivery scheme.To verify the effectiveness of the model and algorithm, simulation experiments are conducted using two sets of cases: 30 customer points in a local area of Harbin and the large-scale R201 case from the Solomon dataset. The results show that compared with traditional vehicle-only or UAV-only delivery models, the vehicle-UAV collaborative delivery model exhibits significant advantages in total cost, carbon emissions, and customer satisfaction; the model maintains good robustness in stability tests under different no-fly zone settings; and parameter sensitivity analysis further reveals the impact of key parameters (e.g., UAV load capacity, endurance, and vehicle load capacity) on delivery performance, providing practical references for logistics enterprises in equipment selection and operation strategy formulation.

1. Introduction

The explosive growth of e – commerce and consumers’ urgent demand for instant delivery have made the “last - mile” problem of logistics delivery a focus of attention in academia and industry. The traditional vehicle delivery model has difficulty meeting the efficient and low – carbon logistics requirements due to defects such as traffic congestion, high carbon emissions, and the rigidity of fixed routes. Drones (Unmanned Aerial Vehicle, UAV), with their flexible take – off and landing, low – altitude obstacle avoidance, and rapid response capabilities, are regarded as a key technology to break through the delivery bottleneck [1,2]. However, drones face multiple challenges in practical applications, such as endurance limitations [3], load capacity constraints [4], and airspace control (e.g., no – fly zones) [5]. The single – drone delivery model is difficult to cover complex scenarios. Therefore, the collaborative delivery of vehicles and drones (Truck – Drone Collaborative Delivery, TDCD) has become a research hotspot. Murray [6] first proposed the vehicle routing problem with drones.It achieves a balance among cost, timeliness, and coverage through resource complementarity [7,8] and has gradually become an important direction for the optimization of modern logistics systems.

In terms of theoretical model construction, early research focused on the basic framework of drone route optimization. Dorling [1] first proposed the multi – trip drone route problem (VRP), optimizing energy consumption and delivery time through mixed – integer programming and simulated annealing algorithms, but did not consider the hard constraints of no – fly zones on the route. hiang [2] constructed a green routing model from the perspective of sustainability, proving that drones can significantly reduce carbon emissions. However, its static order assumption is difficult to adapt to the dynamic logistics environment. Dukkanci [9] systematically sorted out the four collaborative modes of TDCD (parallel, hybrid, truck – assisted drone, and drone – assisted truck), pointing out that the dynamic environment and multi – type vehicle collaboration are the future research directions. However, most existing research focuses on fixed networks and idealized constraints, and there are still obvious gaps in the joint optimization of no – fly zones and real – time order changes [10,11].

In terms of algorithm design and solution, scholars have attempted to combine traditional combinatorial optimization methods with emerging intelligent algorithms. Toy [12] proposed a collaborative scheduling model with trucks as mobile take – off and landing platforms, minimizing the total delivery time through mixed – integer programming, but did not involve route clustering and dynamic adjustment. Baldisseri [13] developed an ant colony optimization (ACO) algorithm to solve the drone-truck pairing problem, achieving a 30% cost savings. However, its clustering process depends on fixed customer grouping and lacks self – adaptability. Kischst [14] proposed a heterogeneous multi – drone collaborative framework, optimizing delivery efficiency through fuzzy C – means clustering and variable neighborhood descent algorithms, but did not consider the route avoidance requirements of no – fly zones.Weng [15] proposed a new two-stage hybrid heuristic algorithm, where the first stage uses an improved K-means clustering algorithm to cluster temporary substations; the second stage optimizes the routes of trucks and drones by combining Tabu Search (TS), Enhanced Genetic Algorithm (GA), and Simulated Annealing (SA).

In addition, dynamic order processing has become a recent research difficulty. Huang [16] used the deep Q – learning method to achieve real – time scheduling, but its model complexity is high and difficult to apply to large – scale scenarios. Marine [17] proposed a variable neighborhood search (VNS) to improve the periodic flight of drones, but the no – fly processing is limited to single – point avoidance and has not been extended to regional – level constraints.

As the core element of airspace control, no – fly zones directly determine the feasibility of drone routes. Eskan [18] reviewed the facility location problem of drone – riding vehicles, emphasizing that the intersection point planning needs to take airspace restrictions into account, but did not propose a dynamic collaborative mechanism. Benarbia [19] proposed the optimization of charging station deployment, balancing endurance and cost through a MINLP model, but its route planning is not linked with no – fly zones. Chang [20] studied the collaborative delivery of drones and public transportation, constructing a charging station deployment model, but did not solve the dynamic avoidance problem of no – fly zones. Liu [21] constructed a mixed-integer linear programming (MILP) model that considers no-fly zones and the joint service path optimization problem for trucks and drones that handle both pickup and delivery.

Wang [22] reviewed 95 papers on mixed truck – drone delivery and pointed out that only 12% of the research involved airspace restrictions, and most of them adopted static avoidance strategies. Existing models such as Huang [23] genetic algorithm only deal with fixed no – fly zones and lack dynamic collaboration with vehicle routes.However, In recent research directions such as reinforcement learning, graph neural networks, and multi-agent cooperation, Chen [24] personalized longitudinal motion planning based on reinforcement learning and imitation learning methods, considering multiple performance indicators as well as the driver’s acceptance of the vehicle’s driving style. Chen [25] proposed an integrated eco-driving framework for fuel cell hybrid electric vehicles in a multi-lane highway scenario, synchronously optimizing the delivery route through a unified continuous control variable.

As a key indicator of logistics service, most existing models focus on time – window penalties [26], while ignoring the exponential impact of delivery timeliness on customers’ psychology. Crisan [27] proposed a multi – objective optimization model that combines carbon emissions and time cost, but its satisfaction function does not quantify customers’ psychological expectations. Boysen [28] pointed out through empirical analysis that customers’ acceptance of drones is closely related to delivery speed and privacy risks, and a more practical satisfaction model needs to be constructed. Li [29] compared the environmental impacts of drones and motorcycles, proving that low – carbon delivery can indirectly improve customer satisfaction, but did not establish a direct correlation function.

In response to the above problems, this paper proposes a route optimization model for vehicle – drone joint delivery under no – fly zone constraints, with the following innovations:

1. (1). It constructs a multi-objective optimization model for vehicle-UAV collaborative delivery under no-fly zone constraints, overcoming the limitation of ignoring airspace restrictions in traditional path optimization studies.

2. (2). It proposes a phased solution strategy that integrates an improved clustering algorithm with multiple meta-heuristic algorithms, effectively enhancing the solution efficiency and quality for large-scale problems under complex constraints.

3. (3). It verifies the applicability and stability of the model and algorithm in real-world scenarios through empirical analysis, providing theoretical support and practical guidance for logistics enterprises to promote intelligent and green delivery.

The structure of this article is as follows: Chapter 2 constructs a vehicle delivery route optimization model with drones under the constraint of no-fly zones; Chapter 3 details the design and implementation process of the multi-stage algorithm; Chapter 4 verifies the effectiveness of the model through small-scale and large-scale examples, and analyzes the sensitivity of parameters and the model performance in different scenarios; Chapter 5 summarizes the research conclusions and presents future research directions. Based on existing research, this study provides a theoretical foundation for the vehicle delivery route planning problem with drones by considering the constraint of no-fly zones, as well as a decision support tool for logistics companies that offers low costs and high satisfaction.

2. Vehicle-assisted drone delivery route optimization considering no-fly conditions

2.1 Problem description

This study plans vehicle-assisted UAV collaborative delivery routes under the constraint that there are UAV no-fly zones in the delivery area. The problem can be described as follows: A logistics enterprise establishes a mixed fleet consisting of vehicles and UAVs to perform delivery tasks. Before delivery, vehicle parking points are first determined based on the results of customer point clustering. Vehicles, carrying UAVs and goods, depart from the distribution center and pass through vehicle parking points in sequence. At each parking point, UAVs take off from the vehicle to deliver goods to customer points in the open area belonging to that parking point. After all UAVs have completed deliveries to customers in the open area and returned to the vehicle, the vehicle then delivers goods to customer points located within no-fly zones. Subsequently, the vehicle, carrying the UAVs, proceeds to the next parking point to continue the delivery task until all customer points have been served, and finally returns to the distribution center.

In the delivery area of the logistics enterprise, there are restrictions imposed by no-fly zones: customers within no-fly zones cannot be served by UAVs and must be served by vehicles. Therefore, this study establishes a route planning model for vehicle-assisted UAV delivery and formulates a scientific and reasonable path optimization scheme to achieve the goals of minimizing logistics operation costs, minimizing carbon emissions, and maximizing customer satisfaction.

2.2 Model assumptions

1. Assumption 1: Each customer belongs to only one clustering point (cluster center).

2. Assumption 2: The cluster center is the vehicle stopping point, and the cluster center does not coincide with the customer point.

3. Assumption 3: There is only one distribution center.

4. Assumption 4: Each vehicle carries m on-board UAVs.

5. Assumption 5: The flight routes of UAVs for delivery are Manhattan routes.

6. Assumption 6: Under the constraints of drone carrying capacity and endurance, the drone can continuously deliver to multiple customer points.

7. Assumption 7: The flight speed of a UAV during delivery is inversely proportional to its load weight.

8. Assumption 8: Customer points within no-fly zones are served by vehicles, while customer points in open areas are served by UAVs.

9. Assumption 9: Customers in open areas are referred to as Type 1 customers, and customer points within no-fly zones are referred to as Type 2 customer points. If a vehicle parking point has Type 2 customer points, the vehicle must wait for the UAVs to finish delivering to Type 1 customers and return to the vehicle before delivering to Type 2 customers; thereafter, the vehicle proceeds to the next parking point.

10. Assumption 10: For the convenience of calculation, this paper uses the Manhattan distance for calculating the UAV flight distance between two points. However, in an environment with complex no-fly zones, the length of the UAV’s actual detour path may be much longer than the Manhattan distance.

2.3 Model parameters and variables

The model parameters constructed in this paper are mainly divided into three categories: constants, sets, and variables. The specific symbols and their meanings are shown in Table 1.

[Figure omitted. See PDF.]

2.4 Construction of UAV flight speed function model

In practice, it is common for UAVs to have speed differences due to varying weights of delivered goods. Therefore, this paper assumes that the flight speed of a UAV under full load (i.e., when the UAV is at its maximum load capacity) is , and its flight speed under no load (i.e., when the UAV has zero load) is ; the speed of both vehicles and UAVs during delivery is inversely proportional to their load weight (refer to Assumption 7). Thus, the flight speed of a UAV when delivering goods with weight w can be expressed as follows:

(1)

2.5 UAV route planning model considering no-fly zones

According to Assumption 5, UAV delivery routes follow the Manhattan distance principle. For the convenience of planning, this paper adopts the grid method to divide the delivery area into 2D grids and 3D grids for analysis. Given that there are no-fly zones in the delivery area (in this paper, no-fly zones only affect UAV delivery and have no impact on vehicle delivery), values are assigned to grids to define whether they belong to no-fly zones. As shown in Fig 1, white grids represent open areas, while black grids represent no-fly zones.

[Figure omitted. See PDF.]

The grid method is a spatial discretization representation method, often used in fields such as path planning and environment modeling. It divides continuous space into regular grid units, and each grid can be assigned different attributes. Through the operation and analysis of grids, it realizes the modeling of spatial environments and related tasks, converting complex spatial problems into computable problems based on discrete grids. For example, in UAV delivery scenarios, dividing the delivery area into grids facilitates the planning of obstacle-avoiding flight paths. As shown in equation (2), black grids are defined as no-fly areas and assigned a value of 1, while white grids are defined as flyable areas and assigned a value of 0.

Let the 2D grid matrix be with a size of m × n, and the grid coordinates be represented by (x,y). Then, the state of a grid can be expressed as equation (2):

(2)

To calculate the 3D flight distance of the UAV, first, this paper defines the Manhattan distance of the UAV between the start point and end point in the 2D grid is shown in equation (3):

(3)

Here, refers to the sum of the total horizontal movement distance and total vertical movement distance of the UAV from the start point to the end point. This is because obstacle avoidance is required for UAV flight due to the existence of no-fly zones, so the optimal path is searched from four directions. However, this paper does not discuss how to find obstacle-avoiding paths, but only focuses on calculating the distance of such paths.

The Fig 2 clearly show that the Manhattan distance from the start point to the end point is actually the sum of the total horizontal movement distance and total vertical movement distance between the two points. However, in a 3D environment (as shown in Fig 3), there is an additional “height” (Z-axis) compared to the 2D environment. UAVs need to travel along “vertical lines” or “diagonal lines” during takeoff and landing. Therefore, the flight path planning in 3D grids can be divided into two steps: horizontal obstacle-avoiding route in the air + takeoff and landing routes.

[Figure omitted. See PDF.]

[Figure omitted. See PDF.]

Thus, the 3D flight (as shown in Fig 4) can be split into three phases for analysis: the Takeoff Phase (TP), the Cruise Phase (CP), and the Landing Phase (LP):

1. Takeoff Phase (TP): From the ground to the cruise altitude, following a “vertical” takeoff path.

2. Cruise Phase (CP): From point A to point B, following an obstacle-avoiding path in the 2D grid (horizontal movement with constant altitude).

3. Landing Phase (LP): From the cruise altitude to the ground at the target point, following a “vertical” landing path.

For the Takeoff Phase and Landing Phase, it is assumed that the UAV takes off and lands vertically (i.e., the altitude changes from 0 to H). The physical flight distances of the Takeoff Phase and Landing Phase are the same. The distance of the Takeoff Phase is shown in equation (4):

(4)

By substituting the horizontal movement speed , , vertical speed , and (representing takeoff time), the equation (5) can be obtained:

[Figure omitted. See PDF.]

(5)

Let H=, Therefore, the total 3D distance of the UAV between two points is equal to the sum of the Takeoff Phase distance, Cruise Phase distance, and Landing Phase distance, which is shown in equation (6):

(6)

2.6 Cost function construction

In the model constructed in this paper, the cost consists of three components: the cost incurred by vehicle delivery, the cost of drone delivery, and the time penalty cost caused by early or late delivery. This is shown in Equation (7) below:.

(7)

Where represents the delivery cost generated by vehicle delivery, represents the delivery cost generated by drone delivery, and represents the time penalty cost for early or late arrival at customer points.

1. (1). The delivery cost incurred by vehicles mainly consists of two parts, as shown in Equation (8):.

(8)

where represents the fixed cost of the vehicle, which usually refers to the basic, normal and inevitable costs related to vehicle use. These costs do not fluctuate significantly with the vehicle’s traveling mileage or usage time. Therefore, the fixed cost of a single vehicle delivery per unit is set as a fixed value .

(9)

In Equation (9), C represents the distribution center, represents the set of vehicle parking points and customer points, represents the fixed cost per vehicle, and represents the number of vehicles dispatched from the distribution center to the set of vehicle parking points and customer points for the first stop..

represents the transportation cost incurred by vehicles, which mainly refers to the cost generated by fuel consumption. Its calculation method is the product of the vehicle’s driving distance, the fuel consumption coefficient per unit distance, and the cost per unit fuel consumption:.

(10)

In Equation (10), Represents the cost per unit fuel consumption, Represents the vehicle fuel consumption coefficient per unit distance, represents the set of all nodes,and represents the total driving distance of all vehicles.

1. (2). The costs generated from drone delivery are primarily the transportation costs of the drone. The unit flight distance cost of the drone is understood as the electricity consumption during flight, various acquisition configurations, and other expenses, with these costs averaged out over the flight distance. The calculation method for drone transportation costs is the product of the drone’s flight distance and the unit flight distance cost of the drone.

(11)

In Equation (11), represents the set of on-board UAVs carried by the vehicle, and represents the total flight distance of all UAVs.

1. (3). The time penalty cost for customer points in this study refers to the cost incurred when goods are delivered earlier than the earliest required time or later than the latest required time by vehicles or UAVs. In such cases, the time delay cost for the customer point is the product of the unit time penalty cost coefficient and the delay duration.

As shown in Fig 5, the calculation formula for the time penalty cost of customer point i is given by Equation (12) as follows:

[Figure omitted. See PDF.]

(12)

In Equation (12), represents the earliest and latest acceptable delivery times for customer i; represents the difference between the actual delivery time to the customer point and the earliest required time by the customer point; and represents the difference between the actual delivery time to the customer point and the latest required time by the customer point.Then, the calculation formula for the total time penalty cost of all customer points is given by Equation (13) as follows:

(13)

2.7 Construction of carbon emission function

Vehicle delivery consumes fuel, which in turn generates carbon emissions. However, drone delivery consumes electricity and does not produce carbon emissions. According to relevant literature, the ratio of unit fuel consumption to the resulting carbon emissions is approximately 2.3 [30].Therefore, in this paper, the calculation formula for carbon emissions is given in Equation (14) as follows:

(14)

2.8 Construction of the customer satisfaction function model

Factors affecting customer satisfaction mainly include product quality, service quality, delivery experience, price factors, and the speed of delivery time. In the model of this paper, the focus is placed on the impact of delivery time on customer satisfaction.

As shown in Fig 6, the function describing the impact of delivery time on the satisfaction of customer point i is presented in Equation (15) below:

[Figure omitted. See PDF.]

(15)

As indicated in the above equation (15), when the goods are delivered to customer point i by vehicle or drone within the time window required by the customer, the satisfaction of customer point i is 1. If the delivery is earlier or later than the required time window, the satisfaction decreases linearly. When the delivery exceeds the maximum acceptable time window of the customer point, the satisfaction is 0. In this paper, the final goal is to calculate the average satisfaction of all customer points, and it is shown in Equation (16):

(16)

2.9 Model establishment

Optimization Objectives:

(17)(18)(19)

Constraints:

(20)(21)(22)(23)(24)(25)(26)(27)(28)(29)(30)(31)(32)(33)(34)(35)

Equation (17) represents the minimization of delivery costs; Equation (18) represents the minimization of carbon emissions; Equation (19) represents the maximization of average customer satisfaction; Equation (20) represents that each customer point can only be served once by either a vehicle or a drone, with no repeated deliveries allowed; Equation (21) ensures that the sum of the number of customer points assigned to all cluster centers equals the total number of customer points; Equation (22) ensures that each customer point belongs to only one cluster center; Equation (23) represents that the total customer demand at all vehicle stop points reached by vehicles must not exceed the maximum load capacity of the vehicles; Equation (24) represents that the total demand weight of all customers delivered by drones taking off from vehicle stop points must not exceed the maximum load capacity of the drones; Equation (25) represents that the total driving distance of vehicles from the distribution center to their return to the distribution center must not exceed the maximum endurance distance of the vehicles; Equation (26) represents that the total flight distance of drones from their departure from vehicle stop points, through customer deliveries, to their return to vehicle stop points must not exceed the maximum flight endurance distance of the drones; Equation (27) represents that vehicles depart from the distribution center and finally return to the distribution center; Equation (28) represents that drones depart from vehicle stop points and finally return to vehicle stop points; Equation (29) represents that each vehicle stop point is allowed to be visited only once. The first part of Equation (30) represents that the time when a drone leaves a customer point is equal to the sum of the time it arrives at the customer point and the service time at that customer point; the second part represents that the time when a vehicle leaves a customer point is equal to the sum of the time it arrives at the customer point and the service time at that customer point; The first part of Equation (31) represents that when a vehicle travels from node to node, the arrival time at node is equal to the sum of the departure time from node and the travel time from node to node; the second part represents that when a drone flies from node to node, the arrival time at node is equal to the sum of the departure time from node and the flight time from node to node; Equation (32) represents that the departure time of a vehicle from a stop point is the latest time when all on-board drones of that vehicle at that node return to the vehicle stop point; Equation (33) represents 1 if a vehicle travels from node to node, otherwise 0; Equation (34) represents 1 if a drone flies from node to node, otherwise 0; Equation (35) represents 1 if stop point s is delivered by vehicle k, otherwise 0..

3. Algorithm construction

Based on the characteristics of the problem and model solved in this paper, a multi-stage heuristic algorithm is designed to solve the vehicle-drone collaborative delivery path. The principles of the algorithm at each stage are as follows:

In the first stage, according to the coordinates of customer points, an improved K-means algorithm is used to divide all customer points into n groups. Each group has a cluster center, and each cluster center has a clustering radius, which is the maximum flight radius of the drone. The purpose is to ensure that each drone can depart from the cluster center, deliver to at least one customer point, and then return to the cluster center. The cluster center is the location where the vehicle stops, so the obtained cluster center is called a vehicle stop point.

In the second stage, based on the n cluster centers obtained in the first stage, each cluster center is analyzed in turn. Since this paper considers the path planning problem of vehicle-assisted drone delivery, drones may encounter no-fly zones and thus be unable to deliver. Therefore, the customer points of each cluster center can be divided into two categories: the first category is customer points in open areas (these can be delivered by drones), and the second category is customer points in no-fly zones (these cannot be delivered by drones). In this stage, path planning is performed for the first category of customer points. The specific planning method uses a genetic algorithm to ensure that each customer point in the first category is delivered exactly once. After completing the planning for the first category of customer points at each stop point in turn, the drone delivery plan for each stop point is obtained, as shown in Equation (36).

(36)

In the third stage, the vehicle delivery path is planned for the first time. The planning objects are the distribution center and all cluster centers (i.e., vehicle stop points). Here, each vehicle stop point is regarded as a customer point, and each vehicle stop point has a demand (the sum of all customer demands at that stop point). The requirement is that vehicles depart from the distribution center, meet the maximum load and maximum endurance requirements of the vehicles, deliver to all vehicle stop points in sequence, and then return to the distribution center. Since the starting and ending points are fixed, and the number of stop points to be delivered is related to the delivery order of the stop points, the demand of the stop points, and the maximum endurance of the delivery vehicles, a variable neighborhood search algorithm is used in this stage. Finally, the initial vehicle delivery plan is obtained, as shown in Equation (37).

(37)

In the fourth stage, the vehicle delivery path obtained in the third stage is re-planned. Specifically, the second category of customer points (those that cannot be delivered by drones) at each cluster center are arranged to be delivered by vehicles. After a delivery vehicle arrives at a vehicle stop point, drones first deliver to the first category of customer points. After all drones have completed their deliveries and returned to the vehicle, the vehicle then delivers to the second category of customer points in no-fly zones in sequence, and proceeds to the next stop point after completion. Therefore, the path planning problem in this stage is essentially a variant of the Traveling Salesman Problem (TSP) with fixed start and end points. Thus, an ant colony algorithm is used in this stage to obtain the vehicle delivery plan for each stop point, as shown in Equation (38).

(38)

In summary of the algorithms in each stage, the final vehicle-assisted drone delivery path plan is obtained, as shown in Equation (39).

(39)

3.1 Phase 1-determining vehicle stop points using improved clustering algorithm

The traditional K-means algorithm aims to assign customer points to the nearest cluster center, minimizing the sum of squared distances from points within each cluster to their respective cluster center. However, the traditional K-means algorithm does not consider distance constraints, i.e., it does not limit the maximum distance from customer points to the cluster center. In the model of this paper, drones have a maximum endurance range. Therefore, to ensure that each drone can deliver to at least one customer and return to the cluster center, it is necessary to restrict the maximum distance from customer points to the cluster center; otherwise, there may be a customer point in a non-no-fly zone that cannot be delivered by either vehicle or drone.To address this limitation of the traditional K-means algorithm, this paper proposes the following improvements: After obtaining the clustered customer data using the traditional K-means algorithm, check whether the Manhattan distance from all customer points to their assigned cluster center is less than the drone’s delivery radius. If all points satisfy this condition, clustering is completed. Otherwise, increase the number of cluster centers, re-perform clustering, and repeat the process until the condition is met, thereby completing the clustering of all customer points. The pseudocode of the improved K-means (IKM) algorithm is shown in Table 2 below:

[Figure omitted. See PDF.]

3.2 Phase 2 – Solving drone delivery routes

In the first stage, this paper first uses the improved K-means algorithm to obtain the cluster centers, i.e., vehicle stop points. Meanwhile, the customer points belonging to each vehicle stop point are also identified. The customer points under each vehicle stop point can be divided into two categories: the first category includes customer points in open areas (these can be delivered by drones), and the second category includes customer points in no-fly zones (these are delivered by vehicles). In the algorithm of the second stage, route planning for drone delivery is conducted for each cluster center (vehicle stop point) and its associated first-category customer points.

First, let all cluster centers (vehicle stop points) be denoted as , and all customer points under a cluster center be denoted as . Among them, represents customer points in open areas, and represents customer points in no-fly zones. The composition of elements within the delivery range of a cluster center is shown in Fig 7 below.

[Figure omitted. See PDF.]

As shown in Fig 7 above, for the convenience of calculation and planning, the delivery area in this paper is divided using a grid method, which facilitates marking open areas and no-fly zones. Since drones cannot deliver to customer points in no-fly zones, a detour strategy is adopted when a drone’s delivery route passes through a no-fly zone. However, regardless of the specific detour route, the flight distance is calculated using the Manhattan distance. This is illustrated in Fig 8 below:

[Figure omitted. See PDF.]

As shown in the Fig 8, the genetic algorithm is used to plan the drone delivery scheme for cluster centers, and the pseudocode of the algorithm is presented in Table 3 below.

[Figure omitted. See PDF.]

According to Model Hypothesis 4, the vehicle carries multiple UAVs. However, due to the limited endurance and payload of UAVs, multiple UAVs will be used to perform the delivery tasks at the current stop. Therefore, it is first necessary to “match” the customers at this stop with the UAVs to ensure that all customers at this stop are delivered by UAVs exactly once. The matching rules are as shown in the above table. Among them, steps 3 and 4 calculate the cumulative demand and cumulative flight distance of the customer set of the initial delivery route, and step 5 finds the customer points that meet the requirements simultaneously. The specific explanations for these steps are as follows: Keep the order of the customer point set {m} unchanged. Starting from the first customer in the set {m}, select one more customer point each time in order. Calculate the flight distance and payload required for the UAV to take off from the vehicle stop, deliver these customers, and then return to the stop. If it meets the rated payload and endurance of the UAV, add the customer point to the delivery task of this UAV. Otherwise, end the matching of this UAV, delete the customers that have completed the matching, and continue the matching work of the next UAV among the remaining customer points until the matching of all customers in {m} is completed.

The above – mentioned operation method is the matching principle of the UAV delivery scheme designed in this paper when the vehicle is at a stop. However, according to the above – mentioned matching method, only one UAV delivery scheme can be matched for one chromosome (here referring to the customer point set {m} at this stop). In this paper, the optimization goals are to minimize the delivery cost and maximize the customer satisfaction, and both of these two optimization goals are related to the flight distance of UAVs. Therefore, next, with the goal of minimizing the flight distance of the UAV delivery route, the genetic algorithm is used for the “chromosome” at this stop to find the optimal UAV delivery route. The specific steps of using the genetic algorithm for solving are as follows:

1. (1). Initial chromosome encoding: Use the customer numbers of the customer point set {m} at the stop as the initial chromosome encoding.

2. (2). Initialize the population: Randomly generate n chromosomes by shuffling the order of the initial chromosome as the initial population.

3. (3). Crossover: Determine the chromosome crossover probability cr, and perform crossover operations on the n populations in sequence. The crossover rule is to cross with the adjacent population, using the two – point crossover method. The crossover rule is shown in Fig 9.

[Figure omitted. See PDF.]

1. (4). Mutation: Determine the chromosome mutation probability mr, and judge whether each population mutates in sequence. If so, reverse the order of the population, as shown in Fig 10.

[Figure omitted. See PDF.]

1. (5). Selection: Combine the parent population and the offspring population after crossover and mutation, and use the roulette wheel selection strategy to re – select n populations from these 2n populations as the parent population for the next iteration.

2. (6). Check whether the number of iterations meets the preset maximum number limit. If it does, output the result; otherwise, go to step 3.

3.3 Phase 3 – Solving initial vehicle delivery routes

In the third stage of the algorithm, the path planning problem considered in this paper can be described as follows: a delivery scenario consisting of one distribution center and multiple vehicle stop points, where each delivery vehicle is required to depart from the distribution center, reach the vehicle stop points in sequence, and finally return to the distribution center. Here, vehicle stop points can be regarded as “customer points,” and the demand quantity of each vehicle stop point varies because the number of customers included in each vehicle stop point and the demand quantity of each customer are different. However, what remains consistent is that each delivery vehicle has the same load capacity and endurance mileage. Therefore, the objective of the third stage is to determine a set of vehicle delivery plans (with at least one vehicle delivery route in the plan). Each vehicle delivery route consists of the distribution center and vehicle stop points. Starting from the distribution center and finally returning to it, each vehicle must not exceed its maximum load during delivery, on the basis that all vehicle stop points are served by exactly one vehicle, and the total driving distance of each vehicle is minimized.

At this stage, with the optimization objectives of minimizing distribution cost, minimizing carbon emissions, and maximizing customer satisfaction, the specific steps for solving using the genetic algorithm are as follows:

1. (1). Initial chromosome encoding: The stop numbers are used as the initial chromosome encoding.

2. (2). Initial population initialization: Randomly generate n chromosomes with the order of initial chromosomes shuffled as the initial population.

3. (3). Crossover: Determine the chromosome crossover probability, and perform crossover on each population in sequence.

4. (4). Mutation: Determine the chromosome mutation probability, and judge whether each population mutates in sequence. If yes, reverse the order of the population.

5. (5). Selection: Calculate the fitness of the offspring population (including distribution cost, carbon emissions, and satisfaction), merge the parent population and the offspring population into a Pareto optimal solution set, and select the top n populations from these 2n Pareto solutions as the parent population for the next iteration.

6. (6). Check whether the number of iterations meets the preset maximum number of iterations limit. If satisfied, output the first solution on the Pareto frontier as the optimal solution; otherwise, return to Step 3.

3.4 Phase 4 – Solving the complete vehicle-assisted drone delivery route

The third stage focuses on researching the vehicle delivery routes between the distribution center and multiple vehicle stop points. Its purpose is to conduct the initial planning of vehicle delivery routes, facilitating subsequent adjustments to the routes. Specifically, it involves planning the vehicle delivery route scheme for the second category of customer points (customers in no-fly zones, who can only be delivered by vehicles) at the cluster centers from the first stage.

First, according to the assumptions in this paper, after a vehicle arrives at a vehicle stop point, it first uses drones to deliver to customers in open areas. Only when the drones complete delivery to the last customer in the open area of that stop point and return to the vehicle will the vehicle start delivering to the customer points in the no-fly zone of the stop point. Finally, the vehicle proceeds to the next vehicle stop point, as shown in Fig 11 below.

[Figure omitted. See PDF.]

However, when planning the vehicle delivery scheme for customer points in the no-fly zone of a vehicle stop point, there are three scenarios as follows:

When the number of customer points in the no-fly zone of the vehicle stop point is 0, the optimal feasible solution for Stage 4 is jointly formed by the current vehicle stop point and the next vehicle stop point , which is ;

When the number of customer points in the no-fly zone of the vehicle stop point is 1, the optimal feasible solution for Stage 4 is jointly formed by the current vehicle stop point and the next vehicle stop point , which is ;

When the number of customer points in the no-fly zone of the vehicle stop point is greater than 1, the feasible solution is jointly formed by the current vehicle stop point , the set of customers in the no-fly zone of the current vehicle stop point , and the next vehicle stop point .

For the first two cases, the optimal feasible solutions are and ; For the third case, this feasible solution is essentially a Traveling Salesman Problem (TSP) with fixed start and end points. In this case, it is necessary to use the genetic algorithm to solve for the optimal distribution route in. With the optimization objectives of minimizing distribution cost, minimizing carbon emissions, and maximizing customer satisfaction, the specific steps for solving the third case using the genetic algorithm are as follows:

1. (1). Initial chromosome encoding: Use the numbers of the second-type customer points at the stop as the initial chromosome encoding.

2. (2). Initial population initialization: Randomly generate n chromosomes with the order of the initial chromosomes shuffled as the initial population.

3. (3). Crossover: Determine the chromosome crossover probability, and perform crossover on each population in sequence.

4. (4). Mutation: Determine the chromosome mutation probability, and judge whether each population mutates in sequence. If yes, reverse the order of the population.

5. (5). Selection: Calculate the fitness of the offspring population (including distribution cost, carbon emissions, and satisfaction), merge the parent population and the offspring population into a Pareto optimal solution set, and select the top n populations from these 2n Pareto solutions as the parent population for the next iteration.

6. (6). Check whether the number of iterations meets the preset maximum number of iterations limit. If satisfied, output the first solution on the Pareto frontier as the optimal solution; otherwise, return to Step 3.

The above algorithm steps are for the analysis of a single stop. The output optimal feasible solutions include the following three types: , , or . Merge the obtained optimal distribution route for the second-type customer points into the complete distribution route to obtain the final complete vehicle-assisted UAV distribution route.

4. Comparative analysis of numerical examples

4.1 Simulation analysis of small-scale instance

In the existing relevant studies, there is relatively little research on the vehicle-assisted UAV (Unmanned Aerial Vehicle) delivery route optimization problem considering no-fly zones, and it is quite difficult to obtain actual data. To verify the applicability and effectiveness of the model proposed in this paper under real-world conditions, a partial area of Harbin City, Heilongjiang Province, China was selected as the delivery area. The distribution center is Harbin International Container Central Station, with coordinates of (34.9, 40.2). Meanwhile, there are 30 customer points in different sub-areas. The desensitized coordinates, demand quantities, and time windows of these customer points are shown in Table 4 below.

[Figure omitted. See PDF.]

Meanwhile, the delivery area was divided into 56 standard sub-areas, each with a size of 10 km × 10 km. Each sub-area is marked with 0 or 1, where 0 represents an open area and 1 represents a no-fly zone, as shown in Fig 12 below:

[Figure omitted. See PDF.]

The specific distribution of the distribution center and customer points is shown in Figure 13 below:

[Figure omitted. See PDF.]

A comparison between Figs 12 and 13 shows that Customer Points 4, 6, 27, and 30 are located within no-fly zones, while the remaining customer points are in open areas. Additionally, the relevant parameters in this paper are set as follows: the take-off/landing speed and time of the UAV is ; ; the departure time from the distribution center is set to 6:00. For all customers, the earliest acceptable delivery time is 2 hours earlier than the required time window, and the latest acceptable delivery time is 2 hours later than the required time window.

The algorithm was programmed using Matlab R2016b and run on a computer with a processor of 11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz and 16.0 GB of memory.

4.1.1 Phase 1: Analysis of clustering results.

The clustering diagram is shown in the figure below. Given the current coordinate information of customer points and the distribution center, and considering the collaborative delivery of customers by vehicle-assisted UAVs, the IKM algorithm is used to cluster 30 customer points into 4 cluster centers under the premise that the distance from all customer points to their corresponding vehicle parking points does not exceed. The location of each cluster center and its affiliated customer points are shown in Fig 14 below:

[Figure omitted. See PDF.]

As can be seen from the Table 5, the IKM algorithm yields 4 cluster centers (A, B, C, D). The clustering coordinates (i.e., the locations of vehicle parking points) are (16.2, 22.6), (50.5, 48.3), (49, 19.4), and (21.4, 53.5) respectively. Cluster Center A covers customer points {1, 2, 3, 4, 6, 13, 14}, among which customer points {4, 6} are located in no-fly zones; Cluster Center B covers customer points {19, 21, 22, 24, 29, 30}, among which customer point {30} is located in a no-fly zone; Cluster Center C covers customer points {5, 7, 8, 9, 10, 11, 12, 17, 20, 23}; Cluster Center D covers customer points {15, 16, 18, 25, 26, 27, 28}, among which customer point {27} is located in a no-fly zone.

[Figure omitted. See PDF.]

4.1.2 Phase 2: UAV delivery route planning.

In this phase, delivery routes are planned sequentially for the customers affiliated with the four vehicle parking points (A, B, C, D). The genetic algorithm is used to solve for the UAV delivery routes, as shown in the Fig 15 (the red routes represent UAV delivery routes):At Vehicle Parking Point A: The UAV delivery routes are {A-13–14-A, A-3–1-A, A-2-A}; At Vehicle Parking Point B: The UAV delivery routes are {B-29–24-B, B-21–19-B, B-22-B}; At Vehicle Parking Point C: The UAV delivery routes are {C-23-12-10-C, C-7-8-11-C, C-5–9-C, C-17–20-C};At Vehicle Parking Point D: The UAV delivery routes are {D-15-25-26-D, D-16–18-D, D-28-D}.

[Figure omitted. See PDF.]

4.1.3 Phase 3: Initial vehicle delivery routes.

In this phase, the Variable Neighborhood Search (VNS) algorithm is used to plan the initial vehicle delivery routes. The planning objects include the distribution center and the four vehicle parking points. Two factors—maximum vehicle load capacity and endurance—are considered to comprehensively plan the number of delivery vehicles and their delivery routes. As shown in the Fig 16 below:The initial delivery route of Delivery Vehicle 1 is {0-D-B-0} (Note: “0” represents the distribution center).The initial delivery route of Delivery Vehicle 2 is {0-A-C-0}.

[Figure omitted. See PDF.]

4.1.4 Phase 4: Final vehicle delivery routes.

Based on the initial vehicle delivery routes obtained in Phase 3, it is considered that customer points in no-fly zones must be delivered by vehicles. Therefore, customers not included in the route planning of Phase 2 are assigned to vehicles for delivery. The ant colony algorithm is used to solve for the final routes of the vehicle-assisted UAV delivery system, as shown in the Fig 17 below:The final delivery route of Vehicle 1 is {0-D-27-B-30–0}.The final delivery route of Vehicle 2 is {0-A-6–4-C-0}.The optimized parts between the initial and final vehicle delivery routes are indicated by the black dashed lines in the Fig 17.

[Figure omitted. See PDF.]

4.1.5 Analysis of vehicle-assisted UAV delivery route planning results for small-scale instances.

To summarize, the algorithm-solved routes of each phase are shown in Table 6 below.

[Figure omitted. See PDF.]

Complete Delivery Route of Vehicle 1 Starting from the distribution center, Vehicle 1 first arrives at Vehicle Parking Point D. Here, 3 on-board UAVs are deployed to deliver to customer points {15, 16, 18, 25, 26, 28} in open areas. After the last UAV completes its delivery and returns to Vehicle 1, Vehicle 1 travels to customer point 27 (in a no-fly zone) for delivery. It then proceeds to Vehicle Parking Point B, where 3 on-board UAVs deliver to customer points {19, 21, 22, 24, 29} in open areas. Once the last UAV returns to Vehicle 1, Vehicle 1 travels to customer point 30 (in a no-fly zone) for delivery, and finally returns to the distribution center.

Complete Delivery Route of Vehicle 2 Starting from the distribution center, Vehicle 2 first arrives at Vehicle Parking Point A. Here, 3 on-board UAVs are deployed to deliver to customer points {1, 2, 3, 13, 14} in open areas. After the last UAV completes its delivery and returns to Vehicle 2, Vehicle 2 sequentially travels to customer points {6, 4} (both in no-fly zones) for delivery. It then proceeds to Vehicle Parking Point C, where 4 on-board UAVs deliver to customer points {5, 7, 8, 9, 10, 11, 12, 17, 20, 23} in open areas. Once the last UAV returns to Vehicle 2, Vehicle 2 returns to the distribution center.

The total final delivery cost is 2293.8, consisting of the following components:

Total vehicle delivery cost: 1582.6; Total UAV delivery cost: 580.35; Time penalty cost: 130.88; The average customer satisfaction is 0.9121. Details are shown in Table 7 below.

[Figure omitted. See PDF.]

4.2 Analysis of randomly generated no-fly zones

No-fly zones are a critical factor influencing the solution results of the vehicle-assisted UAV delivery model. In this section, 10 no-fly zones are randomly generated (with all other parameters unchanged) to compare with the solution results of the benchmark zone in Table 7 above. This comparison aims to verify the stability of the model under the condition of randomly generated no-fly zones.

The data in Table 8 above are obtained from 10 runs under the two scenarios. To verify the impact of randomly generated no-fly zones on the optimization objective of vehicle-assisted UAV delivery route planning, this paper adopts the t-test significance difference method based on the MATLAB platform to test the data in Tables 5–8. Since the population mean and variance are unknown, the Shapiro-Wilk normality test is first used to examine the normal distribution characteristics of each sample dataset in the table. The following hypotheses are proposed:

[Figure omitted. See PDF.]

1. : The sample data follows a normal distribution.

2. : The sample data does not follow a normal distribution.

The confidence level is set to [specify the confidence level if available]. When , , the hypothesis is accepted; when, , the hypothesis is rejected. As can be seen from the test results in Table 9, each group of sample data follows a normal distribution, allowing the t-test to be used for significance testing.

[Figure omitted. See PDF.]

After verifying that the sample data conforms to the characteristics of a normal distribution, the t-test is conducted on the two groups of sample data. First, the following hypotheses are proposed for each group of data:

1. : The algorithm in this paper has no impact on the solution under different problem instances.

2. : The algorithm in this paper has an impact on the solution under different problem instances.

The confidence level is set to 0.05. When and , it indicates that the null hypothesis is not valid; otherwise, the hypothesis is accepted. By conducting the t-test on six pairs of sample data, the test results are shown in Table 10 below.

[Figure omitted. See PDF.]

As can be seen from Table 10, the t-test is used to analyze the stability of the vehicle-assisted UAV delivery route planning model designed in this paper.Under the condition of randomly generating no-fly zones, the solution stability of the algorithm proposed in this paper is not affected, and the H₀ hypothesis holds.

4.3 Comparison of delivery routes under different scenarios

To demonstrate the differences in delivery routes and objective results under different scenarios, this paper compares three scenarios: traditional UAV-only delivery (Scenario 1), vehicle-only delivery (Scenario 2), and the proposed vehicle-assisted UAV delivery (Scenario 3). All parameters remain unchanged, and the algorithm is used to solve for the routes in Scenario 1 and Scenario 2. The route for UAV-only delivery (Scenario 1) is shown in the Fig 18 below:

[Figure omitted. See PDF.]

In Fig 18 above, since no vehicles are involved in delivery, UAVs depart from the distribution center (denoted as “center”), deliver to customer points within their service range, and then return to the center. However, due to the limited maximum flight distance of UAVs, they can only deliver to customer points within their maximum endurance radius. As shown in the figure, a total of 4 UAVs are deployed, with the following delivery routes:{center, 21, 28, center}、{center, 18, 16, center}、{center, 14, 17, center}、{center, 9, 20, 19, center}. Customer Point 6 is within the delivery range but located in a no-fly zone, so no UAV is assigned to deliver to it.

Meanwhile, the vehicle delivery route map for vehicle-only delivery (Scenario 2) is shown in Fig 19 below. For vehicle delivery, there is no restriction on delivery radius—only a limit on the maximum driving distance of vehicles—and no need to consider no-fly zones. Therefore, in the final planned vehicle delivery routes, all customer points are covered. A total of 5 vehicles are used for delivery in Scenario 2, with the following routes:{center, 17, 4, 5, 8, 10, 7, 9, center}、{center, 15, 13, 3, 1, 2, 6, 14, center}、{center, 16, 18, 25, 26, 27, 28, 21, center}、{29, 30, 24, 22, 23, center}、{center, 19, 20, 12, 11, center}.

[Figure omitted. See PDF.]

The delivery route results of the three scenarios are summarized and compared in Table 11 below:

[Figure omitted. See PDF.]

As can be seen from Table 11:In Scenario 1 (UAV-only delivery), due to the limitations of UAV flight distance and load capacity, multiple UAVs are required for delivery. Moreover, UAVs cannot reach customers beyond their maximum endurance radius, resulting in many customers being unserved—this is not in line with practical needs.In Scenario 2 (vehicle-only delivery), higher delivery costs and carbon emissions are incurred, and customer satisfaction is relatively low.In Scenario 3 (vehicle-assisted UAV delivery), the collaborative delivery of customers by vehicles and UAVs achieves the following outcomes (as indicated by objectives such as cost, carbon emissions, and customer satisfaction): it not only ensures that all customers are served but also reduces costs, promotes low-carbon operations, and improves customer satisfaction.

4.4 Simulation analysis of large-scale instances

4.4.1 Analysis of simulation results.

In practical scenarios, enterprises typically need to serve a large number of customer points with complex characteristics. Therefore, the simulation results based on small-scale data are insufficient to demonstrate that the model and algorithm can operate stably under more complex conditions. In this subsection, the R201 dataset from the Solomon benchmark—characterized by densely clustered customer points—is selected, and the multi-stage algorithm proposed in this paper is applied to solve the route optimization problem for vehicle-assisted UAV delivery.Vehicle and UAV parameters remain unchanged. The delivery area is still divided into 10 km × 10 km rectangular sub-areas and abstracted into a 2D plane, where 0 represents an open area and 1 represents a no-fly zone. The division map of the delivery area is shown in Fig 20 below:

[Figure omitted. See PDF.]

The algorithm program was run 10 times, and the optimal vehicle-assisted UAV delivery scheme (based on solution results) was selected.

The delivery routes are shown in the Fig 21. First, analyzing the locations of all customer points: Customer Points {2, 10, 11, 15, 24, 29, 32, 57, 63, 90} are located in no-fly zones, while the rest are in open areas. There are 8 cluster centers (i.e., vehicle parking points) with the following coordinates:A: (52.27, 13.64)、B: (11, 63.33)、C: (52.14, 39.21)、D: (55.82, 61.73)、E: (29.20, 19.87)、F: (32.64, 58.09)、G: (15.45, 42.45)、H: (14.28, 21.28). In Fig 21, Red solid lines represent UAV delivery routes.Black lines represent vehicle delivery routes, where solid black lines indicate vehicles traveling to parking points, and dashed black lines indicate vehicles traveling to customer points in no-fly zones for delivery.

[Figure omitted. See PDF.]

The specific delivery plans for all vehicles are shown in Table 12 below. Here:Customer points in [] are delivered by UAVs. Customer points in {} are delivered by vehicles.The order from left to right in the table indicates the vehicle’s delivery sequence. For example: Vehicle 2 departs from the distribution center (denoted as “0”), first arrives at Parking Point B. UAVs are then deployed to deliver to [64, 49], [19, 36], and [47]. Next, Vehicle 2 delivers to customer point {11} (in a no-fly zone), then proceeds to Parking Point F. UAVs at F deliver to [30, 70], [1, 69], and [31, 88, 62]. After that, Vehicle 2 sequentially delivers to customer points {32, 90, 63, 10} (all in no-fly zones) and finally returns to the distribution center.

[Figure omitted. See PDF.]

The total final delivery cost is 7276.03, consisting of the following components:Total vehicle delivery cost: 6009.67, Total UAV delivery cost: 964.8, Time penalty cost: 301.56, The average customer satisfaction is 0.9037, with details shown in Table 13 below:

[Figure omitted. See PDF.]

4.4.2 Analysis of UAV load capacity.

In the sensitivity analysis of the large-scale instance simulation, this subsection focuses on how the UAV load capacity constraint affects the optimization results of the proposed model and algorithm. To test the impact of UAV load capacity on vehicle-UAV collaborative delivery, was set to 30, 35, 40, 45, and 50 for testing. The vehicle-assisted UAV delivery model was run 10 times, and the optimal solution was selected. The results are shown in Table 14 below:

[Figure omitted. See PDF.]

As observed from Table 14, UAV load capacity directly affects total UAV flight distance and customer satisfaction. Specifically:A smaller maximum UAV load capacity means UAVs can serve fewer customers per trip, requiring more UAV deployments at vehicle parking points. For example:When : The total UAV flight distance is 583.4 km, the UAV delivery cost is 875.1, the total cost is 6884.77, and the average customer satisfaction is 0.8981. However, A larger maximum UAV load capacity allows UAVs to carry more weight and serve more customers per trip, reducing total UAV flight distance, but average customer satisfaction decreases.

4.4.3 Analysis of UAV endurance range.

The UAV endurance range is another key constraint limiting delivery operations. Keeping other parameters unchanged, was set to 30, 35, 40, 45, and 50 to study their impact on vehicle-assisted UAV delivery routes. The experimental results are shown in Table 15. As observed from Table 15, changes in maximum UAV endurance directly affect total UAV flight distance, total vehicle travel distance, total delivery cost, carbon emissions, and average customer satisfaction. This is because UAV endurance directly determines the clustering radius in the first stage of the algorithm: a larger endurance allows a larger clustering radius (resulting in fewer cluster centers) and vice versa, which further impacts the optimization results of subsequent algorithm stages. Specific observations:A smaller maximum UAV endurance leads to a shorter clustering radius and a shorter single-trip flight distance for UAVs, meaning fewer customers can be served per UAV trip and more UAV deployments are required.

[Figure omitted. See PDF.]

For example:When : The number of cluster centers (vehicle parking points) is 11, the total UAV flight distance is 793.9 km, the total delivery cost is 9479.22, the time penalty cost is 356.17, and the average customer satisfaction is 0.8823. A larger maximum UAV endurance allows longer single-trip flight distances and more customers served per trip, reducing the number of cluster centers and the total uav flight distance. For example:When : The number of cluster centers is 4, the total UAV flight distance is 563.1 km, the total delivery cost is 5551.66, and the average customer satisfaction for all customers is 0.9132.The above analysis of maximum UAV load capacity and maximum flight distance shows that both factors have a certain impact on delivery costs. This implies that when enterprises consider adopting vehicle-assisted UAV delivery, they should select UAV models based on actual operational needs.

4.4.4 Analysis of vehicle load capacity.

The maximum vehicle load capacity refers to the maximum cargo weight a vehicle can transport in a single trip. A smaller means more vehicles are required to serve the same number of customers. In the context of this paper, this translates to: in the third stage of the algorithm (vehicle route planning), if the maximum vehicle load capacity is small, vehicles may be unable to continuously serve multiple parking points. Therefore, a sensitivity analysis was conducted on vehicle load capacity, and the results are shown in Table 16 below,As observed from Table 16:A smaller maximum vehicle load capacity means vehicles can serve fewer customers per trip, requiring more vehicles to be deployed.

[Figure omitted. See PDF.]

For example:When : The number of deployed vehicles is 8, the vehicle delivery cost is 7497.4, the total cost is 8641.41, and the average customer satisfaction is 0.9122. A larger maximum vehicle load capacity allows vehicles to travel longer distances and serve more customers per trip, reducing the number of deployed vehicles; When , The number of deployed vehicles is 4, and the vehicle delivery cost is 4787.2. However, average customer satisfaction decreases to 0.8681.Additionally, as the maximum vehicle load capacity increases, vehicle carbon emissions gradually decrease. This is because although individual vehicle travel distances increase, the number of deployed vehicles is significantly reduced—lowering the total vehicle travel distance, reducing fuel consumption, and thus decreasing carbon emissions. The reason for the decrease in average customer satisfaction (despite increased vehicle capacity) is that the increased number of customers served per vehicle trip may delay delivery times for some customers, leading to lower satisfaction.

5. Conclusions and outlook

This study focuses on the optimization of vehicle-assisted UAV delivery paths under the constraints of no-fly zones and draws the following core conclusions: No-fly zones are practical constraints that must be given prioritized consideration in the route planning of vehicle-assisted UAV delivery. The planning model constructed based on these constraints enables differentiated delivery of customer points — with customer points in no-fly zones delivered by vehicles and those in open areas delivered by UAVs assisted by vehicles. This approach ultimately ensures full coverage of delivery for all customer points, significantly reduces the operational input costs of logistics enterprises, and effectively improves the overall average customer satisfaction.

The multi-stage heuristic solution algorithm designed in this study exhibits excellent performance. By decomposing the problem in stages (customer clustering, UAV path optimization, initial vehicle path planning, and final vehicle path optimization), the algorithm significantly reduces computational complexity. It not only shortens the solution time but also achieves better objective results (such as lower total cost and carbon emissions). Even when dealing with large-scale instances like the R201 dataset from Solomon, the algorithm can still efficiently obtain the optimal delivery plan.

Through the comparison of three delivery scenarios, it is found that UAV-only delivery fails to cover some customer points due to limitations in endurance, load capacity, and no-fly zones; while vehicle-only delivery can achieve full customer coverage, it incurs higher delivery costs and results in lower customer satisfaction. In contrast, the vehicle-assisted UAV collaborative delivery model can effectively balance these three aspects, achieving the dual goals of reducing delivery costs and improving customer satisfaction while ensuring delivery to all customer points.

Furthermore, the core parameters of equipment have a significant impact on delivery path planning and optimization results. For UAVs: in terms of load capacity, a larger load capacity allows more customer points to be delivered in a single trip, which may shorten the total flight distance but may lead to a slight decline in customer satisfaction; in terms of endurance, longer endurance reduces the number of customer cluster centers (vehicle parking points) and the number of vehicles required, thereby decreasing the total vehicle travel distance and carbon emissions while improving customer satisfaction. For vehicles: in terms of load capacity, a larger load capacity enables more delivery demands to be carried in a single trip, reducing the number of vehicles to be dispatched and lowering vehicle delivery costs and carbon emissions. However, the increased number of customer points delivered in a single trip may cause delays in delivery time for some customers, leading to a slight decline in customer satisfaction.

This paper has made certain progress and achievements in studying the optimization problem of the joint delivery route of vehicles and UAVs considering the constraints of no – fly zones. In the future, more in – depth research can be carried out from the following aspects:

First, this paper only considers one distribution center, but there may be multiple distribution centers in actual application scenarios. The design of the vehicle – assisted UAV delivery route planning for multiple distribution centers needs further in – depth research.

Second, this paper only considers one type of delivery vehicle and one type of UAV. In future research, scenarios of multi – type vehicle and multi – type UAV joint delivery need to be added and studied in depth.

Third, this paper assumes that the speeds of vehicles and UAVs remain constant during the entire delivery process. However, the real road network situation is complex and changeable, and the speeds of vehicles and UAVs are greatly affected by traffic conditions. The optimization problem of the joint delivery route of vehicles and UAVs with dynamic driving and flying speeds remains to be further studied.

Fourth, the designed four-stage heuristic algorithm (clustering → UAV path → initial vehicle path → final vehicle path) reduces the solution difficulty by decomposing complex problems. However, this strict sequential execution strategy may lead to the issue of “local optimality”. Future researchers are encouraged to explore whether information feedback or iterative mechanisms can be introduced between stages to investigate the possibility of improving solution quality.

Fifth, when calculating UAV paths, this paper explicitly adopts the Manhattan distance and “does not discuss how to find obstacle avoidance paths, but only focuses on the distance calculation of such paths”. Nevertheless, in complex no-fly zone environments, the length of actual detour paths may be much longer than the Manhattan distance, which will directly affect the accuracy of cost, time, and energy consumption calculations. Future scholars are expected to propose more accurate obstacle avoidance and pathfinding algorithms (such as the A* algorithm) to improve the UAV detour route model in this paper.

Supporting information

S1 Data.

https://doi.org/10.1371/journal.pone.0335614.s001

(XLSX)

References

1. 1. Dorling K, Heinrichs J, Messier GG, Magierowski S. Vehicle routing problems for drone delivery. IEEE Trans Syst Man Cybern, Syst. 2017;47(1):70–85.

* View Article

* Google Scholar

2. 2. Chiang W-C, Li Y, Shang J, Urban TL. Impact of drone delivery on sustainability and cost: realizing the UAV potential through vehicle routing optimization. Appl Energy. 2019;242:1164–75.

* View Article

* Google Scholar

3. 3. Dukkanci O, Campbell JF, Kara BY. Facility location decisions for drone delivery with riding: a literature review. Comput Opera Res. 2024;167:106672.

* View Article

* Google Scholar

4. 4. Madani B, Ndiaye M. Hybrid truck-drone delivery systems: a systematic literature review. IEEE Access. 2022;10:92854–78.

* View Article

* Google Scholar

5. 5. El-Adle AM, Ghoniem A, Haouari M. Parcel delivery by vehicle and drone. JORS. 2019;72(2):398–416.

* View Article

* Google Scholar

6. 6. Murray CC, Chu AG. The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery. Transp Res Part C: Emerg Technol. 2015;54:86–109.

* View Article

* Google Scholar

7. 7. Pugliese LDP, Guerriero F, Macrina G. Using drones for parcels delivery process. Procedia Manuf. 2020;42:488–97.

* View Article

* Google Scholar

8. 8. Yoo HD, Chankov SM. Drone-delivery using autonomous mobility: an innovative approach to future last-mile delivery problems. 2018 IEEE International Conference on Industrial Engineering and Engineering Management; 2018. p. 1216–20.

* View Article

* Google Scholar

9. 9. Zhang S, Liu S, Xu W, Wang W. A novel multi-objective optimization model for the vehicle routing problem with drone delivery and dynamic flight endurance. Comput Ind Eng. 2022;173:108679.

* View Article

* Google Scholar

10. 10. Park J, Kim S, Suh K. A Comparative analysis of the environmental benefits of drone-based delivery services in urban and rural areas. Sustainability. 2018;10(3):888.

* View Article

* Google Scholar

11. 11. Zhang R, Dou L, Xin B, Chen C, Deng F, Chen J. A review on the truck and drone cooperative delivery problem. Un Sys. 2023;12(05):823–47.

* View Article

* Google Scholar

12. 12. Goodchild A, Toy J. Delivery by drone: an evaluation of unmanned aerial vehicle technology in reducing CO 2 emissions in the delivery service industry. Transp Res Part D: Trans Environ. 2018;61:58–67.

* View Article

* Google Scholar

13. 13. Baldisseri A, Siragusa C, Seghezzi A, Mangiaracina R, Tumino A. Truck-based drone delivery system: an economic and environmental assessment. Transp Res Part D: Trans Environ. 2022;107:103296.

* View Article

* Google Scholar

14. 14. Kirschstein T. Comparison of energy demands of drone-based and ground-based parcel delivery services. Transp Res Part D: Trans Environ. 2020;78:102209.

* View Article

* Google Scholar

15. 15. Weng X, She W, Fan H, Zhang J, Yun L. Multi-depot vehicle routing problem with drones in emergency logistics. Cluster Comput. 2024;28(1):64.

* View Article

* Google Scholar

16. 16. Huang S-H, Huang Y-H, Blazquez CA, Chen C-Y. Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm. Adv Eng Inform. 2022;51:101536.

* View Article

* Google Scholar

17. 17. Marinelli M, Caggiani L, Ottomanelli M, Dell’Orco M. En route truck–drone parcel delivery for optimal vehicle routing strategies. IET Intell Trans Sys. 2018;12(4):253–61.

* View Article

* Google Scholar

18. 18. Eskandaripour H, Boldsaikhan E. Last-mile drone delivery: past, present, and future. Drones. 2023;7(2):77.

* View Article

* Google Scholar

19. 19. Benarbia T, Kyamakya K. A literature review of drone-based package delivery logistics systems and their implementation feasibility. Sustainability. 2021;14(1):360.

* View Article

* Google Scholar

20. 20. Chang YS, Lee HJ. Optimal delivery routing with wider drone-delivery areas along a shorter truck-route. Expert Syst Appl. 2018;104:307–17.

* View Article

* Google Scholar

21. 21. Liu Y-Q, Han J, Zhang Y, Li Y, Jiang T. Multivisit drone-vehicle routing problem with simultaneous pickup and delivery considering no-fly zones. Discrete Dyn Nat Soci. 2023;2023:1–21.

* View Article

* Google Scholar

22. 22. Wang Z, Sheu J-B. Vehicle routing problem with drones. Transp Res Part B: Methodol. 2019;122:350–64.

* View Article

* Google Scholar

23. 23. Huang H, Savkin AV. Deployment of charging stations for drone delivery assisted by public transportation vehicles. IEEE Trans Intell Transport Syst. 2022;23(9):15043–54.

* View Article

* Google Scholar

24. 24. Chen C, Chen X, Hang P. Personalized longitudinal motion planning based on a combination of reinforcement learning and imitation learning. GEIT. 2025:100321.

* View Article

* Google Scholar

25. 25. Chen W, Peng J, Ma Y, He H, Ren T, Wang C. Eco-driving framework for hybrid electric vehicles in multi-lane scenarios by using deep reinforcement learning methods. GEIT. 2025:100309.

* View Article

* Google Scholar

26. 26. Yoo W, Yu E, Jung J. Drone delivery: factors affecting the public’s attitude and intention to adopt. Telemat Inform. 2018;35(6):1687–700.

* View Article

* Google Scholar

27. 27. Crişan GC, Nechita E. On a cooperative truck-and-drone delivery system. Procedia Comput Sci. 2019;159:38–47.

* View Article

* Google Scholar

28. 28. Boysen N, Briskorn D, Fedtke S, Schwerdfeger S. Drone delivery from trucks: drone scheduling for given truck routes. Networks. 2018;72(4):506–27.

* View Article

* Google Scholar

29. 29. Li X, Tupayachi J, Sharmin A, Martinez Ferguson M. Drone-aided delivery methods, challenge, and the future: a methodological review. Drones. 2023;7(3):191.

* View Article

* Google Scholar

30. 30. Chen J, Fan T, Pan F. Urban delivery of fresh products with total deterioration value. IJPR. 2020;59(7):2218–28.

* View Article

* Google Scholar

Citation: Mao Y, Jia G (2025) Research on the optimization of delivery routes for vehicles with drones under no-fly zone restrictions. PLoS One 20(10): e0335614. https://doi.org/10.1371/journal.pone.0335614

About the Authors:

Yingbo Mao

Roles: Data curation, Formal analysis

E-mail: [email protected]

Affiliation: School of management, Harbin University of Commerce, Harbin, China

ORICD: https://orcid.org/0009-0004-4234-5696

Guiqiong Jia

Roles: Conceptualization

Affiliation: School of management, Harbin University of Commerce, Harbin, China

References

1. Dorling K, Heinrichs J, Messier GG, Magierowski S. Vehicle routing problems for drone delivery. IEEE Trans Syst Man Cybern, Syst. 2017;47(1):70–85.

2. Chiang W-C, Li Y, Shang J, Urban TL. Impact of drone delivery on sustainability and cost: realizing the UAV potential through vehicle routing optimization. Appl Energy. 2019;242:1164–75.

3. Dukkanci O, Campbell JF, Kara BY. Facility location decisions for drone delivery with riding: a literature review. Comput Opera Res. 2024;167:106672.

4. Madani B, Ndiaye M. Hybrid truck-drone delivery systems: a systematic literature review. IEEE Access. 2022;10:92854–78.

5. El-Adle AM, Ghoniem A, Haouari M. Parcel delivery by vehicle and drone. JORS. 2019;72(2):398–416.

6. Murray CC, Chu AG. The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery. Transp Res Part C: Emerg Technol. 2015;54:86–109.

7. Pugliese LDP, Guerriero F, Macrina G. Using drones for parcels delivery process. Procedia Manuf. 2020;42:488–97.

8. Yoo HD, Chankov SM. Drone-delivery using autonomous mobility: an innovative approach to future last-mile delivery problems. 2018 IEEE International Conference on Industrial Engineering and Engineering Management; 2018. p. 1216–20.

9. Zhang S, Liu S, Xu W, Wang W. A novel multi-objective optimization model for the vehicle routing problem with drone delivery and dynamic flight endurance. Comput Ind Eng. 2022;173:108679.

10. Park J, Kim S, Suh K. A Comparative analysis of the environmental benefits of drone-based delivery services in urban and rural areas. Sustainability. 2018;10(3):888.

11. Zhang R, Dou L, Xin B, Chen C, Deng F, Chen J. A review on the truck and drone cooperative delivery problem. Un Sys. 2023;12(05):823–47.

12. Goodchild A, Toy J. Delivery by drone: an evaluation of unmanned aerial vehicle technology in reducing CO 2 emissions in the delivery service industry. Transp Res Part D: Trans Environ. 2018;61:58–67.

13. Baldisseri A, Siragusa C, Seghezzi A, Mangiaracina R, Tumino A. Truck-based drone delivery system: an economic and environmental assessment. Transp Res Part D: Trans Environ. 2022;107:103296.

14. Kirschstein T. Comparison of energy demands of drone-based and ground-based parcel delivery services. Transp Res Part D: Trans Environ. 2020;78:102209.

15. Weng X, She W, Fan H, Zhang J, Yun L. Multi-depot vehicle routing problem with drones in emergency logistics. Cluster Comput. 2024;28(1):64.

16. Huang S-H, Huang Y-H, Blazquez CA, Chen C-Y. Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm. Adv Eng Inform. 2022;51:101536.

17. Marinelli M, Caggiani L, Ottomanelli M, Dell’Orco M. En route truck–drone parcel delivery for optimal vehicle routing strategies. IET Intell Trans Sys. 2018;12(4):253–61.

18. Eskandaripour H, Boldsaikhan E. Last-mile drone delivery: past, present, and future. Drones. 2023;7(2):77.

19. Benarbia T, Kyamakya K. A literature review of drone-based package delivery logistics systems and their implementation feasibility. Sustainability. 2021;14(1):360.

20. Chang YS, Lee HJ. Optimal delivery routing with wider drone-delivery areas along a shorter truck-route. Expert Syst Appl. 2018;104:307–17.

21. Liu Y-Q, Han J, Zhang Y, Li Y, Jiang T. Multivisit drone-vehicle routing problem with simultaneous pickup and delivery considering no-fly zones. Discrete Dyn Nat Soci. 2023;2023:1–21.

22. Wang Z, Sheu J-B. Vehicle routing problem with drones. Transp Res Part B: Methodol. 2019;122:350–64.

23. Huang H, Savkin AV. Deployment of charging stations for drone delivery assisted by public transportation vehicles. IEEE Trans Intell Transport Syst. 2022;23(9):15043–54.

24. Chen C, Chen X, Hang P. Personalized longitudinal motion planning based on a combination of reinforcement learning and imitation learning. GEIT. 2025:100321.

25. Chen W, Peng J, Ma Y, He H, Ren T, Wang C. Eco-driving framework for hybrid electric vehicles in multi-lane scenarios by using deep reinforcement learning methods. GEIT. 2025:100309.

26. Yoo W, Yu E, Jung J. Drone delivery: factors affecting the public’s attitude and intention to adopt. Telemat Inform. 2018;35(6):1687–700.

27. Crişan GC, Nechita E. On a cooperative truck-and-drone delivery system. Procedia Comput Sci. 2019;159:38–47.

28. Boysen N, Briskorn D, Fedtke S, Schwerdfeger S. Drone delivery from trucks: drone scheduling for given truck routes. Networks. 2018;72(4):506–27.

29. Li X, Tupayachi J, Sharmin A, Martinez Ferguson M. Drone-aided delivery methods, challenge, and the future: a methodological review. Drones. 2023;7(3):191.

30. Chen J, Fan T, Pan F. Urban delivery of fresh products with total deterioration value. IJPR. 2020;59(7):2218–28.