Ant colony algorithm to solve a drone routing problem for hazardous waste collection

Abstract

Waste management issues are affecting the economic and environmental aspects of modern societies. Thus, growing the interest of academic and industrial research and development in optimizing the process of waste management. As these issues greatly impact human health and environmental aspects and impose a threat, hazardous waste management requires even much more attention. The problem studied in this research is a variant of the vehicle routing problem using an unmanned aerial vehicle (UAV). The focus of this research is on planning the routes for waste collection and disposal using a UAV. The aim is to collect all the waste as early as possible respecting two constraints; the maximum flying and load capacities of the UAV. A two-phase approach has been proposed to solve the investigated problem. This approach is a hybridization of a developed heuristic (IMWMTT) and an Ant Colony Optimization (ACO) algorithm. The experimental study showed that the hybrid approach outperforms a recently published heuristic MWMTT for all tested instances of various sizes.

Keywords:

• Ant colony optimization
• drone capacity
• drone routing problem
• hazardous waste collection

1. Introduction

Waste management is one of the major problems of modern societies, due to the rise in the amount of generated waste. These problems have a great economic and social impact. Thus, the optimization of waste collection and disposal processes are of great importance. In a waste collection problem, the waste is to be collected from several sites and disposed-off to disposal facilities (Dotoli & Epicoco, 2017). When dealing with hazardous waste such as chemicals, food waste, and medicines, special collection and disposal management is required, making the problem more complicated. Here, heterogeneity of waste, such as different types of hazardous waste in terms of toxicity, makes the problem more complex. The objective is to ensure, safe, efficient, and economical collection, transportation, treatment, and disposal of the hazardous waste. With the rapid development of the technology, drones, called also unmanned aerial vehicles (UAVs) are also being used for hazardous waste collection. Along with the gaining popularity of UAVs in various applications, new challenging problems are arising, and many algorithms are being developed to overcome those challenges. In fact, UAVs can be used in cooperation with AI and IoT techniques to minimize the food wastes as it was mentioned in Said et al. (2023) or any other type of hazardous wastes. The UAV routing problems have not been fully investigated in the literature yet and is gaining interest among scientific communities.

With the increasing amount of waste and the lack of adequate collection and disposal infrastructure has become one of the major issues in waste management. Thus, inadequate proper collection, transportation, and disposal of waste results in serious environmental issues. Furthermore, handling hazardous waste is critical. It might cause issues such as, health impact, soil contamination, and air emissions (Alhakami, Kamal, Sulaiman, Alhakami, & Baz, 2022), etc. which may lead to infections and transmit diseases.

The waste management process impacts the economic and environmental aspects of modern societies in multiple ways. These include, reducing the overall cost of waste disposal, reduce pollution, reduce greenhouse gases, etc. There are several challenges and threats associated with every waste management including hazardous waste management. These in collection and disposal infrastructure, financial constraints, lack of support from localities, ineffective recycling or composting, ever-changing climate, lack of technological advances, changing consumer preferences, unclear regulations and so on. The hazardous waste may have certain properties, such as, flammable, corrosive/caustic, explosive/reactive, toxic/poison. Thus, these products become a hazard when improper use or disposal will cause a threat to the environment or human health.

With the drone technology, industries and their traditional methodologies are being redefined. UAVs have unlocked their potential in the waste management industry yet again and have proved to be the most economical, practical, efficient, and accurate equipment. UAVs have a great potential and is employed for many applications, such as, collecting garbage, monitoring waste treatment, cleaning power lines, mapping landfills, managing cells, calculating landfill capacity, monitoring methane emissions, observing protected areas, airspace calculations and so on.

Unmanned aerial vehicles (UAVs) have become quite popular in recent years especially in handling the two prominent and related types of combinatorial optimization problems which are the travelling salesman problem (TSP) and the vehicle routing problem (VRP). In a TSP, a vehicle’s capacity limitation is not considered, while in a VRP, it is. Thus, the solution to a TSP forms one tour to serve multiple sites, while the solution to a VRP forms multiple tours to serve multiple sites. The UAV route planning is closely related to VRP and multiple-TSP (m-TSP). The VRP is a very well-known and an NP-hard problem in operational research and combinatorial optimization. In such problems, routes are formed such that a set of nodes are visited while minimizing the total traveling cost. A classical variant of VRP is a capacitated VRP (CVRP) where a vehicle has a weight capacity to be respected while forming tours.

In this article, we focus on finding the best possible routes to be taken by the UAV to collect the total waste from a set of sites under some restrictions in the minimum time. For instance, the UAV begins a route from a depot, collects the waste from some sites, discharges it in a landfill site, and then either starts another tour or returns to the depot to get charged. The motivation behind this research is to contribute to the field of research involving vehicle routing problems using UAVs. The goal will be optimizing the hazardous waste collection from different sites by finding the best routes planning using one UAV. As the waste is very dangerous for both human and environment, it has to be collected and discharged as soon as possible. This leads us to find an optimal or near optimal routing plan for the UAV to be able to collect the waste in the shortest possible time.

As the UAV has flying and weight capacities, the investigated problem is closely related to CVRP as well as m-TSP. However, the UAV flying capacity and the need for regular charging make the studied problem more complex than CVRP. To the best of our knowledge, no other research studied our problem with the given constraints except a recently published paper by Kaabi, Harrath, Mahjoub, Hewahi, and Abdulsattar (2022). The current research uses ant colony to propose an improvement of a heuristic published by the same authors. In this article, a 2-step approach is developed. In the first step, a heuristic approach is proposed to utilize the maximum flying capacity of the UAV during each trip. In the second step, the waste collection time is minimized using a meta-heuristic based on a variant of the Ant Colony Optimization (ACO) algorithm. As it will be shown in the rest of the paper, the proposed solution manages better the usage of the UAV’s flying capacity by eliminating many unneeded returns to the depot and therefore minimizes the total collection time.

The remaining of the article is structured as follows. In section 2, the literature review highlights the related and relevant areas of the research. Section 3 includes the problem definition, its constraints, and objectives. The methodology used for conducting the research is detailed in section 4. Next, the experimental results and discussion are explained in section 5 followed by the conclusion and future work.

2. Literature review

