Introduction

The eruption of the COVID-19 epidemic has engendered significant public health security perils, representing a grave menace to human well-being and vitality, while also exerting a profound impact on economic and societal spheres [1, 2]. The virus has afflicted humanity through modes of respiratory droplet and contact transmission. To mitigate the proliferation of the virus, the Chinese government has actively carried out nucleic acid testing [3], which has also spawned research on optimizing the transport path of new coronavirus testing samples. Thus, the investigation into the conveyance path of these samples bears immense practical significance. The sample transfer process commonly entails healthcare personnel collecting samples at diverse testing sites, followed by the imperative dispatch of vehicles from the testing center to gather these samples. However, due to the variability in sample quantities, collection times, and frequencies, this results in an inefficacious utilization of vehicle cargo space and the proliferation of circuitous paths, thereby inflating transshipment costs. Certain testing sites may be inaccessible via vehicular means, necessitating manual transportation, which is not only time-intensive but also heightens the risk of infection. Furthermore, the extensive utilization of trucks has exacerbated the emission of greenhouse gases, consequently inflicting greater damage upon the predicaments of global warming and climate change. Drones have demonstrated merits across a spectrum of domains, encompassing the reduction of operational expenditures, acceleration of transportation velocity, facilitation of contactless delivery, and advocacy for the integration of renewable energy sources [4]. Additionally, owing to its reliance on battery power, the drone system operates with a complete absence of emissions, refraining from the discharge of detrimental gases, thereby contributing to the preservation of the climate and enhancement of air quality. Nevertheless, it is imperative to acknowledge the constraints inherent in their performance with regard to long-haul and large-scale cargo conveyance assignments. Consequently, we proffer an innovative resolution wherein a truck collaboratively transports nucleic acid samples in concert with multiple drones, each endowed with multi-visit capabilities. This approach not only furnishes robust reinforcement in the face of the exigencies presented by this global pandemic but also harmonizes seamlessly with the principles of sustainability and environmental preservation.

Some scholars have proposed research on using trucks and drones to collaborate on package delivery, which has gone through multiple evolutionary stages and variants so far. The Flying Sidekick Traveling Salesman Problem (FSTSP) originally proposed by Murray et al. [5] was the cornerstone of this problem. Subsequently, a profusion of offshoots materialized, among which were TSPD (Traveling Salesman Problem with Drone) [6], MFSTSP (Multiple Flying Sidekicks Traveling Salesman Problem) [7], TSP-mD (Traveling Salesman Problem with Multiple Drones) [8], VRPD (Vehicle Routing Problem with Drone) [9], to name but a few, each tailored to distinct delivery scenarios and endowed with different objective functions. Researchers have predominantly built to formulate mathematical models with delivery time [10] or delivery cost [11] as the centerpiece objective. They have proffered sundry algorithmics to tackle these quandaries, including the column generation algorithm [12], the genetic algorithm [13], the variable neighborhood search algorithm [14], and the hybrid algorithm [15], among others. Furthermore, certain studies have delved into mode of transport, such as truck-supported drone delivery [16], drone-facilitated truck delivery [17], independent truck and drone delivery [18], and hybridized delivery systems [19], to better Adapt to real-world delivery challenges. The above literature can provide methodological reference for this article, but it does not consider the impact of public health emergencies on collaborative delivery path planning of trucks and drones.

The investigation conducted by Barnawi et al. [20] centered on the utilization of drones during the COVID-19 epidemic and introduced a deep learning model for diagnosing cases. Regrettably, this study omitted the consideration of practical concerns, such as the performance, efficiency, and energy consumption of drones in real-world deliveries. Correspondingly, Yang et al. [21] proposed a truck-supported drone joint delivery model to address the distribution challenges posed by the novel coronavirus epidemic. However, in this delivery model, the truck’s cargo capacity remains underutilized, as the truck itself does not directly participate in the delivery service. In this context, Peng et al. [22] conducted research on collaborative delivery of trucks and drones, where trucks directly provide services to customers. They formulated a mixed integer programming model and employed a hybrid neighborhood search algorithm to resolve this conundrum. Wu et al.’s [23] research prioritized the minimization of delivery time and introduced a contactless package delivery conundrum entailing collaborative routing for both trucks and drones. The research by Liu et al. [24] focused on how to supply emergency supplies between high-risk and low-risk epidemic areas after the outbreak of infectious public health events, especially during the COVID-19 epidemic. In order to avoid the spread of the epidemic, they proposed the strategy of using “contactless” drone delivery in high-risk epidemic areas and truck delivery in low-risk epidemic areas. Ji et al. [25] proposed a material distribution method for closed communities based on the collaboration of drones and trucks, focusing on solving the problems of cross-infection and material efficiency. Li et al.’s [26] research centered on contactless medical supplies distribution while also addressing carbon emissions optimization. Finally, Li et al. [27] proposed a two-layer heuristic algorithm to tackle the collaborative delivery conundrum involving trucks and drones. The aforementioned literature serves as a valuable theoretical compass for material distribution within the context of the new coronavirus epidemic.

