A Two-Stage Greedy Genetic Algorithm for Simultaneous Delivery and Monitoring Tasks with Time Windows

Abstract

With advancements in drone driving technology, drones can now collaborate with trucks to execute tasks. However, existing drone–truck collaborative systems are limited to single-task objectives and lack efficiency in large-scale multi-task scenarios. Enhancing the efficiency of drone–truck cooperative systems necessitates the coordination of drone and truck paths to execute multiple tasks simultaneously. Addressing time conflicts in such scenarios remains a significant challenge. This study proposes an innovative drone–truck collaborative system enabling the concurrent execution of delivery and monitoring tasks within specified time windows. To minimize travel costs, a two-stage greedy genetic algorithm (TGGA) is introduced. The methodology initially separates tasks, processes them in batches, and subsequently recombines them to determine the final route. The simulation results indicate that TGGA outperforms existing heuristic algorithms.

1. Introduction

The rapid expansion of e-commerce has driven the widespread adoption of drones for delivery services, leveraging their superior mobility, flexible deployment, and cost-effectiveness [1,2,3]. Research indicates that drones possess the capability to undertake more complex tasks beyond delivery, such as environmental monitoring and data collection [4]. Although previous studies have applied drones to simultaneously perform delivery and monitoring tasks, such as the design and implementation of a quadcopter-based drone system in [5], they overlook a problem: collecting ground information, such as traffic flow data, often requires adherence to specific time constraints. This means that the data must be gathered within a predetermined time frame, fully occupying the drone’s operational period.

In practical scenarios, drones may not always be able to reach monitoring points within designated time frames due to factors such as ongoing tasks or insufficient battery power. While ground-based monitoring stations are not always a viable solution [6,7], trucks can serve as an alternative means of collecting the required information from these points. Moreover, trucks can function as mobile docking stations for drones, enabling them to recharge, replace their batteries, and replenish their supplies. In return, drones can aid trucks with delivery tasks and contribute to reduced travel costs [8]. A critical challenge for drone–truck systems lies in optimizing route planning to ensure both vehicles complete their tasks, particularly time-sensitive ones, while minimizing travel expenses.

Existing research has explored how a truck and a drone efficiently perform single or multiple tasks. Regarding performing a single task, Chen and Chen [9] introduced a drone monitoring path planning algorithm rooted in the concept of skyline queries, significantly enhancing efficiency for large-scale environmental monitoring. Wu et al. [10] investigated a collaborative system employing drones and ground vehicles for continuous urban monitoring, prioritizing task continuity and cost-effectiveness during execution. Stodola and Kutěj [11] explored path planning problems for a truck and multiple drones, enabling drones to transport multiple packages while accounting for the influence of package weight on energy consumption. Yang et al. [12] analyzed the robust drone–truck delivery problem (RDTDP) and proposed an exact branch-and-price (B&P) solution to address uncertainties in ground traffic networks, which could potentially compromise service delivery and expose drones to hazards. Das et al. [13] proposed a collaborative Pareto ant colony optimization (Collaborative P-ACO) algorithm to optimize synchronized drone–truck delivery routes. This algorithm aims to minimize transportation costs and maximize customer satisfaction while adhering to strict time window constraints. Regarding performing multiple tasks, Zhou and Yang [14] designed the Optimization-dependent Multi-Task Assignment Model (PSO-MTAM) to address issues of incomplete and delayed task execution when drones perform multiple tasks, ensuring the timely completion of tasks. Wang and Zhang [15] proposed a wolf-pack-method-based task allocation algorithm for UAV swarm (WTA-UAV) to achieve large-scale and real-time task execution, addressing dynamic task execution issues in complex scenarios with drone swarms. Meanwhile, Wang et al. [16], when solving the multi-task execution problem of drones, considered constraints such as specific time windows, different equipment, and designated execution orders, developing improved multi-objective quantum-behaved particle swarm optimization (IMOQPSO) to overcome these constraints.

Table 1. Comparison of relevant references.