Unmanned Aerial Vehicles also known as drones are remotely operated aircraft which were earlier used for defense purposes but now are found to be very useful for various civilian and environmental applications (Macrina, Pugliese, Guerriero, & Laporte, 2020). UAVs are being used for pick-up and delivery purposes as mentioned by Cokyasar (2021) and Karak and Abdelghany (2019), to transport lightweight or hazardous waste safely to and from the customers. To accomplish the aforementioned purposes, the UAV routes need to be planned to visit different sites achieving certain objectives. The two prominent and related types of routing problems are TSP and VRP (Liu, Lin, Chiu, Tsao, & Wang, 2014).

The basis for all routing problems is VRP, hence, different types of UAV Routing Problems (UAVRPs) are widely studied. Different variants of VRP are discussed by Thibbotuwawa, Bocewicz, Nielsen, and Banaszak (2020) which are then related to UAVRP for optimization. A CVRP was studied in Sitek, Wikarek, Rutczyńska-Wdowiak, Bocewicz, and Banaszak (2021). The authors proposed a hybrid approach integrating constraint programming, genetic algorithm, and mathematical programming and achieved promising results. Along with CVRP, four other variants of VRP were solved by Pisinger and Ropke (2007) which include VRP with time windows, multiple-depot VRP, site-dependent VRP, and open VRP using adaptive large neighborhood search framework. In Montoya-Torres, Franco, Isaza, Jiménez, and Herazo-Padilla (2015), the authors presented a state-of-the-art survey on VRP with multiple depots. They reviewed papers in which different variants of VRP are studied.

Similarly, TSP approaches are utilized for UAV routing as well. Many TSP variants are provided in Thibbotuwawa et al. (2020) which include: heterogeneous, multiple depot, multiple TSP, dynamic traveling repair-person problem, and multi-vehicle TSP. In Babel (2017), the author proposed heuristic algorithms to minimize the total tour length of the curvature-constrained TSP with obstacles and conducted the experimental study using randomly generated scenarios with obstacles of different size and number. In Manyam et al. (2016), the authors studied a novel GPS denied routing problem referred to as the Communication Constrained UAV Routing Problem. The authors used existing methods to solve the cases of two and three UAVs. Furthermore, in Furini, Persiani, and Toth (2016) for time-dependent TSP in controlled airspace, the authors minimized the total traveling time and the holding time over mission way points for the homogeneous fleet of UAVs. A mathematical formulation based on a particular version of the Time Dependent TSP and a Branch and Cut algorithm is proposed.

Many solutions towards planning UAV routes have been proposed in the literature. In Aggarwal and Kumar (2020), a review was conducted on different path planning techniques used for UAVs. Some of these techniques include sampling-based techniques, artificial intelligence techniques, cooperative techniques (mathematical models, bio-inspired models, machine learning models, and multi-objective optimization models), and non-cooperative techniques.

The most common classification of the proposed solutions in the literature was provided by Montoya-Torres et al. (2015): exact solutions, heuristics algorithms, and meta-heuristic algorithms. Sometimes categorized as exact approaches and approximate approaches: heuristic and meta-heuristic (Sitek et al., 2021). Zhao, Zheng, and Liu (2018) have conducted a detailed analysis on computational intelligence algorithms. These algorithms are nature-inspired computational techniques that can address large and real-world problems that cannot be addressed using classical and mathematical models (Azar & Vaidyanathan, 2015). Examples of such algorithms are fuzzy logic, neuron computing, genetic computing, and probabilistic computing.

There are a number of research works proposing exact solutions to routing problems, such as branch and bound algorithm and its variants, mathematical programming models, and constraint programming models. Abdennebi (2017) used the exact method for path planning for UAVs based on integer linear formulation of the problem. The aim was to minimize the delay in reaching a destination while ensuring a certain delivery ratio of messages reporting the drone’s positions. It was found that the generation of the exact solution was limited by the computation complexity. Therefore, in Abdennebi (2017), the authors proposed an approach based on heuristic specifically based on the Dijkstra’s algorithm. This proposed solution covered a large area and generated a set of optimum and near-optimum paths according to the UAV’s battery capacities. In a recent study by Chen, Du, Zhang, Han, and Wei (2021a), the authors proposed an exact formulation based on mixed integer linear programming to produce optimal flight paths for a fleet of UAVs. The authors, however, did not recommend using this solution for large numbers of UAVs and regions as it will spend a huge amount of time in considering the possible flight paths.

As VRPs are complex real-life problems, the search state space is usually very large. Hence, exact approaches are often not able to solve VRPs of real sizes within reasonable time frames (Sitek & Wikarek, 2019). The exact solutions or approaches intent to solve the small-sized problem and obtain an optimal solution. As VRP is an NP-hard problem, approximate approaches are widely adopted to obtain good if not optimal solutions in polynomial time. Sometimes exact methods are used in combination with heuristic and metaheuristic techniques for finding initial solutions or pre-solving. According to Sitek et al. (2021), the approximate solutions which are found to obtain promising results are: Cluster-first, route-second, neighborhood search, route construction heuristics, granular tabu search, ant colony optimization, genetic algorithms, simulated annealing, and greedy randomized adaptive search procedures.

Due to the NP-hardness of the VRP, several heuristic and meta-heuristic algorithms have been proposed in the literature. In Xia, Jun, Manyi, Ming, and Zhike (2009), a 3D vehicle path planning method based on heuristic A* algorithm and a mathematical model were proposed. It was shown that the proposed heuristic is adaptive for different missions of the UAVs. In Li, Yang, Tong, and Shen (2018), the authors proposed Greedy and Q-learning algorithms for UAV path planning in a risky environment. The Greedy algorithm obtained high-quality solutions in a relatively short time and was robust. While Q-learning was preferred for obtaining less risky solutions. Silva Arantes, Silva Arantes, Motta Toledo, Júnior, and Williams (2017) proposed a heuristic and two genetic algorithms for UAV path planning under critical conditions. The three proposed approaches were: greedy heuristic, genetic algorithm, and multi-population genetic algorithm. A large set of scenarios were tested using the FlightGear simulator. Based on the statistical analysis, a combination of greedy heuristic with the genetic algorithms was found to be a good strategy. Chen et al. (2021a) proposed a Spatial-temporal Clustering-Based Algorithm to obtain flight paths for autonomous heterogeneous UAVs. This two-phase approach clusters the regions to be visited using their densities calculated via relative distances. In another study, Chen, Zhang, Wu, You, and Ning (2021b) propose a new method to solve similar problem. Their solution was inspired by the density-based clustering analysis and symbiotic interaction behaviors of organisms to settle the UAVs path planning problem.