Although there have been studies focusing on collaborative delivery using trucks and drones, the existing literature has not yet delved into the specific delivery needs of nucleic acid samples. Firstly, this need is pressing as any delays may result in sample failure. Such failures can lead to substantial economic and human costs and even cause social panic. Secondly, this demand carries a high risk of infection and necessitates non-contact methods. Additionally, existing research often does not take into account the actual situation of drones visiting multiple nodes in a single trip and processing nodes whose demand is greater than the drone’s load capacity. With advancing technology, we will also investigate how multiple drones can be coordinated with trucks to enhance drone utilization. Simultaneously, we will prioritize two key goals: delivery time and distribution cost. In summary, this study aims to address the urgent delivery of nucleic acid samples. We establish a bi-objective programming model that takes into account the actual situation of a truck carrying multiple drones and the drones’ visits to multiple nodes within one trip. This model is designed to minimize delivery time and costs. To tackle this crucial problem, we have devised a genetic adaptive large-scale neighbor search algorithm (GALNS) to resolve this conundrum, offering valuable insights for decision-making in virus sample transport path planning during major outbreaks.

Literature Review

In this section, we furnish a concise exposition of antecedent research intimately associated with the present paper’s undertaking. Should readers desire an exhaustive and in-depth analysis, they are encouraged to peruse the studies authored by Macrina et al. [28] and Madani et al. [29]. According to the number of trucks and vehicle-mounted drones, we can divide the truck and drone collaborative delivery problems into three categories (Table 1): TSPD, TSP-mD and VRPD.

Murry et al. [5] introduced the concept of the FSTSP, which encompasses the collaborative delivery of a truck and a drone. In this context, they imposed a constraint wherein the drone could exclusively serve one customer per flight while optimizing for delivery time. To contend with the inherent NP-hard of this challenge, they formulated a mixed-integer programming model and devised a heuristic algorithm for resolution. Building upon this work, Agatz et al. [6] conceived an alternative model, denoted as TSPD, with the objective of cost-minimization in transportation. They also engineered a path-first clustering-second heuristic algorithm, effectively addressing this problem. Ha et al. [15] focused their attention on the TSPD model with the goal of minimizing operating costs, where operating costs include transportation costs and time costs caused by waiting. Tong et al. [30] harnessed a variable neighborhood search algorithm to tackle the TSPD challenge. It should be pointed out that in the above studies, the drone typically undergoes battery replacement after each flight to facilitate subsequent node services. However, Yurek et al. [31] proposed a different perspective, considering the TSPD problem under charging strategy.

Following this, Phan et al. [32] expanded the purview of the TSP-D problem to encompass real-world distribution scenarios, introducing the concept of a truck equipped with multiple drones for delivery, which they designated as the TSP-mD problem. Campbell et al. [33] employed continuous approximation modeling techniques to assess a collaborative delivery system involving both trucks and multiple drones. The research findings underscored the economic advantages inherent in TSP-mD. Seifried et al. [34] developed an exact algorithm for resolving this problem and substantiated the NP-hard of TSP-mD. Murray et al. [7] further studied the MFSTSP, correlating the energy consumption model of the drone with the package weight, speed and operation time. It is worth noting that in the above study, the drone could only visit one customer at a time. Subsequently, Gonzalez-R et al. [35] proposed an extension of the TSP-D problem model, permitting drones to serve multiple customers in a single flight. Luo et al. [8] addressed the multi-drone multivisit traveling salesman problem and harnessed a multi-start tabu search methodology to tackle the challenge, involving up to a hundred customers. Lastly, Mara et al. [36] devised a heuristic algorithm grounded in Adaptive Large-scale Neighborhood Search (ALNS) techniques for the resolution of this problem.

Wang et al. [9] embarked on an expansive exploration of collaborative delivery challenges both trucks and drones, transcending the confines of a single vehicle to encompass multiple vehicles, thereby birthing the VRPD problem. Their research illuminated that, even when each vehicle carries just one drone, and the drones share identical speed and distance matrices with the trucks, this collaborative delivery paradigm can slash completion time in half. Subsequently, some scholars conducted research on exact methods [37, 38] and heuristic algorithms [39, 40] to solve this problem. Some scholars have studied the collaborative delivery problem of trucks and drones in different contexts [23, 26]. In addition, some literature studies the extension of the collaborative delivery problem of trucks and drones by adding constraints. Meng et al. [41] extended the VRPD to a logistics system that incorporates dual requisites: pickup and delivery. They intricately modeled parameters such as drone travel distance and package carrying weight, conceptualizing them as pivotal facets of drone energy consumption models. Subsequently, they formulated a mixed integer programming model, replete with problem-specific inequalities. In addition, they proffered a novel two-stage heuristic algorithm to proficiently tackle this conundrum. Kuo et al. [42] directed their research towards the minimization of travel expenses, focusing on the expansion of the VRPD, this time accounting for temporal constraints in the form of time windows. They ingeniously devised a variable neighborhood search algorithm as a means to resolve this intricate challenge. Jeong et al. [43] studied the impact of package weight on drone flight duration and considered the situation where drone flights are prohibited in some delivery areas during certain periods. Furthermore, Liu et al. [11] innovatively incorporated the concepts of no-fly zones and pickup and delivery tasks into the VRPD framework. Their solution strategy was grounded in a two-stage heuristic algorithm, anchored in the principles of simulated annealing, offering a resolution to this multifaceted problem.

Table 1.

Categorization of cooperative delivery challenges amidst trucks and drones.

TSPDTSP-mDVRPD
Number of trucks nn = 1n = 1m>1
Number of vehicle-mounted drones mm = 1m>1m3 1