References	D	T	NT	Solution
[9]	1	1	=1	Branch and Bound Skyline
[10]	1	1	=1	Estimation of Distribution
[11]	n	n	=1	Adaptive Ant Colony Optimization
[12]	1	1	=1	B&P
[13]	n	n	=1	Collaborative P-ACO
[14]	n	0	⩾1	PSO-MTAM
[15]	n	0	⩾1	WTA-UAV
[16]	n	0	⩾1	IMOQPSO
[17]	n	m	=1	Adaptive Large Neighbourhood Search
[18]	1	1	=1	Variable Neighborhood Search
This paper	1	1	⩾1	TGGA

D: the number of drones. T: the number of trucks. NT: the number of task types.

summarizes the literature related to our tasks, focusing on single-task and multi-task scenarios. The authors of [9,10,11,12,13,17,18] mainly concentrate on single-task scenarios, optimizing the routes of the drone and truck to improve task execution efficiency. Notably, refs. [17,18] made enhancements in single-task settings, allowing the drone to address similar tasks, such as simple pickup and delivery. Compared to single-task execution, performing multiple tasks better leverages the potential of the drone in practical applications and enhances system operational efficiency, as it requires consideration of various task characteristics, such as task value and urgency. The authors of [14,15,16] address how drones can execute multiple tasks simultaneously; however, their focus is primarily on task allocation among multiple drones performing different tasks, with limited discussion on how to optimize the routes for these tasks post-allocation, especially for a single drone executing these tasks. Optimizing the path of a single drone during multi-task execution is crucial, as it undoubtedly saves drone resources, especially when cooperating with the truck, significantly improving the system’s operational efficiency. While [9,10,11,12,13,17,18] focus on route planning of the drone and truck, they typically employ a uniform planning approach for all tasks, which may not be well suited for multi-task scenarios. Therefore, this study extends the existing single-task drone–truck routing optimization system by introducing multi-task functionality to improve the operational efficiency of the drone and truck when performing multiple tasks, specifically applied to the delivery and monitoring task scenarios proposed in [5].

To the best of our knowledge, this research presents the first drone–truck collaborative system capable of simultaneously executing delivery and monitoring tasks. The primary objective of this system is to optimize task sequencing and route planning to ensure timely task completion while minimizing overall travel costs. Specifically, since monitoring tasks will persist for a certain period, the drone and truck must arrive before the monitoring tasks begin and leave after they conclude, while delivery tasks can be executed at any time. Therefore, when multiple monitoring tasks have conflicting time constraints, both the drone and truck must coordinate their routes to efficiently complete package deliveries. By clearly defining the specific objectives of the monitoring tasks and establishing reasonable monitoring times, this system can be effectively applied in real-world scenarios. For instance, it can be coordinated with traffic management authorities to facilitate the appropriate collection of road traffic data during peak hours throughout the delivery process. As the drone–truck path planning problem is NP-hard [19], we design a two-stage greedy genetic algorithm (TGGA) to determine the optimal travel route. In essence, TGGA decomposes the problem into smaller sub-problems, determines the optimal path for each sub-problem, and then combines these individual paths using a greedy approach to derive the overall optimal route. The experimental results demonstrate that TGGA surpasses existing heuristic algorithms by generating lower-cost routes within shorter computation times.

The remainder of this manuscript is structured as follows: Section 2 provides a detailed description of the drone–truck delivery and monitoring system, including its mathematical formulation. Section 3 presents the proposed path planning algorithm. Section 4 outlines a comparative analysis of the proposed algorithm with existing methods. Finally, Section 5 concludes the study with a summary of the key findings.

2. System Model

We consider a truck carrying a drone to complete $n+m$ monitoring and delivery tasks together, where n symbolizes as the number of monitoring tasks and m denotes the number of delivery tasks. The set of total tasks is defined as $V=\left\{V_1,V_2,\dots ,V_{n+m}\right\}$, and the set of monitoring tasks is represented as $M=\left\{M_1,M_2,\dots ,M_n\right\}$. The drone deployed by the truck can facilitate task efficiency. Post-departure from the depot, the drone can autonomously undertake surveillance missions. While the drone is engaged, the truck can concurrently execute proximate deliveries or alternative surveillance operations. The drone’s capabilities are beyond surveillance, encompassing the transportation of goods from the truck to designated delivery locations. The drone sortie is limited to a single payload. Both the drone and the truck are obligated to return to the depot upon task completion. A comprehensive visualization of the truck–drone collaborative model is presented in Figure 1.