In a recent research (Kaabi et al., 2022), proposed a 2-phase solution approach to solve a single UAV path routing problem with an objective to collect the maximum of waste from a number of sites in a minimum time. The first phase is based on a heuristic that generates feasible tours. While in the second phase a linear program optimally schedules the trips.

Nature-inspired algorithms are commonly used to solve path planning optimization problems. Genetic algorithm, ant colony optimization and particle swarm optimization are examples of nature-inspired algorithms. In Ha, Deville, Pham, and Hà (2020), the authors studied the TSP with drone in which a truck and drone are used to deliver parcels to customers. Two objectives were considered namely minimize the total operational cost and minimize the completion time for the truck and drone. A hybrid genetic algorithm was developed to solve the problem. The capacitated multi depot (Distribution center/Collection center) heterogeneous green vehicle routing problem with simultaneous pickup and delivery was addressed by Sherif, Asokan, Sasikumar, Mathiyazhagan, and Jerald (2021). A Simulated Annealing Algorithm with swap neighbourhood solution method was proposed. A meta-heuristic swarm-based optimization technique that simulates natural water drops was proposed by Jaradat (2020) to solve a school bus routing problem. In Qu, Gai, Zhang, and Zhong (2020), a hybrid algorithm combining simplified grey wolf optimizer and modified symbiotic organisms search was developed to solve an unmanned aerial vehicle path planning problem. Moreover, standard grey wolf optimization was adapted by Sopto, Ayon, Akhand, and Siddique (2018) to address a TSP problem. A path planning for UAVs in Three Dimensional Dynamic Environment is considered in Goel, Varshney, Jain, Maheshwari, and Shukla (2018). In this study, the authors used a Glow-worm Swarm Optimization method for planning the paths of the UAVs. In Pandiri and Singh (2018), a k-Interconnected Multi-Depot Multi-Traveling Salesman Problem was investigated. To solve this problem, a hyper-heuristic based artificial bee colony algorithm was proposed.

When comparing the performance of approximate approaches of heuristics and meta-heuristics, it was found that in terms of accuracy Ant Colony Optimization achieved better results as compared to Genetic Algorithms (GA) and Simulated Annealing (SA) (Mukhairez & Maghari, 2015). Based on the performance analysis of GA and PSO, it was found that limited success was shown for the PSO algorithm towards more complex and richer areas such as combinatorial optimization (Gharib, Benhra, & Chaouqi, 2015). Hence, GA was found to perform better than PSO. When comparing the performance of ACO and GA. Haroun, Jamal, and Hicham (2015) found that both algorithms have a great potential for solving real-world problems such as TSP. Based on the study analysis, in terms of computational resources, GA was found to be fast, easy to implement, and cost-efficient, and suitable for small or medium-sized problems for the rapid finding of optimum solutions. Whereas, ACO obtained high-quality solutions and better results, particularly with large-size problems within a reasonable time. Furthermore, it can easily be hybridized and adjusted with other algorithms and provide better results. The study done by Chen et al. (2022) confirmed the above-mentioned facts. The authors got inspired from the foraging behaviors of ants to propose an ant colony system (ACS)-based algorithm to allocate regions to proper UAVs and to adjust the visiting orders of regions so as to reduce the completion time of the coverage task. Although we are not studying the same problem, but the way we are clustering the regions to be visited and finding the proper sequence of regions within the same cluster is comparable to their proposed ant colony-based approach.

Different terminologies are used to describe the vehicle and drone routing problems. We adopt the same terminology used in Cattaruzza, Absi, and Feillet (2016). A trip is a sequence of sites starting from and ending at the depot. Whereas, the sequence of trips is called a tour. Moreover, the problem investigated in this article is different from the classical VRP. In fact, a single UAV is used in successive trips to collect hazardous wastes from different sites. In addition, restrictions related to the sites that the UAV can or cannot fly over and flying and waste capacity of the UAV are considered.

3. Problem description

In this paper, the problem of routing a UAV for the purpose of collecting hazardous waste from different locations in a minimum time is considered. The UAV has a predefined capacity and flying time limit based on its charge. We assume that there is only one depot and one disposal locations. The UAV needs to perform many trips to collect all the waste from the given locations. When the UAV’s weight capacity reaches its limit or the charge is to be finished, the UAV ends the trip by discharging the collected waste in the disposal location and returning back to the depot for charging and eventually starts a new trip. The problem is formulated as a complete directed graph $G(V\cup \overline{F},E).$ Some required notations are summarized in Table 1.

Table 1. Summary of notations.

Notation	Definition
n	Number of sites containing a waste to be collected
m	Number of non-flying zones
C	Capacity (maximum carried weight) of the UAV
T	The maximum flying time of the UAV
$\overline{F}$	Set of non-flying zones
vi	Site or Node i
$l_{i,j}$	Length of edge $e_{ij};$ Flying time of the UAV between sites vi and vj
$\tau /2$	The time needed for the UAV to land or take-off
r	Recharging time of the UAV
wi	Weight of the waste to be collected from the site vi
V	The set of nodes (sites) to be visited by the UAV
E	The set of edges $\{e_{ij}=(v_i,v_j)|v_i,v_j\in V\cup \overline{F}\}$
v0	Depot D from where the UAV starts each trip
$v_{n+1}$	The landfill site L where the waste is discharged

Each node $v_i\in V\setminus \{v_0,v_{n+1}\}$ has a positive weight w_i which represents the amount of waste to be collected. If a site v_i is a non-flying zone, then all its ongoing and outgoing edges have lengths equal to $\infty .$

The UAV has a maximum flying capacity T that cannot be exceeded. When this flying capacity is reached, the UAV needs to be recharged, where the recharging time is denoted by r. Moreover, the UAV has a weight capacity C. The UAV starts a trip from the depot D, collects the waste from a set of sites, discharges the waste in the site L and probably returns to the depot D. The depot D is the place where the UAV is parked, eventually recharged, or maintained. The maintenance operations include changing spare parts, cleaning, sterilizing, etc. The time needed to perform such maintenance operations is neglected compared to the recharging time. This justifies why each trip must start from the depot D. The total weight of the collected waste in one trip should be smaller than or equal to C. During a trip, the UAV cannot fly over non-flying zones. Due to the limited flying and weight capacities, the UAV might not be able to collect all the wastes in one trip. Therefore, more than one trip is needed. The objective, denoted by C_max (completion time of the last traveled trip), is to collect all the wastes in a minimum time. C_max value is the sum of the total UAV’s flying time needed for visiting all the sites, the UAV’s recharging time for each trip, and all the take-off and landing times from and to each site throughout the tour.