The preceding literature delves into the examination of collaborative truck and drone delivery from various perspectives and problem scenarios. While these investigations have advanced our understanding, there remains ample space for further exploration. Despite the proposal of theoretical frameworks within these studies, they must still account for the intricacies of real-world delivery operations. Moreover, it is imperative to acknowledge that this predicament is formally established as NP-Hard, necessitating additional research to devise more efficient algorithms, particularly in addressing expansive-scale challenges.

Problem Description

Given a delivery network G = ( , )V A , V ={0,1,2,..., ,n n +1} represents the node set, node 0, n + represents the inspection center, 1 C ={1,2,..., }n represents the detection node set; A represents the arc set, A = {( , ) |i j i ∈V j, ∈V i, ≠ j} . U ={1,2,..., }u represents the collection of drones, and P ={1,2,..., }p represents the collection of drone trips. The location of each detection node is known, along with the sample collection requirements, which are determined based on the number of samples that need to be collected. When orchestrating the conveyance of these samples, the formidable challenge at hand lies in the judicious planning of synergistic transport paths for both trucks and multiple drones, each endowed with multi-visit capabilities. This endeavor is aimed at augmenting sampling efficiency, mitigating the peril of contagion, and curtailing transportation costs. This study christens this intricate quandary as the Multi-Visit Multiple Flight Assistant Traveling Salesman Problem (MV-MFSTSP).

The workflow is as follows: a fleet, comprising a truck and a cohort of multi-visit drones, commences its journey from the inspection center denoted as ‘0’, methodically collecting samples at diverse detection nodes. It is imperative that each detection node receives service either from a truck or a drone, and upon the culmination of all tasks, the fleet is obliged to return to the inspection center. To facilitate management, the truck is bound to the drone it carries, i.e. they move together (Fig. 1). The drone is afforded the flexibility to launch and land either at the detection node or the inspection center. Following the completion of the sample collection task at each detection point, the drone must fulfill two prerequisites before proceeding to the subsequent detection point: its remaining cargo capacity must meet or exceed the sample collection volume requisite for the next point, and its remaining flight distance must meet or exceed the remaining flight distance for the ensuing detection point. If the drone fails to meet these criteria, it shall return to the nearest accessible truck parking location to await landing. Meanwhile, while the drone executes its mission aloft, the truck continues its preordained path, ensuring the uninterrupted delivery of sample packages. Furthermore, to forestall cross-contamination, it is imperative that samples undergo requisite disinfection both before collection and after delivery.

Fig. 1.

Model drawings of trucks and drones.

https://www.pjoes.com/f/fulltexts/175025/PolJEnvironStud-2024-33-3-2663-2677_Fig_1_min.jpg

The assumptions of the MV-MFSTSP problem are as follows:

The drone traverses nearly linear trajectories, prompting its adherence to the Euclidean distance metric; while the truck needs to travel along the road network, the truck distance is defined as dij = ηdij, η is a constant that represents the curvature of the road.

Both the truck and the drone always keep moving at a constant speed, and the drone is faster than the truck.

The impact of the drone’s flight speed and load capacity on the cruising range is not considered.

In the event that either the truck or the drone arrives ahead of schedule, they must await the other’s arrival before recommencing the delivery process.

No consideration is given to the time required for battery replacement when their energy levels are depleted.

Fig. 2.

A possible solution for MV-MFSTSP.

https://www.pjoes.com/f/fulltexts/175025/PolJEnvironStud-2024-33-3-2663-2677_Fig_2_min.jpg

The truck possesses the capacity to transport all available drones in a single haul, and the quantity is contingent upon the volume of samples gathered at the detection node.

In this paper, MV-MFSTSP is assumed to be explored in two-dimensional (2D) space.

Fig. 2 illustrates a plausible path for a truck transporting multiple multi-visit drones collaboratively engaged in sample transportation. Further symbols and explanations pertinent to the mathematical model can be found in Table 2.

Before establishing a mathematical model, first divide the detection nodes as follows:

Nku: detection nodes in this set are served by trucks, Nk={i|qi>Q||dij>Dmax/2,∀i,j∈C};

Nk: detection nodes in this set can be served by both drones and trucks, Nku = C – Nk.

Mathematical Model

Table 2.

Model symbols and explanations.