In Figure 1, (a) shows the drone and truck departing from the depot simultaneously. Due to the urgency of monitoring task 1, it is executed by the drone, while the truck performs delivery task 2 concurrently. In (b), since monitoring task 1 ends at 1:00, and monitoring task 3 starts precisely at 1:00, the drone cannot immediately proceed to monitoring task 3 after completing monitoring task 1. Therefore, the truck takes over monitoring task 3. In (c), when the truck executes the monitoring task, it cannot simultaneously perform delivery services. As a result, delivery task 4 is executed by the drone. However, since the drone does not carry the goods required for delivery task 4 when leaving monitoring task 1, it must first travel to truck task execution point 3 to load the goods before continuing with the delivery. In (d), the drone and truck return to the depot immediately after completing their tasks.

The objective of this model is to minimize the combined travel cost of the drone and truck, mathematically expressed as

$${\displaystyle min{\displaystyle \sum _{i=1}^{n+m}}{\displaystyle \sum _{j=1,j\ne i}^{n+m}}(U_{i,j}\alpha +K_{i,j}\beta )d_{i,j}}$$

(1)

where $U_{i,j}\in \left\{1,0\right\}$ and $K_{i,j}\in \left\{1,0\right\}$ denote that the drone and truck, respectively, are in transit from point i to point j. If $U_{i,j}$ or $K_{i,j}$ equals 1, the drone or the truck is in motion; if they equal 0, they are stationary. $d_{i,j}$ represents the distance between point i and point j. $\alpha$ denotes the unit distance cost for the drone, and $\beta$ for the truck.

As depicted in Figure 1, each monitoring task is associated with a specific temporal constraint, representing the time window within which the task must be executed. To fulfill a monitoring task, the responsible vehicle (drone or truck) must arrive at the monitoring point prior to the tasks commencement and depart only upon its completion. Constraints  (2) and  (3) formalize this requirement:

$${\displaystyle {\displaystyle \sum _{j=1,j\ne i}^{n+m}}(U_{j,i}+K_{j,i})(T_i^l-T_i^{in})⩾0,\forall i\in M}$$

(2)

$${\displaystyle {\displaystyle \sum _{j=1,j\ne i}^{n+m}}(U_{i,j}+K_{i,j})(T_i^{out}-T_i^r)⩾0,\forall i\in M}$$

(3)

where $T_i^l$ and $T_i^r$ denote the start and end times of the $ith$ monitoring task, respectively. $T_i^{in}$ and $T_i^{out}$ indicate the times when the drone or the truck begins or completes the $ith$ monitoring task, respectively.

To enhance model realism, we account for the drone’s energy consumption, setting the energy consumption per unit of flight and hovering time as the constant $P_1$ and $P_2$. Consequently, the drone must adhere to the following energy consumption constraints throughout the task:

$$e_i-U_{i,j}{\displaystyle \frac{d_{i,j}}{V_u}}{P}_1⩾0,\forall i,j\in V$$

(4)

$$e_i-(T_i^r-T_i^l)U_{j,i}{P}_2⩾0,\forall i\in M,\forall j\in V$$

(5)

where $e_i$ represents the remaining energy of the drone at point i, and $V_u$ signifies a constant indicating the drone’s speed. Constraint  (4) requires the drone’s remaining energy during flight to be greater than zero. Constraint  (5) guarantees the drone has sufficient energy while hovering to complete the monitoring task.

3. Two-Stage Greedy Genetic Algorithm

Given the NP-hard nature of the drone–truck path planning problem, this section introduces a hybrid heuristic method known as TGGA. TGGA partitions tasks and addresses identical tasks within the same stage, thereby reducing the computational complexity and algorithm runtime. Additionally, TGGA solves entire tasks at the end of the second stage, ensuring an optimal combination of routes across different tasks.

3.1. Route Setting

We present the path representation of TGGA, as shown in Figure 2. Utilizing both a drone and a truck, we employ a two-dimensional array to depict the travel path. The first row of the array specifies the tasks to be performed by each mode of transportation. The second row indicates the mode of service with “−1”, “0”, and “1” (“0” for tasks performed by the drone, “1” for tasks performed by the truck carrying the drone, and “−1” for tasks performed by the truck alone). For the special depot point, we stipulate that the first row uses “0” and the second row uses “1” to represent it.