4. The proposed approach

To solve the studied problem, we propose a 2-phase approach. Phase 1 is an improvement of an approach developed by Kaabi et al. (2022) where the use of weight and flying capacities of the UAV is optimized. For instance, the problem is relaxed by letting the UAV to start some of its trips from the landfill site L after discharging the waste and having enough charge. Further improvements were achieved via phase 2 by applying an Ant Colony Optimization Algorithm to reduce the total flying time of the UAV in each trip when it is possible.

4.1. Phase 1: An improved MWMTT heuristic algorithm

In Kaabi et al. (2022), a heuristic was used to generate a set of feasible trips, R. A feasible trip is a trip where a UAV would collect waste in shortest time respecting the maximum flying and waste capacities. Each trip ends by unloading the collected waste at the landfill site, and then returning to the depot. If there was any non-visited site remaining then the drone will be recharged before starting the next trip from the depot. The generated trips are then optimally scheduled using a linear programming model so that the last trip is ended as early as possible. This was achieved by grouping the trips into different clusters. The trips of each cluster could be performed without the need of recharging the UAV. Therefore, the UAV was recharged only after completing the trips of each cluster. This 2-step based approach was called MWMTT.

In Phase 1 of this research, the trips are generated in a different way than MWMTT. The UAV starts a trip from the depot, visits some sites according to a decreasing order of waste by time ratios. If the UAV cannot load any more waste, then it visits the landfill for discharging. If the UAV’s maximum flying time is not fully consumed, the UAV can start another trip from the landfill to visit some other sites. This process repeats until the UAV’s maximum flying capacity is reached. In this case, the tour ends by returning back to the depot for recharging and eventually some other maintenance activities. This new method of generating the tours and trips will optimize the use the UAV in term of waste and flying capacities. The steps of the Improved MWMTT (IMWMTT) are described in Algorithm 1 where W_k and T_k are the current cumulative collected weight and the current cumulative time of a trip R_k, respectively.

Algorithm 1.

IMWMTT Heuristic to generate feasible trips.

1: in: Graph $G=(V\cup \overline{F},E)$ out: R: Set of trips.

2: compute the shortest times $l_{i,n+1}^{*}$ from every node $v_i(1\le i\le n)$ to L.

3: mark the nodes of the set $\overline{V}=\{v_1,v_2,\dots ,v_n\}$ as non-visited.

4: $R\leftarrow \varnothing ,k\leftarrow 1$

5: while ($\overline{V}\ne \varnothing$) do

6:  Boolean $\mathit{continue}\leftarrow \mathit{true}$

7:  $R_k\leftarrow \left\{D\right\}$ (generate a new trip)

8:  $p\leftarrow 0$ (index of the current node of R_k), $W_k\leftarrow 0,T_k\leftarrow \frac{\tau }{2}$

9:  while (continue = true) do

10:   $X\leftarrow \varnothing$ (set of candidate nodes)

11:   for each node $v_i\in \overline{V}$ do

12:    if $W_k+w_i<C$ and $T_k+l_{p,i}+\tau +l_{i,n+1}^{*}+\tau +l_{n+1,0}+\frac{\tau }{2}<T$ then

13:     $X\leftarrow X\cup \left\{v_i\right\}$

14:    end if

15:   end for

16:   if ($X\ne \varnothing$) then

17:    select $v_i\in X$ having the maximum value of $\frac{w_i}{l_{p,i}}$

18:    $R_k\leftarrow R_k\cup \left\{v_i\right\}$

19:    mark v_i as visited $(\overline{V}\leftarrow \overline{V}\setminus \{v_i\})$

20:    $T_k\leftarrow T_k+l_{p,i}+\tau$

21:    $W_k\leftarrow W_k+w_i$

22:    $p\leftarrow i$

23:    else

24:    Boolean addD

25:    if ($p=$ L) then

26:     $\mathit{addD}\leftarrow \mathit{true}$

27:    else

28:     $\mathit{addD}\leftarrow \mathit{false}$

29:    end if

30:    if ($W_k>0$) then

31:    $R_k\leftarrow R_k\cup \left\{L\right\}$

32:    $T_k\leftarrow T_k+l_{p,n+1}^{*}+\tau$

33:    $W_k\leftarrow 0$

34:    $p\leftarrow L$

35:    end if

36:   if ($\mathit{addD}=$ true) then

37:     $\mathit{continue}\leftarrow \mathit{false}$

38:     $R_k\leftarrow R_k\cup \left\{D\right\}$

39:     $T_k\leftarrow T_k+l_{n+1,0}+\frac{\tau }{2}$

40:     $R\leftarrow R\cup \left\{R_k\right\}$

41:     $k\leftarrow k+1$

42:    end if

43:    end if

44:  end while

45:  end while

46: return $R=\{R_1,R_2,\dots ,R_s,\dots ,R_k\}$

The steps of Algorithm 1 are explained as follows:

• Graph G denotes the input. R, a set of feasible trips needed to collect all the wastes denotes the output of the algorithm (line 1).

• Compute the shortest flying time from every node $v_i,i=1\dots n$ to L. This step ensures that the flying times from the last visited node in a trip to the landfill site L is minimum. This allows the UAV to collect the maximum waste respecting its flying capacity (line 2).

• Before the tour begins, all the nodes are marked as non-visited nodes (line 3).

• Initially, the set of trips, R is empty. The trip number is denoted by k, as the first trip begins k is assigned the value 1 (line 4).

• The outer while loop (lines 5 to 45) generates a set R of feasible trips needed to collect all the wastes.

• The inner while loop (lines 9 to 44) generates the trips of the same tour.

• A feasible trip is constructed by iteratively selecting the site having the maximum waste off rate; the ratio of the waste in the site to the flying time needed to reach that site (lines 7 to 41).

