In the information age of the 21st century, the booming e-commerce industry has greatly promoted the progress of the logistics sector. With consumers’ growing demand for fast and convenient delivery services, last-mile delivery has become a critical link in the logistics field. The rise of the low-altitude economy, which was highlighted as an important topic at the Third Plenary Session of the 20th Central Committee of the Communist Party of China, has drawn increasing attention to the timeliness and convenience of drone delivery. More and more researchers are focusing on drone path planning problems, covering various aspects. Initially, drones were primarily used in military applications. Later, they gradually found their way into civilian scenarios, such as agricultural field information acquisition, facility inspection, and logistics delivery, where they have become increasingly popular.
For single-drone scenarios, Liu et al. proposed a tangent-based path planning method to solve UAV path planning in complex environments. Liu Guangcai et al. considered three-dimensional urban scenes and UAV performance constraints, setting the objective function to minimize the total delivery cost and designing an improved A*-artificial potential field combined algorithm to solve the model. Huang Shuzhao et al. improved the selection, crossover, and mutation operators of the genetic algorithm to plan smooth and flyable paths for effective field information acquisition. Zhang Honghai et al. considered urban environmental factors and constructed a multi-constraint logistics UAV path planning model, solving it with the A* algorithm. Wang Fei et al. introduced Singer mapping to improve the particle swarm optimization algorithm for solving multi-constraint UAV path planning problems in urban logistics. Feng Wenjing et al. addressed delivery issues in remote rural areas from a green perspective, planning UAV delivery paths with the goal of minimizing energy consumption.
For multi-drone scenarios, multi-drone cooperative path planning refers to planning paths for multiple drones under collaborative constraints so that they can accomplish tasks with minimal cost. The similarity between multi-drone cooperative path planning and single-drone path planning lies in the need to plan feasible flight paths that satisfy constraints for each drone, while the difference is that the multi-drone scenario seeks the global optimum rather than the optimal path for a single drone. Yu Yanpeng et al. proposed an evolutionary multi-tasking algorithm for multi-drone cooperative path planning to address the low efficiency of urban emergency material distribution. Gong et al. proposed a multi-drone coverage method based on deterministic radio wave propagation for cooperative coverage search in urban areas. Xian Bin et al. proposed a method combining offline MPC global planning and online improved artificial potential field local planning to solve multi-drone path planning. DU et al. applied particle swarm optimization to plan paths for multiple drones.
The simultaneous pickup and delivery problem was first proposed by Min to solve the path planning for book distribution and collection. Subsequent research has mostly focused on vehicle routing problems. Li Yixu et al. studied the green vehicle routing problem with simultaneous pickup and delivery, aiming to minimize carbon emission cost and using a three-stage Lagrangian heuristic algorithm. Liu Jiansheng et al. added time windows to simultaneous pickup and delivery and proposed an adaptive brainstorming algorithm for vehicle routing. He Meiling et al. designed an improved ant colony algorithm to solve the vehicle routing problem with the objective of minimizing fixed vehicle costs, driver costs, fuel consumption, and carbon emission costs.
In summary, while simultaneous pickup and delivery and multi-drone cooperative path planning have yielded some research results, there is little research on multi-drone path planning considering simultaneous pickup and delivery specifically for rural areas. Applying multi-drone cooperation to the rural logistics delivery scenario can avoid road constraints and complete pickup and delivery services faster. Therefore, this paper constructs a model for the logistics drone path planning problem that considers simultaneous pickup and delivery, with the goal of minimizing both the fixed cost and variable cost of drones. An improved genetic algorithm is designed to solve the model.
1. Problem Description and Model Assumptions
The multi-drone path planning problem considering simultaneous pickup and delivery studied in this paper is illustrated in Figure 1 (omitted due to no picture reference). Assume there is one initial distribution center and multiple customer points in a certain rural area. Customers have different pickup and delivery demands. Simultaneous pickup and delivery means that during the delivery journey, if the drone is not fully loaded, it can perform pickup services. In the process of pickup and delivery, all customers are served by multi-rotor drones. The problem aims to construct a reasonable drone flight route that satisfies various constraints and minimizes total cost.
Assumptions:
- Goods are standardized items with quantifiable weight/volume; pickup and delivery demands are single.
- All drones are homogeneous.
- Each customer is served by only one drone, and the service covers the customer’s total demand.
- Each customer’s pickup quantity is less than the drone’s capacity.
- A drone’s single battery range (before swapping) can execute multiple pickup and delivery tasks; after completing tasks, it must return to the distribution center.
- Drones only swap lithium batteries at the distribution center, with a fixed swapping time.
- The rural area terrain is simplified as a flat plane; flight distance is calculated as the straight-line distance between nodes.
2. Model Establishment
Let \( W \) be the set of drones, \( W = \{1, 2, \dots, w\} \); let \( N \) be the set of customer points, \( N = \{1, 2, \dots, n\} \); let 0 denote the distribution center; let \( d_{ij} \) be the distance from node \( i \) to node \( j \); let \( D_k = \{0, 1, 2, \dots, n\} \) be the set of drone takeoff/landing points, where 0 is the distribution center and 1 to \( n \) are customer points; let \( Q_{\max} \) be the maximum payload of a drone; let \( D_{\max} \) be the maximum flight range; let \( f \) be the fixed cost per drone; let \( c \) be the cost per unit distance; let \( x_{ijw} \) be a binary variable equal to 1 if drone \( w \) flies from node \( i \) to node \( j \); let \( q_j \) be the delivery weight at customer \( j \); let \( p_j \) be the pickup weight at customer \( j \); let \( Z \) be total cost; let \( F \) be total fixed cost; let \( D \) be total variable cost.
The model for multi-drone cooperative path planning considering simultaneous pickup and delivery is:
$$ \min Z = F + D $$
$$ F = w \times f $$
$$ D = c \sum_{i,j \in D_k} \sum_{w \in W} x_{ijw} d_{ij} $$
Subject to:
$$ \sum_{w \in W} \sum_{i \in D_k, i \neq j} x_{ijw} = 1, \quad \forall j \in N $$
$$ \max\{p_j, q_j\} \leq Q_{\max}, \quad \forall j \in N $$
$$ \sum_{i,j \in D_k} p_j x_{ijw} \leq Q_{\max}, \quad \forall w \in W $$
$$ \sum_{i,j \in D_k} q_j x_{ijw} \leq Q_{\max}, \quad \forall w \in W $$
$$ d_{ij} \leq D_{\max}, \quad \forall i,j \in D_k $$
$$ \sum_{i \in D_k^0} \sum_{j \in D_k^1} d_{ij} x_{ijw} \leq D_{\max}, \quad \forall w \in W $$
$$ x_{ijw} \in \{0, 1\}, \quad \forall i,j \in D_k, \forall w \in W $$
$$ \sum_{i \in D_k} \sum_{j \in D_k} x_{ijW} \leq |V| – 1, \quad \forall w \in W $$
Equation (1) is the objective function minimizing total cost. Equation (2) represents the fixed cost of drones. Equation (3) represents the variable cost of drones. Equation (4) ensures each customer point \( j \) is served exactly once by one drone. Equation (5) ensures the pickup or delivery weight at any customer does not exceed the drone’s maximum payload. Equation (6) ensures that the total pickup weight on each drone’s route does not exceed the maximum payload. Equation (7) ensures that the total delivery weight on each drone’s route does not exceed the maximum payload. Equation (8) ensures that the distance between any takeoff/landing point and the next customer point is within the maximum range. Equation (9) ensures the total flight distance of each drone is within the maximum range. Equation (10) defines the decision variable. Equation (11) eliminates subtours.
3. Algorithm Design and Implementation
Genetic algorithm (GA) has good global search ability, a simple process, and is easy to extend, but it has slow search speed and is prone to local optima. Greedy algorithm takes the optimal choice at each step. In this paper, we design an improved genetic algorithm. First, we use the greedy algorithm to generate the initial population; then, we design crossover and mutation operations. The algorithm flowchart is shown in Figure 2 (omitted).
3.1 Encoding and Initialization
In GA, encoding transforms the solution space into genes suitable for evolutionary operations. We adopt integer encoding and use the greedy algorithm to generate the initial population. Each gene corresponds to a customer node, and distribution center numbers serve as separators to distinguish the service range of different drones. For example, the chromosome “0-4-2-15-0-6-5-17-0” indicates: drone 1 serves customers {4, 2, 15}, drone 2 serves customers {6, 5, 17}, where 0 is the distribution center. This encoding clearly reflects the constraint that each customer is served by exactly one drone and the task is complete, laying the foundation for subsequent crossover and mutation operations.
3.2 Fitness Function
The fitness function evaluates the quality of a chromosome. A higher fitness value means a better solution. Since our objective is minimization, the fitness function is inversely proportional to the objective function:
$$ \text{fit} = \frac{1}{Z} $$
where \( Z > 0 \).
3.3 Selection Operation
We use roulette wheel selection based on fitness values. Chromosomes with higher fitness have a higher probability of being selected to the next generation.
3.4 Crossover Operation
Crossover generates new individuals and increases population diversity. For the multi-drone path planning problem with simultaneous pickup and delivery, we design two crossover methods based on integer encoding.
1) Two-point crossover: Randomly select two crossover points in the parent chromosome and swap the customer sequence between the two parents to generate offspring. Since customer tasks may be duplicated or missing after swapping, we introduce a repair mechanism to remove duplicate customer nodes and add missing ones, ensuring each customer task is unique and complete. During repair, we also check the drone load and range constraints, adjusting the path allocation if necessary to ensure feasibility. The two-point crossover is illustrated in Figure 3 (omitted).
2) Gene swap crossover: We propose a simplified crossover method where a single gene (corresponding to a customer node) is swapped between two parent chromosomes, generating two offspring. Unlike traditional crossover, this method emphasizes the integrity of customer tasks — the customer’s pickup and delivery demands must always be handled by the same drone. After swapping, a consistency check is performed to avoid duplication or omission, along with a feasibility check on drone load and range. The gene swap crossover is illustrated in Figure 4 (omitted).
3.5 Mutation Operation
Mutation introduces new individuals to increase diversity and prevent premature convergence. We use a swap mutation: randomly select two genes within a chromosome and swap their positions. This method effectively changes the customer visit order. Under the simultaneous pickup and delivery constraint, each customer node must be served entirely by one drone. Therefore, during mutation, we swap complete customer nodes to ensure that the pickup and delivery demands are not split. After mutation, we check the new chromosome against load and range constraints; if the drone’s load exceeds \( Q_{\max} \) or the range exceeds \( D_{\max} \), we discard the mutation or adjust the path via repair.
4. Simulation and Analysis
4.1 Simulation Environment and Parameter Settings
To verify the effectiveness of the proposed drone path planning scheme considering simultaneous pickup and delivery, we conduct a simulation. Following the method in reference [19], we select several nodes that fit the problem description, including 20 customer points and 1 initial distribution center. Amazon’s survey shows that 90%–95% of packages weigh less than 2.27 kg. Combined with reference [20], we set the package weight at customer points in the range of 0.1–2 kg, randomly generated. The initial distribution center information is shown in Table 1, customer information in Table 2.
| Distribution Center ID | X | Y |
|---|---|---|
| 0 | 35 | 35 |
| Customer ID | X | Y | Delivery weight (kg) | Pickup weight (kg) |
|---|---|---|---|---|
| 1 | 41 | 49 | 1 | 0 |
| 2 | 35 | 17 | 2 | 0 |
| 3 | 55 | 45 | 2 | 0 |
| 4 | 40 | 30 | 0 | 2 |
| 5 | 15 | 30 | 2 | 0 |
| 6 | 25 | 30 | 1 | 0 |
| 7 | 20 | 50 | 1 | 0 |
| 8 | 10 | 43 | 2 | 0 |
| 9 | 55 | 60 | 2 | 0 |
| 10 | 30 | 60 | 0 | 2 |
| 11 | 20 | 65 | 1 | 0 |
| 12 | 50 | 35 | 2 | 0 |
| 13 | 30 | 25 | 1 | 0 |
| 14 | 15 | 10 | 2 | 0 |
| 15 | 30 | 5 | 1 | 0 |
| 16 | 10 | 20 | 0 | 2 |
| 17 | 5 | 30 | 2 | 0 |
| 18 | 20 | 40 | 2 | 0 |
| 19 | 15 | 60 | 1 | 0 |
| 20 | 45 | 65 | 2 | 0 |
We use the previously designed genetic algorithm to solve the model. The parameter settings for the simulation are: population size 1000, termination condition after 500 iterations. Model parameters are shown in Table 3. According to reference [20], the maximum payload of drones can reach 10–20 kg. Based on the real parameters of the SF Fangzhou 40 drone, we set the maximum payload to 10 kg and the maximum range to 18 km. Referring to reference [21], the fixed cost per drone is set to 50 CNY.
| Parameter | Value |
|---|---|
| Drone payload (kg) | 10 |
| Drone maximum range (km) | 18 |
| Drone fixed cost (CNY) | 50 |
4.2 Simulation Results Analysis
The experiment was conducted in an environment of AMD Ryzen 7 4800H with Radeon Graphics 2.90 GHz, 16.0 GB RAM, Windows 11 64-bit operating system, using Python 3.11. After completing pickup and delivery services, drones return to the nearest distribution center; the distance from the last customer point to the nearest distribution center is negligible. The initial drone routes obtained by the greedy algorithm are shown in Table 4.
| Drone ID | Drone route |
|---|---|
| W1 | 0-4-2-15-14 |
| W2 | 0-6-5-17-16 |
| W3 | 0-13-18-7-19 |
| W4 | 0-12-3-9-20 |
| W5 | 0-1-10-11-8 |
To verify the optimization ability of our algorithm, we compare the traditional genetic algorithm with our improved genetic algorithm. The results are shown in Table 5.
| Traditional GA (CNY) | Improved GA (CNY) | Gap |
|---|---|---|
| 1,248 | 1,016 | 232 |
From Table 5, we can see that the total cost is reduced from 1,248 CNY to 1,016 CNY after improving the genetic algorithm, a reduction of 18.5%. This demonstrates that our improved genetic algorithm effectively optimizes the multi-drone path planning problem considering simultaneous pickup and delivery in rural areas.
China drone technology has been rapidly developing, and the application of drones in logistics, especially in rural last-mile delivery, has become a significant trend. By incorporating simultaneous pickup and delivery into the multi-drone path planning model, this research provides a more practical solution for the rural logistics market in China, where both delivery and pickup services are frequently needed. The improved genetic algorithm shows good performance, and the approach can be further extended to larger-scale problems and real-world implementations.
5. Conclusion
This paper explores the multi-drone cooperative path optimization problem considering simultaneous pickup and delivery and proposes a two-stage algorithm. In the first stage, a greedy algorithm is used to generate an initial solution; in the second stage, an improved genetic algorithm is applied to optimize the initial solution. The method effectively solves the multi-drone cooperative path planning problem. Future research could delve into customer satisfaction, intelligent decision algorithms, multi-objective optimization, and multi-modal cooperative delivery to achieve more efficient and cost-effective logistics services.
As the low-altitude economy continues to expand in China, the demand for China drone logistics solutions will only grow. The model and algorithm proposed in this paper can serve as a foundation for developing practical China drone delivery systems that handle both pickup and delivery simultaneously, especially in rural areas where road infrastructure is limited. The results demonstrate that considering simultaneous pickup and delivery leads to more realistic and efficient path planning for logistics drones.