3.2. Stage One: Monitoring Task Path Planning

During this phase, TGGA plans the path for monitoring tasks to ensure timely execution. The entire process for stage one is detailed in Algorithm 1.

Algorithm 1 Monitoring Task Path Planning

Input:  M = $\left\{M_1,M_2,\dots \right\}$, $T_l$ = $\left\{T_1^l,T_2^l,\dots \right\}$, $T_r$ = $\left\{T_1^r,T_2^r,\dots \right\}$, $N_{max}$ represents the maximum number of routes, $I_{max}$ the maximum number of iterations, $\alpha$ the unit path cost of the drone, and $\beta$ the unit path cost of the truck.   1: # Greedy initialization   2: Monitoring tasks path set $S\leftarrow ⌀$   3: $M\leftarrow$ Sort by $T_l$ from small to large   4: for $i=1$ to $N_{max}$ do   5:       Temporary path $P=M$   6:       $P\leftarrow$ Randomly assign the drone or the truck to each point in P   7:       if P satisfies the constraint of $T_r$ then   8:           Add P to S   9:           $i=i+1$ 10:       end if 11: end for 12: # Optimization of execution method 13: for $i=1$ to $I_{max}$ do 14:       for $j=1$ to $N_{max}$ do 15:           Randomly select path P from S 16:           r = Random number $0\sim 1$ 17:           if r < 0.5 then 18:               $P\leftarrow$ Change the execution method for up to two points 19:           else 20:               $P\leftarrow$ Find task points that meet the needs of drone 21:           end if 22:           if P satisfies the constraint of $T_r$ then 23:               Add P to S 24:           end if 25:       end for 26:       $S\leftarrow$ Calculate the cost by the total path of the drone $\times \alpha +$ the total path of the truck $\times \beta$ 27:       S = The $N_{max}$ lowest-cost paths in set S 28: end for Output:  The lowest cost monitoring path

3.2.1. Greedy Initialization

A high-quality initial solution minimizes unnecessary later searches, ensures the timely execution of monitoring tasks, and reduces the solution time. Given that the time window constraints of existing drone–truck systems allow the drone or truck to arrive before the window closes and leave immediately after, monitoring tasks differ in this regard. For monitoring tasks, the drone or truck must arrive before the time window opens and leave only after it closes. Prioritizing monitoring points near the drone or truck may result in other monitoring points being left unexecuted. Moreover, all monitoring tasks have fixed durations. Considering these factors, we sequentially perform the most pressing monitoring task at the current time to ensure the proper execution of all monitoring tasks. Specifically, we first sort the monitoring tasks based on the left-side time window ($T_l$) (Line 3). Then, for each task point on the route, we randomly assign an execution mode (Line 5–6). If the assigned route satisfies the conditions of the right-side time window ($T_r$) (Line 7), the path is added to the initial route set (Line 8). Otherwise, we repeat the assignment step until the specified quantity is reached.

3.2.2. Optimization of Execution Method

Upon acquiring a high-quality initial solution, we systematically alter the execution method of the tasks on the path to enhance route optimization. In particular, we switch task points between the truck and the drone to enhance efficiency. Specifically, we change the “1” or “−1” in the second row of the array to “0”, or change “0” to “1” or “−1”, with a maximum of two points being modified each time (Line 18). As shown in Figure 3, we change the execution methods between task 1 and task 4. After the change, task 1 is carried out by the drone, so the corresponding position in the second row is marked as “0”. Meanwhile, task 4 is completed by the truck, so the corresponding position in the second row changes from “0” to “1”. However, since the truck is not carrying the drone at this moment, the corresponding position in the second row changes from “1” to “−1”. Alternatively, tasks currently performed by the truck but meeting the conditions for drone execution will be reassigned to the drone (Line 20), as depicted in Figure 4. The conditions for a task to be executed by the drone are as follows:

• The drone energy must be sufficient to complete the task and then land at the next task point on the truck route.
• The previous task point must not be executed by the drone.

If the revised route is not viable (Line 22), the change is discarded.

3.3. Stage Two: Delivery Task Path Planning