• The R_k denotes the set of nodes for the kth trip of the set R. The first node added to every new trip is D having an index, p as 0. The total collected waste, W_k and the total flying time, T_k at the beginning of the trip are 0 but as the drone takes-off $\tau /2$ time is added. Thus, T_k is initialized to $\tau /2$ each time the trip begins (lines 7 and 8).

• The variable X denotes the set of candidate nodes, initialized to null (line 10).

• The for loop (lines 11 to 15) is used to create a set of candidate nodes X, i.e. the next potential nodes to be visited while respecting the maximum waste capacity and maximum flying capacity of the UAV.

• If there is at least one candidate node (lines 16 to 22).

  • Select the node v_i, the one from where maximum waste can be collected in minimum time (line 17).

  • The node v_i is then:

    • added to the set R_k (line 18)

    • marked as a visited (line 19)

  • The value of W_k, T_k and p are updated accordingly (lines 20 to 22).

• If there is no candidate node (lines 23 to 43).

  • The UAV goes to L and unloads the waste if some waste is collected, i.e. if the value of $W_k>0.$ Then the value of W_k, T_k and p are updated accordingly (lines 30 to 35).

  • The UAV returns to D (lines 36 to 42) only when the following two conditions are met.

    • The UAV is currently at L (line 25) and

    • There exists no candidate node that can be visited by UAV from L (i.e. $X=\varnothing ,$ when the current node is L)

For demonstration purposes, Algorithm 1 will be illustrated with an instance of 5 sites as shown in Table 2. The flying time $t_{ij}=\infty$ prevents the UAV from landing in the site v₀ if the collected waste is not discharged yet in v₆. In the proposed Algorithm 1, if the UAV has reached its maximum waste capacity, then it must first unload the collected waste before performing other trips from v₆ provided that the maximum flying time is not reached.

Table 2. Sample instance of 7 nodes.

	v0	v1	v2	v3	v4	v5	v6
v0	0	7	8	8	4	9	5
v1	$\infty$	0	4	1	7	2	7
v2	$\infty$	6	0	8	6	1	8
v3	$\infty$	5	7	0	9	2	5
v4	$\infty$	4	3	3	0	1	4
v5	$\infty$	4	3	2	9	0	6
v6	7	7	8	5	4	6	0
wi	0	7	8	7	6	11	0

$T=41,C=19,r=2,\tau =1.$

The same example when tested using MWMTT, that is, after applying LPM, to which the results are compared with, generated 3 trips. Using the proposed Algorithm 1 of Phase 1, the number of generated trips is 2, which are given as follows:

• $R_1:v_0,v_4,v_5,v_6,v_3,v_1,v_6,v_0,T_1=42,W_1=31$

• $R_2:v_0,v_2,v_6,v_0,T_2=26,W_2=8$

The objective value, C_max obtained for the sample instance is: $$C_{\max }=T_1+r+T_2=70$$

4.2. Phase 2: A hybrid IMWMTT and ACO Algorithm

4.2.1. Ant colony optimization algorithm

Ants when leaving their colony in search of food leave behind a chemical substance called pheromone to guide other ants. The more frequent an ant travels through a specific path, the more intense the pheromone substance remains on that particular path. With time, the intensity of the pheromone decreases due to evaporation. Every ant intends to follow the path having the most intense pheromone because the path with the most intense pheromone represents the shortest path found so far by the ants. In this way, the paths of all the ants begin to converge, and the probability of following the shortest path increases. This communication, planning, and behaviors of ants are studied and modeled as an algorithm to solve real-life complex combinational optimization problems. It is found to achieve effective results. Thus, forms the fundamentals of different variants of the ACO algorithm. Some of the common variants include Ant System (AS), Ant Colony System (ACS), Elitist ACO (EACO), Max-Min Ant System (MMAS), Rank-based Ant System (ASrank), etc.

Initially, each ant forms its tour by selecting the next unvisited site based on the pheromone deposited by previous ants. Next, the pheromone intensity of connecting edges used when constructing a tour by each ant is updated based on the tour’s quality. The quality of the tour can be evaluated using various measures such as the distance between sites, the flying time, the travel cost, etc. For the current research, the quality of the tour depends on two parameters; the amount of waste collected and the flying time spent to complete a tour. Lastly, once all the ants have finished constructing their tour and have deposited pheromones, the pheromone is evaporated from each edge based on evaporation rate. In an ACO algorithm, each ant remembers the visited sites, as well as, the total traveled time. The main steps of one of the most popular variants of ACO algorithms which is ACS developed by Dorigo and Gambardella (1997) are given in Algorithm 2.

Algorithm 2.

ACS metaheuristic algorithm

1: while (termination condition is false) do 2:  generate tour for each ant 3:  evaporate pheromone of all the edges based on evaporation rate 4:  update pheromone matrix 5: end while

Some important factors that must be considered in the algorithm to generate improved feasible tours include randomness, next site selection, pheromone update, and evaporation. Each of which is explained below briefly:

Randomness: The reason why randomness is important is that it helps in balancing between exploration (i.e. allowing ants to choose the unexplored edges with no pheromone) and exploitation (i.e. the convergence of all ants towards the path with the most intense pheromone). It is possible that some other paths may exist but have not been explored yet by the ants, which may result in a better tour. Thus, having some degree of randomness helps in finding a global optimal tour and not sticking to a local optimal tour. Thus, allowing more search space for exploration.

Next site selection: In the process of selecting the next site to be visited by the ant, a heuristic value ${\eta }_{i,j}$ is calculated which guides the ant in finding better tours. This value is the inverse of the flying time $l_{i,j}$ from site i to site j, as the objective is to minimize the tour’s total flying time. Thus, the shorter the flying time of the connecting edge, the more likely the ants will travel through it. The amount of pheromone on an edge connecting the sites i and j is denoted by ${\tau }_{i,j}.$ Note that here, ${\tau }_{i,j}$ is different from τ. Equation (1)(1) $${\rho }_{i,j}^n=\frac{{\tau }_{i,j}^{\alpha }\times {\eta }_{i,j}^{\beta }}{\sum _{i,j}^{}{\tau }_{i,j}^{\alpha }\times {\eta }_{i,j}^{\beta }}$$(1) represents the formula used for selecting the next site to visit. (1) $${\rho }_{i,j}^n=\frac{{\tau }_{i,j}^{\alpha }\times {\eta }_{i,j}^{\beta }}{\sum _{i,j}^{}{\tau }_{i,j}^{\alpha }\times {\eta }_{i,j}^{\beta }}$$(1) where n represents the nth ant, α controls the importance of pheromone impact, and β controls the importance of heuristic value impact.