TypeSymbolExplanation
ParametereSample validity period.
MA very large positive integer.
RMaximum number of drones that can be carried on a truck.
DmaxThe maximum flight distance of the drone. Because the drone serves at least one detection node each time it flies, the distance to the farthest detection node that the drone can visit is Dmax/2.
C1, C2Truck/drone cost per unit transportation distance.
SiService time of detection node i∈C.
qiSample weight of detection node i∈C, qi = lic, li represents the number of samples at detection node i, c is the weight of a single sample.
QMaximum load capacity of drone.
V1, V2 The speed of truck/drone transportation.
dij', dijTransportation distance of truck/drone from node i∈V to node j∈V.
tij', tijuTransportation time of truck/drone from node i∈V to node j∈V.
Variablexij(=1)0-1 variable, which indicates that the truck travels from node i∈V to node j∈V.
yijup(=1)0-1 variable, which indicates that the u-th ((u∈U) drone’s p-th (p∈P) trip along arc (i,j)∈A.
hiupS(=1)0-1 variable, which indicates that node i∈V is the launch node of the p-th (p∈P) trip of the u-th (u∈U) drone, and S is the abbreviation of “Start”.
hiupE(=1)0-1 variable, which indicates that node i∈V is the landing node of thep-th (p∈P) trip of the u-th (u∈U) drone, and E is the abbreviation of “End”.
Ziup(=1)0-1 variable, which indicates that node i∈V is served by the p-th (p∈P) trip of the u-th ((u∈U) drone.
Zi(=1)0-1 variable, which indicates that node i∈V is served by a truck.
ti'Continuous variable, which represents the time when the truck arrives at node i∈V.
tiupContinuous variable, which represents the time when the p-th (p∈P) trip of the u-th (u∈U) drone reaches node i∈V.
giContinuous variable, which represents the truck access order of node i∈V.
kiContinuous variable, which represents the drone access order of node i∈V.
riContinuous variable, which represents the number of drones that are not on the truck when departing from node i∈V.
tiContinuous variable, which represents the actual time of arrival at node i∈V.

[i] ti

(1)
minf1=C1∑i∈V∑j∈Vdij′xij+C2∑u∈U∑p∈P∑i∈V∑j∈Vdijyijup
(2)
minf2=max{tn+1}

S.T.

(3)
∑u∈U∑p∈PZiup+Zi=1,∀i∈Nku
(4)
Zi=1,∀i∈Nk
(5)
∑j∈Vyijup≥Ziup,∀i∈V,p∈P,u∈U
(6)
Zi=∑j∈Vxji,∀i∈V
(7)
hiupE+∑j∈Vyijup=hiupS+∑j∈Vyjiup,∀i∈V,p∈P,u∈U
(8)
∑j∈Vyijup≤1,∀i∈V,p∈P,u∈U
(9)
∑j∈Vyjiup≤1,∀i∈V,p∈P,u∈U
(10)
∑j∈Vxij=∑j∈Vxji≤1,∀i∈V
(11)
∑u∈U∑p∈Pyijup+∑u∈U∑p∈Pyjiup≤1,∀(i,j)∈A
(12)
Ziup+Zjup≥1−M(1−yijup),∀(i,j)∈A,p∈P,u∈U
(13)
hiupS≥1−M(2−yijup−Zjup+Ziup),∀(i,j)∈A,p∈P,u∈U
(14)
hjupE≥1−M(2−yijup−Ziup+Zjup),∀(i,j)∈A,p∈P,u∈U
(15)
∑u∈U∑p∈PhiupS≤M∑j∈Vxji,∀i∈V
(16)
∑u∈U∑p∈PhiupE≤M∑j∈Vxij,∀i∈V
(17)
hiupS+hiupE≤1,∀i∈V,p∈P,u∈U
(18)
∑i∈VhiupS=∑i∈VhiupE≤1,∀p∈P,u∈U
(19)
gi−gj≥1−M(1−xij),∀i∈C,j∈V,i≠j
(20)
ki−kj≥1−M(1−yijup),∀i∈C,j∈V,i≠j,p∈P,u∈U
(21)
ti=max{tiu_max,ti′},∀i∈V,u_max∈U,p∈P
(22)
tiu_max=max{∑p∈Pti1,pZi1,p,∑p∈Pti2,pZi2,p,...,∑p∈Ptiu,pZiu,p},∀i∈V,u_max∈U,u∈U,p∈P
(23)
tiu,p≥ti−1+ti−1,i+Si−1−M(1−yi−1,iup),∀i∈V,p∈P,u∈U
(24)
ti′≥ti−1+ti−1,i′+Si−1−M(1−xi−1,i),∀i∈V
(25)
tij=dij/V2,∀(i,j)∈A
(26)
tij′=dij′/V1,∀(i,j)∈A
(27)
∑p∈P∑u∈U∑j∈Cy0jup+r0=R
(28)
∑p∈P∑u∈U∑l∈Vyilup+ri≥∑p∈P∑u∈U∑h∈Vyjhup+rj−M(1−xij),∀i∈C,j∈C,i≠j
(29)
∑p∈P∑u∈U∑l∈Vyjlup+rj≥R−M(1−xj,(n+1)),∀j∈C
(30)
∑i∈NkuqiZiup≤Q,∀p∈P,u∈U
(31)
∑i∈V∑j∈Vdijyijup≤Dmax,∀p∈P,u∈U
(32)
xij,yijup,Zi,Ziup,hjupE,hjupS∈{0,1},∀i∈V,j∈V,i≠j,p∈P,u∈U
(33)
1≤gi≤n+2,1≤ki≤n+2,ti≥0,ti′≥0,tiup≥0,0≤ri≤R,∀i∈V,p∈P,u∈U

This study considers the dual optimization objectives of the transportation cost and the maximum allowable return time to the inspection center, as expressed in formulas (1-2). Constraint (3) means that each detection node can only be provided with a collection service by a truck or drone. Constraint (4) ensures that the detection points in the set Nk can only be served by trucks. Constraints (5-6) give the relationship between variables. Constraint (7) provides a traffic balance equation for the nodes visited during the drone trip, which can handle launch and landing nodes. Constraints (8-9) provide the total in-degree and total out-degree of the drone for each detection node to ensure that each detection node is only served once. Constraint (10) not only maintains the flow balance of trucks, but also ensures that trucks can visit a detection node at most once. Constraint (11) requires that each edge be visited by a drone at most once. Constraint (12) requires that each edge visited by the drone has at least one node service during this drone trip to prevent the drone from flying along the truck’s path unnecessarily. Constraints (13-14) determine the launch and landing nodes of the drone trip, respectively. Constraints (15-16) ensure that the launch and landing nodes of the drone must be visited and served by the truck. Constraint (17) ensures that the launch and landing nodes of the drone cannot be the same node. Constraint (18) ensures that the number of launch and landing nodes in each drone trip is equal, and there is at most one launch node in each drone trip. Constraints (19-20) represent subtours that eliminate the paths of trucks and drones. Constraint (21) is to calculate the actual time to reach node i. Constraint (22) represents the latest time for all drones to arrive at node i. Constraints (23-24) calculate the time for drones and trucks to arrive at node i, respectively. Constraints (25-26) calculate the transportation time of drones and trucks from node i to node j, respectively. Constraint (27) means calculating the number of drones on the truck when it leaves the inspection center. Constraint (28) means that if the truck wants to go from detection node i to j, then the sum of the number of drones on the truck when leaving node i and the number of drones from node i to other nodes is equal to the number of drones on the truck when leaving node j the sum of the number and the number of drones from node j to other nodes. Constraint (29) is a special case of constraint (28) at the inspection center. Constraint (30) represents the load constraint of the drone. Constraint (31) is the maximum flight distance constraint of the drone. Constraints (32-33) represent the value range of all variables.

Solution Approach

Main Objective Method

Contingent upon the specific circumstances of the issue at hand, it becomes imperative to ensure the timely conveyance of test samples to the inspection center, adhering to their stipulated validity periods. Consequently, this study adopts the main objective method for addressing the bi-objective programming model. In this model, we designate objective function (1) as the principal aim, relegating objective function (2) to the status of a constraint. By doing so, we effectuate a transformation of the original bi-objective programming model into a single-objective programming model. To confine the ultimate timeframe for the fleet’s return to the inspection center, we refine objective function (2) into formula (34).

(34)
tn+1≤e

Genetic Adaptive Large-scale Neighborhood Search Algorithm

Algorithm Framework

Murry et al.’s [7] research shows that the MFSTSP problem is NP-hard, so the MV-MFSTSP problem is also NP-hard. The ALNS algorithm has been widely used to solve NP-hard problems [36], and the operators of ALNS are customizable. Hence, it can specifically optimize the paths for trucks and drones to work together. Considering that the precision of solution and the pace of convergence in ALNS are notably influenced by the initial solution, we advocate for the adoption of a “sort first, then group” approach to constructing the initial solution, which leverages genetic algorithms. Furthermore, to mitigate the risk of ALNS getting trapped in local optima and to enhance algorithmic efficiency, we incorporate the Metropolis acceptance criterion from Simulated Annealing (SA) into ALNS. This refined algorithm is denominated as the Genetic Adaptive Large-Scale Neighborhood Search Algorithm (GALNS) [44].

The fundamental concept underlying the Metropolis acceptance criterion is to probabilistically embrace new solutions during each iteration, thus circumventing entrapment within a local optimum [45]. The probability associated with accepting these new solutions is determined by Formula (35):

(35)
P={1,f(Snew)<f(Scurr),e−[f(Snew)−f(Scurr)]/T,f(Snew)≥f(Scurr).

where, f(Scurr) represents the objective function value of the current solution, and f(Scurr) represents the objective function value of the new solution. As the number of iterations increases, the probability of acceptance will definitely decrease. This is because the search time needs to be reduced, that is, the temperature T decreases as the number of iterations increases. The formula is as follows:

(36)
Tgen+1=αTgen

where, α is the cooling factor, 0<α<1.

This study formulates three sets of operator pairs and employs the roulette principle for their selection. These operator pairs individually undertake the task of destroy and repair of the existing solution, guided by the principles of “randomness,” “correlation,” and “whole path reconstruction.” Such an approach not only broadens the domain of viable solutions but also contributes to an enhanced level of solution precision. The probability associated with the selection of an operator pair is delineated in Formula (37).

(37)
Pj=wj/∑k=1|Ω|wk,j=1,2,...,|Ω|

where, wj represents the weight of the operator to j, and |Ω| represents the total number of operator pairs.

The weighting of operator pairs undergoes dynamic adjustments in response to performance score fluctuations throughout the iterative process. If the new solution Snew, following the operator pair exploration, ascends as the fresh global optimum solution, it shall receive a points. When the new solution Snew is better than the current solution Scurr, b points are given; when the new solution Snew is worse than the current solution Scurr but accepted by the acceptance criterion, c points are given, otherwise, d points are given, where a3 b3 c3 d. The weight wj undergoes updating according to the formula (38).

(38)
wj=βwj0+(1−β)(Ψj/Πj),j=1,2,...,|Ω|

where, β represents the reaction parameter, β∈[0,1]. wj0 signifies the historical weight. Ψj denotes the score corresponding to operator pair j, and Πj reflects the frequency of utilization of operator pair j.

The framework of GALNS is shown in Fig. 3.

Construct Initial Solution

The dimensions and length of the solution to the MV-MFSTSP problem are not predetermined, rendering the conventional approach to initial solution construction impractical. Consequently, this study introduces a novel “sort first, then group” method for the initial solution construction, leveraging genetic algorithms. The fundamental concept is as follows: Firstly, employ a genetic algorithm to ascertain the optimal truck delivery paths for all nodes. Subsequently, categorize all nodes into two groups: one comprises nodes amenable to both drones and trucks, while the other consists of nodes exclusively suitable for truck service. Thereafter, eliminate nodes of the first category from the truck path, followed by determining the nodes to be serviced by drones based on Formula (39). This formula accounts for the overall transportation cost when distinct vehicle types serve each node. In essence, we eliminate the most expensive nodes for drone delivery and insert these omitted nodes into the most economical positions along the truck’s path. This step expedites the search for the optimal solution during subsequent optimization processes. Lastly, we sequentially insert the omitted nodes at positions where the increase in total transportation cost is minimal. Following the insertion of each node, the algorithm scrutinizes whether the present path complies with the drone’s load capacity, endurance, and sample validity constraints. Subsequently, it reevaluates the cost associated with each uninserted node when placed at various positions within the current path. If during the process of inserting nodes, there is a path that does not satisfy the constraints, then the algorithm will add a new drone path or add the node to the truck path to ensure that all nodes are eventually inserted into the path. As illustrated in Fig. 4, we can derive Formula (39).

Fig. 4.

Demonstration diagram of a simple path.

https://www.pjoes.com/f/fulltexts/175025/PolJEnvironStud-2024-33-3-2663-2677_Fig_4_min.jpg
Fig. 3.

GALNS algorithm framework.

https://www.pjoes.com/f/fulltexts/175025/PolJEnvironStud-2024-33-3-2663-2677_Fig_3_min.jpg
(39)
f(B)={(|AB|+|BC|)×η×C1≥(|AB|+|BC|)×C2+|AC|×η×C1,Node B is serviced by drone,Other,Node B is serviced by truck.

Pursuant to Formula (39), we can deduce a lemma that will provide useful help for guiding parameter selection.

Lemma: When η≥AB+BCAB+BC−AC×C2C1 or C2C1≥AB+BC(AB+BC−AC)×η is established, node B can save transportation costs by choosing drone service.

Operator Design

(1) randDestory and randRepair

Operator randDestory represents randomly deleting a node from the current solution, while operator randRepair represents inserting the deleted node into a position that minimizes the increase in transportation cost. Its calculation method is shown in formula (40).

(40)
minr∈removedΔfri=fri−f0

where, f0 represents the transportation cost of the destroyed solution, fri represents the transportation cost of node r at the i-th position, Δ fri represents the transportation cost increment of node r inserted into position i, and removed represents the set of removed nodes.

Taking Fig. 5 as an example, we first randomly selected the drone launch node 2 as the node to be removed. In this operation, since the drone path where node 2 is located is still serving node 3, we need to remove node 3 as well and store them as a set in the node set to be removed. Then, according to the calculation method of formula (39), we sequentially insert node 2 and node 3 into the position that minimizes the increase in transportation cost.

(2) relatedDestory and relatedRepair

Operator relatedDestory refers to removing several related nodes according to formula (41-42).

(41)
R(i,j)=1/(d¯ij+Vij),∀i∈C,j∈C,i≠j
(42)
d¯ij=dij/maxdij,(maxdij≠0)

where, d¯ij is the standardized value of dij, d¯ij∈[0,1]. Vij = 1 indicates that node i and node j are not on the same path, otherwise Vij = 0. When R(i,j) is larger, the correlation between node i and node j is greater.

The operation of operator relatedRepair is to try to re-insert the removed node to the position with the largest regret value while satisfying the conditions of load capacity, endurance, and sample validity. The regret value refers to the cost difference between the node’s optimal insertion position and the sub-optimal insertion position in the truck and drone paths, and its calculation method is as shown in formula (43).

(43)
maxr∈removedHr=Δfrl2−Δfrl1

where, Δ fri represents the transportation cost increment when node r is inserted into the position i, and l1 and l2 respectively represent the minimum and sub-minimum positions of the transportation cost increment when node r is inserted into the destroyed solution. The regret value Hr represents the cost difference of inserting node r into the destroyed solution.

Taking Fig. 6 as an example, we first selected the drone launch node 3 and landing node 4 as the nodes to be removed based on formula (41). In this operation, node 7 in the path also needs to be removed and stored in the set of nodes to be removed. Then, we will sequentially insert the nodes in the node set to be removed to the position with the largest regret value according to formula (43).

(3) wholeUavpathDestory and wholeUavpathRepair

Operator wholeUavpathDestory means to randomly delete a drone path from the current solution, while operator wholeUavpathRepair will sequentially insert the drone service nodes in the deleted drone path to the position with the smallest transportation cost increment. Taking Fig. 7 as an example, we first randomly selected a drone path R1 for deletion, and stored the node 6 served by the drone in the removed node set. Next, we insert node 6 into the appropriate location one by one according to the principle of minimum transportation cost increment.

Fig. 5.

randDestory and randRepair.

https://www.pjoes.com/f/fulltexts/175025/PolJEnvironStud-2024-33-3-2663-2677_Fig_5_min.jpg
Fig. 7.

wholeUavpathDestory and wholeUavpathRepair.

https://www.pjoes.com/f/fulltexts/175025/PolJEnvironStud-2024-33-3-2663-2677_Fig_7_min.jpg
Fig. 6.

relatedDestory and relatedRepair

https://www.pjoes.com/f/fulltexts/175025/PolJEnvironStud-2024-33-3-2663-2677_Fig_6_min.jpg

Experiment

Because MV-MFSTSP is an extended problem of the MFSTSP, this study chooses to use the test instance of the MFSTSP [7] to evaluate the performance of our proposed model and algorithm. All test cases featured within this paper can be accessed online at the following link: https://github.com/optimatorlab/ mFSTSP. We employ Gurobi (version 9.1.2) for resolving the MIP model, utilizing Python (version 3.9) as the programming language, and configuring a maximum runtime constraint of 3600 seconds. For algorithms such as GALNS, we utilize Matlab (version 2018b) for implementation, imposing a maximum iteration limit of 200. All coding endeavors are conducted on a server furnished with an Intel(R) Core (TM) i5-10200H CPU @ 2.40GHz. Referring to the performance parameters of multi-rotor drones [46] and the parameters of standard nucleic acid detection samples [4], the parameters are set as shown in Table 3.

Comparative Analysis of Small-Scale Instances

Owing to the inherent intricacy of the MV-MFSTSP problem, the exact solver can exclusively procure optimal solutions for small-scale instance. Consequently, we confine the node count in our instances to a maximum of 20 nodes. We then apply both the GALNS algorithm and the Gurobi solver to these instances, yielding a comparative analysis presented in Table 4. Regarding the Gurobi’s solution, this table documents the upper and lower bounds (Obj_UB, Obj_LB) pertaining to the optimal solution value, alongside its corresponding runtime (Time) and disparity between them (GAP = (Obj _UB - Obj _ LB)/Objj _UB*100%). Regarding the GALNS solution, this table records the optimal solution value (Obj) and the computation time (Time) obtained via GALNS, while denoting the disparity between them as GAP1 = (Obj _UB - Obj)/Objj _UB*100%. The test instances are categorized based on their node quantities (Num), and Table 4 documents the corresponding mean values (AVG.) for each group of test instances.

According to the results, the MV-MFSTSP challenge can be optimally addressed employing the Gurobi solver for instances featuring a modest scale of no more than 10 detection nodes. However, as the number of nodes increases to 15 (20), the optimal solution cannot be obtained within 3600 seconds. On average, the gap between the upper and lower bounds of the solution is 18% (41%). This shows that as the node size increases, the solver performance decreases drastically and more computation time is required. In contrast, the GALNS algorithm exhibits commendable performance not only for smaller-scale predicaments but also maintains a minimal disparity with Gurobi’s solutions when tackling 15 and 20-node challenges. On average, GALNS demonstrates efficiency in terms of computation time and solution quality for cases involving 5 and 10 nodes. Nevertheless, when the node count escalates to 15 and 20, GALNS performance exhibits a slight reduction, yet it continues to boast relatively expeditious computation times. In general, it is necessary to design a heuristic algorithm for MV-MFSTSP to solve.

Table 3.

GALNS parameters.

ParameterValueParameterValueParameterValue
NIND50Qu15 lbVu0.75 km/min
Pc0.9Dmax20kmCu0.078
Pm0.05α0.97Vk0.5 km/min
ζ100β0.5C0.78
Tmin10a, b, c, d1.5, 1.2, 0.8, 0.6η2
T01000s3 min//

Comparative Analysis of Medium-Scale and Large-Scale Instances

The ALNS algorithm is commonly employed for addressing the collaborative delivery path optimization problem concerning trucks and drones [36]. Hence, to assess the algorithm’s efficacy, this paper applies both the GALNS and ALNS algorithms to medium- and large-scale instances, subsequently compares their solution results (Table 5). Table 5 shows the name of the calculation example (Instance), the number of nodes (Num), the optimal solution value of the algorithm (ObjALNS and ObjGALNS) and the difference value between them. The computational formula is denoted as GAP2 = (ObjALNS - ObjGALNS)/ ObjALNS*100%. To reduce the impact of chance, the LNS and GALNS algorithms were executed 20 times for each computational instance to ascertain the minimum value. These test instances are categorized based on their node quantities, and Table 5 catalogues the corresponding mean values (AVG) for each cohort of test instances.

Table 4.

Small-scale instance result comparison.

InstanceNumGurobiGALNSGAP1
Obj_UBObj_LBGAPTimeObjTime
20170606T113038113409533.1833.180133.180.230
20170606T113251786976528.2428.240128.240.230
20170606T113339368121543.3843.380143.380.190
20170606T113427164164531.9531.950131.950.210
20170606T113515209066523.3523.350123.350.260
AVG.532.0232.020132.020.220
20170606T1130381134091036.3336.3301036.330.210
20170606T1132517869761051.8451.84020551.840.220
20170606T1133393681211030.575.570.82360030.570.620
20170606T1134271641641038.4538.450117138.450.290
20170606T1135152090661083.8583.8501583.850.30
AVG.1048.2143.210.161000.248.210.330
20170606T1130381134091555.8653.10.05360053.580.320.04
20170606T1132517869761549.3945.810.07360046.850.580.05
20170606T1133393681211547.4443.640.08360048.41.01-0.02
20170606T1134271641641521.227.270.66360019.350.250.09
20170606T1135152090661586.9485.50.02360087.250.250
AVG.1552.1747.060.18360051.090.480.02
20170606T1130381134092081.1357.530.29360083.280.72-0.03
20170606T1132517869762093.354.540.42360094.240.74-0.01
20170606T1133393681212079.0562.130.21360081.150.61-0.03
20170606T1134271641642092.1931.870.65360090.851.010.01
20170606T1135152090662093.0850.70.463600103.490.71-0.11
AVG.2087.7551.350.41360090.600.76-0.03
Table 5.

Solution results of different algorithms.

InstanceNumObjALNSObjGALNSGAP2
20170606T11451122113250123.75117.490.05
20170606T11465488247250128.42124.060.04
20170606T11484093046150202.6168.970.20
20170606T1153033416545099.9099.900.00
20170606T11543734843650143.05123.480.16
AVG.50139.54126.780.10
20170606T115823934453100244.41215.890.13
20170606T120227545709100220.15177.580.24
20170606T121241353494100252.91201.360.26
20170606T121632081849100302.67247.540.22
20170606T122019874088100236.13179.330.32
AVG.100251.25204.340.23

In the case of the 50-node instance, the ALNS algorithm yields an average optimal solution of 139.54, whereas the GALNS algorithm attains an average optimal solution of 126.78, with a mere 0.10 average disparity between them. As the node count escalates to 100, the ALNS algorithm’s average optimal solution stands at 251.25, whereas the GALNS algorithm achieves an average optimal solution of 204.34, resulting in an average difference of 0.23. In summation, when the node count remains below 100, the GALNS algorithm outperforms the ALNS algorithm. This superiority arises from the GALNS algorithm’s optimization grounded in a superior initial solution and the inclusion of a simulated annealing acceptance criterion, which effectively circumvents local optima, thereby enhancing the algorithm’s performance.

Comparative Analysis of Different Transport Modes

If the inspection center exclusively employs trucks for operations, this mode is referred to as the traditional truck transfer mode (Truck). Conversely, when the inspection center utilizes a truck carry out multiple drones, each endowed with multi-visit capabilities, operating in tandem, this mode is designated as the truck and drone cooperative transfer mode (Truck + Drone). To delve deeper into the merits and demerits of these two operational modes, we applied them to five test instances comprising 100 nodes. The comparative outcomes are delineated in Table 6 and Fig. 8. Additionally, we selected the computation instance “20170606T115823934453” to illustrate the optimal route for traditional truck transfer (Fig. 9) and the optimal route for truck and drone cooperative transfer (Fig. 10).

Fig. 8.

Comparison chart of different working modes.

https://www.pjoes.com/f/fulltexts/175025/PolJEnvironStud-2024-33-3-2663-2677_Fig_8_min.jpg
Table 6.

Comparison results of different working modes.

InstanceNumTruckTruck + DroneGAP3
20170606T115823934453100300.87215.890.39
20170606T120227545709100306.29177.580.72
20170606T121241353494100294.93201.360.46
20170606T121632081849100309.04247.540.25
20170606T122019874088100296.43179.330.65
AVG.100301.51204.340.50

The findings demonstrate that the synergy between trucks and drones in the transport paradigm confers distinct competitive advantages when compared to the traditional truck-based transportation model, particularly in cost reduction for conveying nucleic acid testing samples. Across the five computation instances, the collaborative transfer truck and drone model yielded a noteworthy 50% reduction in transportation costs on average. For medical testing facilities, this collaborative transport model presents a pioneering and effective resolution for the conveyance of nucleic acid testing samples, delivering substantial cost savings, heightened efficiency, and expedited test result acquisition.

Fig. 9.

Optimal route for traditional truck transfer.

https://www.pjoes.com/f/fulltexts/175025/PolJEnvironStud-2024-33-3-2663-2677_Fig_9_min.jpg
Fig. 10.

Optimal route for truck and drone cooperative transfer.

https://www.pjoes.com/f/fulltexts/175025/PolJEnvironStud-2024-33-3-2663-2677_Fig_10_min.jpg

Conclusions

This study proposes an innovative solution to address the challenges faced in COVID-19 sample transport and climate change. Our approach is based on a co-transport working model of multiple multi-visit drones on a truck, with the primary objectives of cost minimization and swift return of samples to the inspection center. To achieve this objective, we established a model of the MV-MFSTSP in which two vehicles work together, and adopted a solving algorithm called GALNS. This algorithm comprises three pivotal components: firstly, an initial solution construction method founded on genetic algorithms, which formulates the initial solution through the “sort first, then group” methodology; secondly, the ALNS algorithm, which uses customized neighborhood operations to continuously improve the solution; Finally, we introduce a simulated annealing mechanism to further augment the algorithm’s performance. Through testing across various scales, our research findings evince that the proposed MV-MFSTSP model and the GALNS algorithm exhibit wide-ranging applicability and effectiveness. Compared with the traditional truck transfer model, our solution is more competitive in reducing transmission risks, saving costs and reducing greenhouse gas emissions.

Future research endeavors shall encompass the exploration of integrating multiple trucks to enhance the efficiency of sample transfers. Moreover, we shall take into account real-world delivery time window constraints to better align with the exigency of timely sample delivery. Our ongoing efforts shall also involve the development of even more streamlined algorithms dedicated to resolving this problem model.