Throughout this phase, we plan the delivery path and then integrate the greedy strategy with the monitoring task path to achieve a comprehensive solution.

3.3.1. Random Initialization

To broaden the search scope and prevent TGGA from quickly converging on a local optimum, we randomly order all delivery tasks while adhering to energy consumption constraints and execute them sequentially based on the sorted order.

3.3.2. Selection

We employ the tournament mechanism to consistently select the most cost-effective route. Specifically, during each operation, we randomly select five routes from all available paths and then choose the route with the lowest cost. Only one route is selected per operation, meaning the process will be repeated up to the maximum population size.

3.3.3. Crossover

We propose two crossover strategies for planning the delivery path, selecting one at each crossover instance. The first strategy involves TGGA randomly selecting two routes. A segment is chosen from one route, and the duplicate points in the other route are removed. The remaining parts of the second route are then merged with the selected segment at the position of the last duplicate point. The entire process is illustrated in Figure 5. The second strategy involves TGGA randomly selecting a route and reversing a section of it.

3.3.4. Mutation

The mutation method mirrors the execution optimization method in stage one. If the altered route is not viable, the change is discarded.

3.3.5. Greedy Combination

After determining the delivery path, we implement a greedy strategy to integrate the monitoring and delivery paths. As illustrated in Figure 6, we insert the closest delivery task to the monitoring task. If the delivery task has not yet merged, all preceding delivery tasks in the sequence will be inserted before the monitoring task. In the event that this delivery task has already been integrated with other monitoring tasks, the subsequent nearest delivery task will be selected until all delivery points are fully incorporated. For delivery locations that cannot be incorporated before any monitoring task, we position them sequentially after the final monitoring task.

4. Numerical Analysis

We design comparative experiments involving Variable Neighborhood Search (VNS) [20], Iterated Local Search (ILS) [21], and Adaptive Large Neighborhood Search (ALNS) [22]. VNS and ILS are both time-sensitive algorithms that consider the order of task execution during their design phase. Specifically, VNS utilizes eight different neighborhood operators, while ILS employs five local search operators along with strategies for drone task allocation and landing, achieving efficient time planning. In contrast, ALNS represents the state-of-the-art algorithm for the Vehicle Routing Problem with Drones (VRPD) [20]. It optimizes the collaborative delivery paths for drones and trucks by repeatedly destroying and repairing the current solution, and it adaptively adjusts based on the effectiveness of different solving methods to effectively explore the solution space. Additionally, all these algorithms aim to reduce operational costs [20,21,22].

Due to the structural differences among the various algorithms, we make the following modifications to ensure a fair comparison of the three algorithms: (1) Initialization. Given the specific nature of the different tasks, the three algorithms do not have corresponding initialization operations. Therefore, we first standardize the process by using the initialization steps from stage one and stage two of this study. We then append the delivery tasks to the end of the monitoring tasks to complete the route. Finally, we optimize the complete route according to the optimization steps from their respective original literature, resulting in the initialized route. (2) Population Size. We introduce the concept of a population for all three algorithms and set it to be completely consistent with TGGA. This means that each route in the population is thoroughly searched before proceeding to the next search iteration. The core algorithms (such as destruction, repair, etc.) and the order of execution remain entirely consistent with the original literature. In addition, parameters such as the number of iterations and the time of the three algorithms are the same as those of TGGA. All algorithms operate under the same computational resources.

4.1. Test Instances

This research employs computer-generated random data across 16 instances ($Ins$). In the initial eight instances, 3 monitoring tasks (M) are paired with 5, 10, 15, 20, 25, 30, 35, and 40 delivery tasks (D). In the following eight instances, the number of monitoring tasks increases to eight, maintaining the same combinations of delivery tasks. Each monitoring task time T needs 30 min, randomly assigned within each hour, but does not overlap. In the initial eight instances, tasks span 5 h; in the latter eight, they extend to 10 h. All monitoring tasks, delivery tasks, and warehouses are randomly allocated within a rectangular area of 50 km × 50 km.

4.2. Parameter Settings