Pheromone update: The pheromone deposited by the nth ant while traversing over the selected edge from site i to site j updates the pheromone value of that edge. This change in the pheromone value is denoted by $\Delta {\tau }_{i,j}^n$ given in Eq. (2)(2) $$\Delta {\tau }_{i,j}^n=\{\begin{array}{cc}\frac{Q}{T_n},\hfill & \text{if }n\text{th ant traverses from site }i\text{ to site }j\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$(2) . (2) $$\Delta {\tau }_{i,j}^n=\{\begin{array}{cc}\frac{Q}{T_n},\hfill & \text{if }n\text{th ant traverses from site }i\text{ to site }j\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$(2) where Q is a constant representing the amount of pheromone deposited by the nth ant during the flying time T_n of a tour made by ant n. As this is a minimization problem in terms of total flying time, the fraction $\frac{Q}{T_n}$ indicates that the lesser the flying time, the higher the pheromone deposited by the nth ant. Therefore, Eq. (2)(2) $$\Delta {\tau }_{i,j}^n=\{\begin{array}{cc}\frac{Q}{T_n},\hfill & \text{if }n\text{th ant traverses from site }i\text{ to site }j\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$(2) is used in updating the pheromone value of each edge once all the ants have constructed their tours. Updating the pheromone value of each edge by each ant depends on the evaporation rate of the pheromone.

Evaporation: While updating the pheromone value of each edge by the nth ant, evaporation plays a vital role. When there is some degree of evaporation, then ${\tau }_{i,j}^n$ is calculated as given in Eq. (3)(3) $${\tau }_{i,j}^n=(1-\rho )\times {\tau }_{i,j}+\sum _{n=1}^m\Delta {\tau }_{i,j}^n$$(3) . (3) $${\tau }_{i,j}^n=(1-\rho )\times {\tau }_{i,j}+\sum _{n=1}^m\Delta {\tau }_{i,j}^n$$(3) where m is the total number of ants, and ρ represents the evaporation rate ranging from 0 to 1. When ρ = 0, there is no evaporation.

4.2.2. The proposed hybrid approach

The proposed hybrid approach is a combination of Algorithms 1 and 3. The UAV trips are initially formed using the IMWMTT heuristic. As the UAV has a flying and waste capacities to be respected, it needs to perform multiple trips in order to collect the waste from all the sites. The order of the sites to be visited is planned for each trip such that the flying and waste capacities are respected, thus forming feasible tours. Every next site to be visited by the UAV is selected in such a way that the maximum waste is collected while flying for the minimum time. In each trip, the UAV may visit the landfill more than once, that is when the maximum waste capacity is reached or no more waste can be collected from any of the non-visited sites but the flying capacity is not. In this case, multiple sub-trips within the same trip will be formed. In the first sub-trip, the UAV starts from the depot, collects the maximum waste from some sites and then discharges it in the landfill. A second sub-trip, starting from the landfill is formed if the maximum flying capacity is not reached. The UAV continues performing such sub-trips until it needs to be recharged. Thus, in the last sub-trip, the UAV discharges the waste in the landfill and returns back to the depot. Each sub-trip is considered as a cluster.

Each trip in Phase-1 (IMWMTT) has been formed such that the flying capacity is respected, which contains multiple clusters respecting the waste capacity. Thus, the problem of ordering the sites within each cluster can be considered as a single objective optimization problem. Using Algorithm 3, the order of sites is rescheduled such that the UAV flies during a shorter time to visit the sites of the same cluster. The parameters used in Algorithm 3 are illustrated in Table 3. Moreover, the hybridization of Algorithms 1 and 3 is presented in Algorithm 4. The lines from 41 to 50 are added to the Phase-1 of Algorithm 1 to enhance the results obtained in Phase-1. The order of visiting the sites is updated if and only if the new order of sites within the clusters has a total flying time less than the previous order of sites.

Table 3. ACO implementation parameters.

Parameter	Values
nTrails	Number of trails
α	Pheromone importance
β	Flying time priority
ρ	Pheromone evaporation rate in each iteration
Q	Total amount of pheromone left on the trail by each Ant
antFactor	Number of ants to be used per site
randomFactor	Randomness in the simulations
maxIteration	Maximum number of iterations
maxAttempts	Maximum number of iterations
$c{l}_{i,s}$	ith cluster in trip Rs
$N_{i,s}$	Number of nodes in the cluster $c{l}_{i,s}$
partialTimeMatrix	2D array of time matrix representing partial matrix based on the sites in the cluster
initialPartialTrail	1D array of initial partial trail or order of sites formed using IMWMTT

Algorithm 3.

ACO metaheuristic to form feasible sub-trips.

1: in: cluster $c{l}_{i,s}$ of the trip R_s

2: out: $cl{\prime }_{i,s},t{\prime }_{i,s}:$ rescheduled cluster $c{l}_{i,s}$ and its total flying time.

3: $cl{\prime }_{i,s}\leftarrow c{l}_{i,s},$

4: $\mathit{attempt}\leftarrow 1,\mathit{maxAttempts}\leftarrow 5$

5: for $\mathit{attempt}\leftarrow 1$ to maxAttempts do

6:  $\mathit{iteration}\leftarrow 1$

7:  while ($\mathit{iteration}\le \mathit{maxIteration}$) do

8:   initialize trails and place each ant at D or L depending on the cluster number

9:   for each ant do

10:    while (there are non-visited sites) do

11:     move ant to next site with the possibility given in Eq. (3)(3) $${\tau }_{i,j}^n=(1-\rho )\times {\tau }_{i,j}+\sum _{n=1}^m\Delta {\tau }_{i,j}^n$$(3)

12:    end while

13:    set ant position to L

14:   end for

15:   evaporate pheromone of all the edges based on evaporation rate of Eq. (3)(3) $${\tau }_{i,j}^n=(1-\rho )\times {\tau }_{i,j}+\sum _{n=1}^m\Delta {\tau }_{i,j}^n$$(3)

16:   update pheromone matrix as given in Eq. (2)(2) $$\Delta {\tau }_{i,j}^n=\{\begin{array}{cc}\frac{Q}{T_n},\hfill & \text{if }n\text{th ant traverses from site }i\text{ to site }j\hfill \\ 0,\hfill & \text{otherwise}\hfill \end{array}$$(2)

17:   when necessary, update $cl{\prime }_{i,s}$ and $t{\prime }_{i,s}$ (among all iterations)

18:   $\mathit{iteration}\leftarrow \mathit{iteration}+1$

19:  end while

20:  when necessary, update $cl{\prime }_{i,s}$ and $t{\prime }_{i,s}$ (among all attempts)

21: end for

22: return sub-tour $cl{\prime }_{i,s}$ and its total flying time $t{\prime }_{i,s}$ (The best among all attempts)

Algorithm 4.

Hybrid IMWMTT + ACO to form feasible trips.

1: in: Graph $G=(V\cup \overline{F},E)$ out: R: Set of trips.

2: $R=\{R_1,R_2,\dots ,R_s,\dots ,R_k\}\leftarrow$ IMWMTT (G)

3: for each trip $R_s\in R$ do

4:  for each cluster $c{l}_{i,s}$ in trip R_s do

5:   $(cl{\prime }_{i,s},t{\prime }_{i,s})\leftarrow$ ACO $(c{l}_{i,s})$

6:  end for

7:  $R{\prime }_s\leftarrow$ concatenate all $cl{\prime }_{i,s}\cup \left\{D\right\}$

8:  $T{\prime }_s\leftarrow \sum _{cl{\prime }_{i,s}}t{\prime }_{i,s}+l_{n+1,0}+\frac{\tau }{2}$

9:  if $T{\prime }_s<T_s$ then

10:   $R_s\leftarrow R{\prime }_s$

11:   $T_s\leftarrow T{\prime }_s$

12:  end if

13: end for

14: return R

For better understanding, let us consider the trips formed in the illustrated example of Phase-1 (IMWMTT).

• $\begin{array}{c}{R}_1:v_0,v_4,v_5,v_6,v_3,v_1,v_6,v_0,T_1=42,W_1=31\\ c{l}_{1,1}:v_0,v_4,v_5,v_6\\ c{l}_{2,1}:v_6,v_3,v_1,v_6\end{array}$

• $\begin{array}{c}{R}_2:v_0,v_2,v_6,v_0,T_2=26,W_2=8\\ c{l}_{1,2}:v_0,v_2,v_6\end{array}$

The order of the sites in each cluster is rearranged using Algorithm 3 to minimize the total flying time of the overall trip. The total waste collected by the UAV in the overall trip will not be affected by changing the order of the sites within the clusters. After applying Algorithm 3, the order of the sites in $c{l}_{2,1}$ reduced the total flying time of the trip R₁ by 4 time units, that is, from 42 to 38. Whereas, in the trip R₂ the order of sites remains the same.

• $\begin{array}{c}{R}_1:v_0,v_4,v_5,v_6,v_1,v_3,v_6,v_0,T{\prime }_1=38,W_1=31\\ cl{\prime }_{1,1}=c{l}_{1,1}:v_0,v_4,v_5,v_6\\ cl{\prime }_{2,1}:v_6,v_1,v_3,v_6\end{array}$

• $\begin{array}{c}{R}_2:v_0,v_2,v_6,v_0,T{\prime }_2=T_2=26,W_2=8\\ cl{\prime }_{1,2}=c{l}_{1,2}:v_0,v_2,v_6\end{array}$

The new objective value, C_max obtained for the sample instance is $C_{\max }=T{\prime }_1+r+T{\prime }_2=\mathbf{66}.$ In conclusion, by applying Algorithm 3 the total flying time was minimized by 4 time units.

5. Experimental results

As this work is an extension of existing research (Kaabi et al., 2022) the same instances, that is, three datasets, namely, DS₁, DS₂, and DS₃ are used for testing and comparison. Each data set has 40 to 49 instances with the number of sites ranging from 21 to 981. Each instance has the following data:

• The waste capacity of the UAV, C

• The weight of waste to be collected from each node v_i, w_i

• The flying time between the nodes v_i to v_j, $l_{(i,j)}$

• The maximum flying time of the UAV, T

• The recharging time of the UAV, r

All the three datasets have some common data values, that is, C, w_i and $l_{i,j}.$ The remaining data values T and r, differ in the three datasets having a different range of values, it is such that every two datasets have one of two data values common.

5.1. IMWMTT (Algorithm 1): analysis of the results and Discussion

The main idea of IMWMTT was to improve the objective function value (C_max), by letting the UAV collect the maximum of waste in a minimum time while fully utilizing the maximum flying time available for the UAV during each trip. Thus, the UAV can perform another tour starting from L after unloading the waste, and does not need to return to D, until there is no such site that could be visited in the remaining flying time. This strategy ensures the best utilization of the maximum flying capacity and helps in minimizing the number of needed trips. The key difference in generating trips between the IMWMTT and MWMTT heuristics is that the drone’s fuel and weight capacity is used to the maximum as possible. The route will be such that IMWMTT would avoid the drone to refill fuel until needed and would continue its route by disposing off the waste if the waste capacity is reached. The proposed hybrid approach updates the order of sites within clusters by skipping to visit the depot unless required, i.e., only when the fuel needs to be refilled and the objective optimized during this process is the total travel time which will eventually affect the C_max objective as well. Figure 1 illustrates the comparison of the objective values of MWMTT (Kaabi et al., 2022) and IMWMTT (Algorithm 1) using the instances of three datasets, DS₁, DS₂, and DS₃. This figure shows the number of sites in each instance on the x-axis and the objective values on the y-axis. It is clear that there is a noticeable improvement of the obtained results for all three datasets. The results indicate better utilization of flying time by the UAV.

Figure 1. Performance of IMWMTT and MWMTT for different data sets.

The number of tours in a trip of each instance of the three datasets, DS₁, DS₂, and DS₃, generated using MWMTT when compared with the proposed IMWMTT results, are found to be reduced. Based on the experimental results in comparison with the MWMTT, the average percentage of the number of tours generated by the MWMTT is reduced by 27, 24, and 25% for the datasets DS1, DS2, and DS3, respectively by applying IMWMTT.

Based on the experimental results for the three datasets, DS₁, DS₂, and DS₃, the results obtained are as follows. The improvements in the values of C_max are in $[4.5\%,23.8\%]$ for DS₁, $[2.3\%,24.5\%]$ for DS₂, and $[2.6\%,23.7\%]$ for DS₃. To compare the results, that is, the performance and the quality of the solutions of proposed hybrid approach with the MWMTT heuristic, the same dataset was used for experimental study. It was found that there is a noticeable improvement of the obtained results for all the three datasets. The results indicate better utilization of flying time by the UAV. Thus, improving the objective value, C_max. Furthermore, the efficiency of Algorithm 1 can be supported by comparing the percentage error values of the obtained results with lower bound values given in Kaabi et al. (2022). The average percentage error of IMWMTT is found to be reduced for each of the three datasets. These average percentage error values after applying IMWMTT are 31.6, 21.9, and 15.9% for DS₁, DS₂, and DS₃, respectively. Thus, are found to be reduced by 11.5, 13.7, and 12.5% for DS₁, DS₂, and DS₃, respectively, when compared with the percentage error values of the compared research work, MWMTT.

5.2. Hybrid IMWMTT + ACO (Algorithm 4): analysis of the results and Discussion

The obtained results of the hybrid approach are tested by setting the input parameters of an ACO as given in Table 4. The parameter values are based on the literature, and are taken from the research of Ronit and Abhirup (2017).

Table 4. ACO implementation parameters.

Parameter	Values
nTrails	1
α	1
β	5
ρ	0.5
Q	500
antFactor	0.8
randomFactor	0.01
maxIteration	1000

The idea of the hybridization of ACO and IMWMTT was to further improve C_max by reducing the UAV’s flying time within each cluster of each trip formed by IMWMTT. When the total flying time of the UAV in each cluster is reduced, it reduces the total flying time of the overall trip, hence minimizing C_max. As the trips are constructed by IMWMTT, the set of sites a UAV visits in each cluster and each trip remains the same. Therefore, the total waste collected by the UAV does not change. As well as, the total number of trips remains the same. The improvement was obtained by rescheduling the order of nodes within each cluster using Algorithm 3 which planned a better route for the UAV in terms of total flying time.

Figure 2 shows C_max values obtained by MWMTT, IMWMTT, and hybrid IMWMTT + ACO for the three datasets, DS₁, DS₂, and DS₃. The figure illustrates a clear improvement of C_max for all datasets. The proposed hybrid approach of rescheduling the order of visiting the sites indicates the better formation of trips by minimizing the total flying time of the UAV. Based on the experimental results for the three datasets, DS₁, DS₂, and DS₃, the results obtained are as follows. The improvements in the values of C_max are in $[6.2\%,25.9\%]$ for DS₁, $[4.2\%,27.4\%]$ for DS₂, and $[6.6\%,27.2\%]$ for DS₃.

Figure 2. Results of MWMTT, IMWMTT, and hybrid (IMWMTT + ACO).

The average percentage error of the hybrid approach (Algorithm 4) of Phase-2 is found to be reduced for each of the three datasets. These average percentage error values after applying the hybrid approach are 29.9, 19.3, and 12.1% for DS₁, DS₂, and DS₃, respectively. Thus, are found to be reduced by 1.7, 2.6, and 3.5% for DS₁, DS₂, and DS₃, respectively, when compared with the percentage error values of Algorithm 1 of Phase-1.

Furthermore, the efficiency of the hybrid approach (Algorithm 4) can be supported by comparing the percentage error values of the obtained results with lower bound values given in Kaabi et al. (2022). The average percentage error of Algorithm 4 is found to be reduced for each of the three datasets. These average percentage error values after applying the hybrid approach are 29.9, 19.3, and 12.1% for DS₁, DS₂, and DS₃, respectively. Thus, are found to be reduced by 1.7, 2.6, and 3.5% for DS₁, DS₂, and DS₃, respectively, when compared with the percentage error values of IMWMTT. It is worth to note that the hybrid approach generates trips in less than 4 s for all tested instances.

6. Conclusion and recommendations

Due to the significant effect on the environment, and economy, as well as, on landscape development, optimization of waste collection management is of great importance. Thus, the growing need for support tools for efficient decision-making capabilities is encouraging researchers to propose models that form optimized routes. Using propelling drone technology or UAVs specifically for hazardous waste management aids the waste management organizations in several applications such as monitoring landfills, calculating airspace, and deterring littering. Also, UAVs can plan safe, efficient, and economical collection, transportation, treatment, and disposal of waste, while confirming the system to operate acceptably for different kinds of scenarios. In other words, UAVs are not just useful for waste management corporations, but also for the safety of the environment. With research conducted in perfecting drone flying and optimizing its routing plans can boost the potential of a drone, and achieve maximum productivity in minimum time, coupled with diminished operational hazards and expenses for waste management practices.

This research contributes to optimizing UAV routing plans by developing a two-phase hybrid approach called IMWMTT and ACO. A single UAV was used to visit several sites. As the UAV had a limited flying and waste capacities, multiple trips were formed and the UAV was treated or recharged in between trips. In Phase 1 (IMWMTT), trips are formed to collect the maximum of waste in each trip during the minimum total flying time. In Phase 2 (Hybrid IMWMTT and ACO), the trips formed using IMWMTT were rescheduled by eventually changing the order of visiting the sites in each cluster of each trip. The proposed approach was implemented and tested on three datasets. The experimental results proved the superiority of the proposed approach in all tested instances compared to what was found in the literature. In fact, the objective function C_max was reduced to up to 30%.

In this research, a single UAV was used for waste collection. Having multiple drones or heterogeneous drone types will improve the objective values as drones with different waste and flying capacities’ limitations will fly simultaneously. This work may also be extended by handling real-time requests from different sites, making real-time decisions, and rescheduling the trips. For the real-time problem, the approach must be efficient in terms of execution time, for frequent rescheduling. UAVs have unlocked their potential in the Waste Management industry and have proved to be the most economical, practical, efficient, and accurate equipment. The limitations or potential challenges of the proposed hybrid approach is that as the proposed approach uses drone technology real dataset is not easily available. This is due to the two main reasons which are privacy and legislative regulations. In the real-world waste management scenarios, the proposed approach helps in efficient route planning of the drone technology, which helps in the transportation aspects. Thus, more applications of this technology must be explored, researched, and tested to solve different real-life problems.

Disclosure statement

No potential conflict of interest was reported by the author(s).