We derive the cost ratio of the drone and truck per unit distance as 0.1 [23], the drone’s speed ($V_u$) as 20 m/s, and the truck’s speed ($V_k$) as 15 m/s [24]. The drone’s maximum energy (e) is 10,000 units, and the constant energy consumption per second during high-speed continuous flight ($P_1$) is 4, while the constant energy consumption per second during hovering prohibition ($P_2$) is 0.2. According to Formulas (4) and (5), this allows for 40 min of continuous high-speed flight or hovering for about 13 h. Ensuring a fair comparison among the algorithms involves obtaining the optimal parameters for VNS, ILS, and ALNS based on references [20,21,22], respectively. For TGGA, the parameters are initially set by referring to [25]. However, the following adjustments are made to some sensitive parameters to achieve the optimal performance of TGGA: the probability of executing a crossover operation is 0.9, with each execution selecting one of two crossover strategies with a probability of 0.5. The probability of executing a mutation operation is 0.1, with one mutation strategy selected with equal likelihood each time. The maximum population size ($N_{max}$) for all algorithms is 100. All algorithms conclude after 100 generations ($I_{max}$), or a maximum of 3600 s.

4.3. Comparison with VNS, ILS, and ALNS

To ensure experimental accuracy, we conducted 20 comparisons for each instance at various task scales and averaged the results. We recorded the average best cost $X^{best}$, as well as its standard deviation $X_{std}^{best}$ for 20 runs of each algorithm, and the average convergence time $X^{time}$, in which X denotes one of TGGA, VNS, ILS, or ALNS. Moreover, we computed the cost savings of TGGA pertaining to VNS, ILS, and ALNS, represented as $X^{imp}$, according to [22], utilizing the subsequent formulas:

$$X^{imp}=1-{\displaystyle \frac{{TGGA}^{best}}{X^{best}}}$$

(6)

where ${\displaystyle \frac{{TGGA}^{best}}{X^{best}}}$ represents the cost ratio of TGGA compared to algorithm X (VNS, ILS, ALNS), while $1-{\displaystyle \frac{{TGGA}^{best}}{X^{best}}}$ represents the proportion of cost savings achieved by TGGA compared to algorithm X.

4.3.1. Optimal Value Analysis

Figure 7 illustrates the average optimal results from 20 runs across 16 instances, as well as the average cost savings ratio of TGGA compared to the three algorithms. It is clear that TGGA consistently achieves the lowest optimal cost among the three algorithms, regardless of the number of tasks executed. When the number of monitored tasks is fixed and the number of delivered tasks is relatively small, the optimal costs of the four algorithms show little difference. However, as the number of delivered tasks increases, the cost savings of TGGA compared to the three algorithms become significantly greater. When the number of delivered tasks exceeds 30, the cost savings of TGGA stabilize, remaining around 50% for VNS and around 40% for both ILS and ALNS. Additionally, we observe that an increase in monitored tasks raises system costs, as the drone and truck often need to prioritize completing monitoring tasks, temporarily neglecting nearby delivery tasks. This increases the travel distance for both the drone and truck. Nevertheless, TGGA maintains the lowest cost. These data indicate that TGGA’s two-stage greedy strategy is effective.

Table 2. Standard deviation of optimal value of TGGA vs. VNS, ILS, and ALNS.

$\mathit{Ins}$	M	D	${\mathit{TGGA}}_{\mathit{std}}^{\mathit{best}}$	${\mathit{VNS}}_{\mathit{std}}^{\mathit{best}}$	${\mathit{ILS}}_{\mathit{std}}^{\mathit{best}}$	${\mathit{ALNS}}_{\mathit{std}}^{\mathit{best}}$
1	3	5	16,378	18,585	17,350	19,518
2	3	10	18,045	21,566	19,004	16,084
3	3	15	15,725	29,520	20,108	25,121
4	3	20	14,869	27,835	23,567	23,899
5	3	25	25,060	36,605	18,507	24,960
6	3	30	35,554	32,580	31,985	18,337
7	3	35	24,116	32,315	56,197	23,644
8	3	40	23,696	53,525	45,792	29,117
9	8	5	13,695	16,286	17,219	17,297
10	8	10	21,633	36,063	26,242	23,638
11	8	15	21,746	27,647	15,015	12,466
12	8	20	24,974	22,030	29,908	25,761
13	8	25	27,919	27,702	28,606	31,367
14	8	30	27,836	32,291	29,934	28,371
15	8	35	36,446	30,874	36,977	28,632
16	8	40	37,881	36,260	42,316	34,002

shows the standard deviations of the optimal values for 16 instances. It is observed that TGGA has a standard deviation comparable to the three existing algorithms, and that the standard deviation increases with the number of tasks. However, in most instances, TGGA exhibits a lower standard deviation and remains relatively stable overall. This indicates that TGGA can maintain consistent performance even with random datasets.

4.3.2. Convergence Time Analysis

To further compare the performance of the four algorithms, we recorded the convergence times of each algorithm within 100 generations. If an algorithm exceeded 3600 s during the 100 generations, it returned the current optimal cost. The data in Figure 8 indicate that VNS has the shortest convergence time among the three algorithms, followed by TGGA, while the convergence times of ILS and ALNS are notably longer than those of VNS and TGGA. From a theoretical perspective, the time complexity of the most complex operator in VNS is $O\left((M+D)N_{max}{I}_{max}\right)$, while the time complexity of the greedy combination operation in TGGA is $O\left(MD{N}_{max}{I}_{max}\right)$. However, in the practical results illustrated in Figure 8, the convergence times for TGGA and VNS are quite similar. Although TGGA’s convergence time is longer than that of VNS, the analysis of optimal values shows that the extended convergence time of TGGA greatly reduces the optimization cost. In contrast, as the number of tasks increases, ILS and ALNS struggle to converge within the allotted time.

In summary, the proposed TGGA achieves significantly lower optimal costs than VNS does. It also surpasses ILS and ALNS in attaining lower optimal costs within a limited time frame. Thus, TGGA can achieve superior optimal costs with only a modest increase in computation time.

4.4. Time Window Sensitivity Analysis

To further investigate the differences in results between the three algorithms and TGGA under various scenarios, we conducted two experiments analyzing the effects of different durations of time windows and the distribution ranges of those time windows on all four algorithms. The selected numbers of monitoring tasks and delivery tasks were 3 and 20, respectively.

4.4.1. Time Window Duration

In this section, we set different durations (T) for the time windows, specifically, 0 min, 30 min, and 60 min. As shown in Figure 9, when the duration changes from 0 min to 30 min, VNS, ILS, and ALNS exhibit a slight increase, while TGGA remains stable. For the duration of 60 min, the costs of all four algorithms show little variation. This indicates that the duration has a minor effect on VNS, ILS, and ALNS, while it has almost no impact on TGGA.

4.4.2. Time Window Distribution

We define three different ranges for the time window distribution, allowing monitoring tasks to be randomly distributed within 3 h, 5 h, or 7 h. As illustrated in Figure 10, the bar chart represents the average optimal cost of the algorithms. It is evident that as the time window for monitoring tasks expands, the optimal costs of all four algorithms gradually decrease. This may be because, when the distribution of the monitoring task time windows is more dispersed, both the drone and the truck have more time to consider the geographical locations of the tasks, allowing them to prioritize the execution of closer task points. Although the reduction is small, this result indicates that the time window distribution range can affect the optimal values of TGGA, with a more significant cost-saving effect observed as the range increases.

5. Conclusions

This study explores a novel drone–truck collaborative system that concurrently performs monitoring and delivery tasks, optimizing sequences and paths to resolve time conflicts. As drone–truck path planning falls within the NP-hard problem category, we formulate the TGGA to simplify solution complexity and minimize travel costs. TGGA initially decouples tasks, sequentially planning optimal routes for each type. After identifying the lowest-cost paths, a greedy method couples all tasks to determine the final route. Our simulations indicate that TGGA efficiently combines and plans the lowest-cost paths for different tasks. TGGA produces a significantly lower-cost final path within in a limited time frame than existing algorithms.

Future work could explore several extensions of this research, for example, allowing multiple groups of trucks to depart simultaneously, with each group carrying only one drone. Alternatively, a group of trucks could depart from the warehouse with multiple drones on board to perform more delivery and monitoring tasks over larger areas. This would require the development of more efficient operators, including optimization strategies between different drones, as well as between drones and trucks. Overall, future research could focus on identifying more efficient operators or developing faster methods to effectively address these challenges.