Districting and Routing Problem in Waste Collection

By Ho Wan Luo, Yikan Liu, Sheng Zhao as part of course project of ECE1724H: Bio-inspired Algorithms for Smart Mobility. Dr. Alaa Khamis, University of Toronto, 2023.

Abstract

Addressing the challenge of effective waste management in Toronto’s densely populated urban areas, our study introduces an innovative data-driven approach to optimize garbage collection. By analyzing a comprehensive dataset including garbage bin locations and historical waste generation patterns, high-density bin areas were identified using Chloropleth mapping and segmented through X-Means clustering. The project further involved a comparative analysis of several advanced optimization algorithms, such as Simulated Annealing, Genetic Algorithms, Particle Swarm Optimization, Ant Colony Optimization, and Self-Organizing Maps. These algorithms were evaluated based on their efficacy in reducing travel times and adapting to dynamic waste generation patterns. The outcome is a scalable and adaptable waste management model that enhances operational efficiency and urban cleanliness, with potential applicability in other urban contexts.

Introduction

Effective waste management is a critical challenge in Toronto, particularly in densely populated and commercially active areas. The frequent overflow of garbage bins not only detracts from the city’s aesthetics but also poses environmental and health hazards [1]. The current system, based on fixed schedules, struggles to adapt to the variable waste generation patterns, especially during peak periods like public holidays and events [2].

Addressing the challenges posed by the numerous bins throughout the city, our project aims to optimize their servicing. We plan to use data-driven algorithms to enhance the allocation and collection strategies, thereby making the waste management process more responsive and efficient. This approach is designed to align better with the dynamic waste generation patterns, improving both the environmental and aesthetic quality of Toronto’s urban environment.

Our project’s core involves identifying the most efficient garbage truck routes in a selected busy area of Toronto, using a comprehensive dataset including the geographical locations of garbage bins and historical waste generation patterns. We will dynamically segment the garbage service area using a Chloropleth Map to highlight high-density bin areas. In these areas, the X-Means clustering algorithm will be employed to divide the district into regions for more efficient route planning.

Further, we will conduct a comparative analysis of advanced optimization algorithms, including Simulated Annealing (SA), Genetic Algorithms (GA), Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), and Self-Organizing Map (SOM) approaches. This analysis aims to determine the most effective strategy to enhance Toronto’s waste collection routes, focusing on minimizing travel times and adapting to changing waste patterns.

Ultimately, this project seeks to improve waste collection efficiency in Toronto, contributing to a cleaner, healthier urban environment. It aims to develop a scalable model for waste management that can be adapted to other urban areas, setting a precedent for using data science and optimization algorithms in urban infrastructure challenges.

Literature Review

The optimization of urban waste management is a well-documented challenge that has traditionally been approached with operations research methods like the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP)[1][2]. These methods, while foundational, often lack the flexibility required for the dynamic and unpredictable patterns of waste generation in cities like Toronto[3].

Modern research has shifted towards adaptive bio-inspired algorithms, such as Genetic Algorithms (GA), Ant Colony Optimization (ACO), and Particle Swarm Optimization (PSO), due to their ability to find efficient solutions in complex, non-linear search spaces. These methods are increasingly favored for their computational efficiency and robustness in urban environments.

Our project extends this body of work by utilizing a suite of bio-inspired algorithms, including the novel incorporation of Self-Organizing Maps (SOM) for preliminary data clustering. This enhances route optimization by reducing the computational complexity faced by subsequent algorithms. Furthermore, our solution emphasizes adaptability and scalability, ensuring that the system can adjust to changing waste generation patterns and be applied to other urban contexts.

In essence, our approach marries the flexibility of modern algorithms with the practical needs of Toronto’s waste management, offering a scalable model that can be adapted to other cities. This alignment with and divergence from existing literature showcases the project’s contribution to innovative urban sustainability solutions.

Data Acquisition and Initial Analysis

Our first step involves acquiring a comprehensive dataset on litter receptacles from the City of Toronto, which includes detailed information such as the geometry, area ID, and address of each bin (https://open.toronto.ca/dataset/street-furniture-litter-receptacle/) [4]. We plot this data on a graph to visualize the distribution of bins across the city. This spatial analysis is crucial for understanding the scope of our challenge.

To further refine our focus, we will access data on waste curbside collection areas of Toronto (https://open.toronto.ca/dataset/solid-waste-daytime-curbside-collection-areas/) [5]. Combining this with the litter receptacle data, we will employ a Chloropleth Map to identify districts with the highest concentration of bins.

Since the quantity of bins in the city of Toronto is massive, it’s essential to prioritize and address the challenges and opportunities in the regions with the highest bin counts. In our project, we will focus on these areas, as they tend to have unique obstacles that can impact the efficiency of the waste collection process. These high-density areas are often commercial or popular tourist destinations[6], where timely and proper waste disposal is crucial to maintaining the city’s cleanliness. By concentrating our efforts on these specific regions, we aim to develop targeted solutions that can significantly improve the overall waste management system in Toronto.

Problem Formulation and Modeling

Algorithmic Approach and Implementation

Building on this data-driven foundation, our project will delve into the implementation of various algorithms to optimize waste collection routes:

X-Means Clustering:

We will apply the X-Means clustering algorithm to the identified high-density areas to segment the city into distinct regions based on bin density and waste generation patterns. This step is vital for breaking down the large-scale problem into manageable segments, facilitating more focused route optimization.

Algorithm Model of X-Means Clustering for Toronto’s Waste Management:

1. Given a dataset X = {x1, x2, . . . , xn}, representing the locations of garbage bins in Toronto, and an initial range for the number of clusters, representing potential waste collection zones, [Kmin, Kmax].
2. Initialize K centroids, representing potential central points for waste collection zones, and partition X into K clusters by assigning each bin location xi to the nearest centroid, forming preliminary waste collection zones.
3. Recalculate the centroid of each zone for better representation to minimize the within-cluster sum of squares (WCSS), indicating the compactness of bins within each waste collection zone. The WCSS for a given number of clusters K is defined as:

where μ_k is the centroid of cluster C_k.

1. Evaluate potential splits of each zone into two, aiming for more precise waste collection areas. For each split, calculate the Bayesian Information Criterion (BIC) value to assess its validity:

1. Maximize the BIC to find the optimal number of clusters, and accept splits that improve BIC, refining the waste collection zones and balancing model simplicity and fit.
2. Iterate steps 2–6 until the most effective distribution of zones (clusters) is achieved.

Decision Variables and Predefined Parameters:

Given a set of garbage bin locations, the task is to find the most efficient route for multiple garbage trucks to visit each location exactly once and then return to the starting point, such that the total distance traveled is minimized. The number of trucks is determined by applying X-means clustering to the garbage bin locations, effectively reducing the number of locations to visit. Different TSP algorithms are used to evaluate the cost of visiting all cluster centers.

Decision Variables:

• x[i][j][k]: Binary variables that are equal to 1 if truck k goes from location i to location j, and 0 otherwise.

Predefined Parameters:

• d[i][j]: The distance from location i to location j.
• N: The total number of locations.
• K: The total number of trucks (determined by X-means clustering).
• V: The set of all locations plus a depot where the route starts and ends.
• C: The maximum capacity of a truck.
• q[i]: The amount of waste at location i.

Objective Function:

The objective is to minimize the total distance traveled. This can be represented mathematically as:

Constraints:

• Hard Constraints:

1. Each location is visited exactly once:

1. If a location is visited by a truck, the truck leaves it:

1. The total amount of waste collected by a truck does not exceed its capacity:

• Soft Constraints

1. Balanced Workload: While not strictly necessary, you might want to balance the workload among the trucks. This could mean balancing the total distance each truck travels, the total amount of waste each truck collects, or the total time each truck spends on the route.
2. Preferred Routes: There might be certain routes that, while not the shortest, are preferred due to less traffic, better road conditions, or other factors.

Soft constraints: soft constraints are not strictly enforced. If a solution violates a soft constraint, it doesn’t become infeasible. Instead, the quality of the solution is lower. In your objective function, you exclude terms to simplify the problem.

Proposed Solution

After applying X-means clustering, we have a reduced set of locations (cluster centers) and simplified the city’s complex geographic layout into manageable segments. With respect to the constraints, we can then employ a variety of bio-inspired algorithms to enhance the waste collection in Toronto’s urban landscape. These algorithms are renowned for their ability to solve complex optimization problems through mechanisms that emulate natural processes and behaviors. The selected algorithms for this project are as follows:

Simulated Annealing (SA):

This algorithm is inspired by the annealing process in metallurgy. It is particularly useful for finding global optima in a large search space and is adept at avoiding local minima, making it suitable for optimizing waste collection routes that may have many local optima due to the city’s complex geography.

Algorithm Model of Simulated Annealing (SA):

• Let a route be represented as a sequence of bins:

• The total distance D(R) of a route R is given by:

where d(bi, bi+1) is the distance between consecutive bins.

• Generate a new route R′ by a slight modification of R (e.g., swapping two bins).
• If D(R′) < D(R), accept R′ as the new route.
• If D(R′) ≥ D(R), accept R′ with probability

• Decrease T gradually according to a cooling schedule.
• Repeat until convergence or a maximum number of iterations is reached.

Algorithmic Analysis and Adaptation/Tuning:

We initialized the SA with a ‘mutate’ generation method for minor route adjustments and a ‘random’ method for diverse starting solutions.

The SA parameters were carefully selected for effective search balance: max_iter=1200 to provide ample iterations for comprehensive solution exploration, max_iter_per_temp=500 for detailed analysis at each cooling stage, initial_temp=150 to encourage extensive early exploration, and final_temp=0.01 for focused solution refinement at later stages. A linear cooling schedule was employed for gradual temperature decrease.

These parameters greatly influenced the SA’s efficacy, ensuring a thorough initial exploration of potential routes and subsequent focused optimization, leading to the identification of efficient waste collection paths. The result was a high-quality solution to the TSP instances tested, demonstrating the effectiveness of the tuning process in the SA method for TSP.

Genetic Algorithms (GA):

GA is based on the principles of natural selection and genetics. It is robust in exploring and exploiting the search space and can efficiently handle the multi-objective nature of the waste collection problem, such as minimizing the distance traveled while maximizing the amount of waste collected.

Algorithm Model of Genetic Algorithm (GA):

• A route is encoded as a chromosome: C = (b1, b2, . . . , bn).
• The fitness of a chromosome C is inversely proportional to its total distance.
• Select parents based on fitness and generate offspring via crossover and mutation.
• Offspring routes are evaluated and the fittest routes are retained.
• Iteratively apply selection, crossover, and mutation over generations.
• Convergence is achieved when there is no significant improvement in fitness.

Algorithmic Analysis and Adaptation/Tuning:

We initiated our GA with a carefully chosen population size of 20, using PermutationRandomSampling() for diverse route permutations. Our GA primarily focused on InversionMutation() for mutating routes and OrderCrossover() for combining them, ensuring logical route structures while introducing necessary variations.

To guarantee valid solutions, we incorporated the StartFromZeroRepair() function, ensuring each collection point is visited once without repetition. We also routinely removed duplicate routes to maintain genetic diversity within the population.

Our GA used DefaultSingleObjectiveTermination() as a termination criterion, halting the algorithm after 300 generations without improvement to optimize computational efficiency. The GA’s performance was evaluated based on process time. The adaptive approach and parameter tuning enabled the GA to effectively generate high-quality solutions for the TSP within a practical time frame.

Particle Swarm Optimization (PSO):

Drawing inspiration from social behavior patterns in birds and fish, PSO is used for continuous optimization problems. It can quickly converge to optimal or near-optimal solutions by sharing information among individual solutions, which is beneficial when routes need to be adjusted dynamically in response to fluctuating waste levels.

Algorithm Model of Particle Swarm Optimization (PSO):

• Each particle i has a position (route) Pi and velocity Vi.
• Update Vi based on the particle’s best-known position and the swarm’s best-known position.
• Position update rule:

• The fitness of each particle is the inverse of the route distance.
• Iterate until the optimal route is found or a maximum iteration count is reached.

Algorithmic Analysis and Adaptation/Tuning:

We initialized the algorithm with 50 particles, with each particle representing a potential solution for our route optimization problem. The number of dimensions for the problem was set equal to the number of regions identified in Toronto.

Key parameters of the PSO were fine-tuned for optimal balance: inertia weight (w) at 0.79, personal learning coefficient (c1) at 2.05, global learning coefficient (c2) at 1.5, with 10 nearest neighbors (k), and a norm exponent (p) of 2. These settings critically influenced the particles’ exploratory and exploitative behaviors.

The PSO was executed for 250 iterations, balancing thorough exploration against computational efficiency. This iteration count ensured to converge on effective solutions without overextending runtime. We monitored process time to assess efficiency and used route visualization for evaluating solution quality.

Ant Colony Optimization (ACO):

Mimicking the way ants find the shortest path to food sources, ACO is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. This characteristic is well-suited for finding optimal paths in waste collection, where each bin location can be seen as a graph node.

Algorithm Model of Ant Colony Optimization (ACO):

• Represent waste collection points as nodes in a graph.
• Ants traverse the graph, choosing paths probabilistically based on pheromone levels.
• Pheromone update rule:

where τij is the pheromone on the path from node i to j, and ρ is the evaporation rate.

• ∆τij is the amount of pheromone deposited, typically inversely proportional to the route length.
• Iterate the process, allowing ants to find increasingly shorter routes.

Algorithmic Analysis and Adaptation/Tuning:

We initialized ACO with key parameters, notably setting the evaporation rate at 0.5 and the pheromone quantity (Q) deposited by ants at 100. These settings play a critical role in dictating the ants’ behavior within the algorithm, striking a crucial balance between exploring new routes (exploration) and strengthening existing efficient routes (exploitation).

To ensure the ACO algorithm performs optimally without overextending computational resources, we limited its run to 100 iterations. This duration was deemed sufficient for the artificial ants to effectively search for and refine optimal routes, while also keeping the algorithm’s execution time practical.

We evaluated the ACO’s performance through two primary metrics: processing time and the quality of the routes visualized. The processing time gave us an insight into the efficiency of the algorithm, while the visualization of the generated paths allowed us to assess their practical applicability for waste collection. The results obtained from these parameters were encouraging, demonstrating that our configuration of the ACO algorithm could yield reasonable and effective solutions for the Traveling Salesman Problem (TSP) — a direct analog to optimizing waste collection paths in a city setting.

These outcomes underscore the potential of ACO in urban planning applications, particularly in tasks requiring the optimization of complex logistical routes within a constrained environment.

Self-Organizing Map (SOM):

SOM is an unsupervised learning algorithm that projects high-dimensional data into a lower-dimensional (typically two-dimensional) space. It organizes data points so that similar points are located close to one another on the map, aiding in the clustering of bins and thus optimizing collection routes.

Algorithm Model of Self-Organizing Map (SOM):

• Consider a dataset X = {x1, x2, . . . , xn}, where each xi represents the geographic coordinates of a waste bin.
• Initialize a two-dimensional grid of nodes, each node nij having a weight vector wij of the same dimension as the input vectors in X.
• For each input vector xi, find the node with the closest weight vector (the Best Matching Unit, BMU).
• Update the weight vectors of the BMU and its neighbors to be more like the input vector, according to:

where θ(i, j, BM U ) is a neighborhood function centered on the BMU, and α is the learning rate.

• Iteratively present all input vectors, updating the map over time.

Algorithmic Analysis and Adaptation/Tuning:

The SOM was initialized with a grid of size ‘1xN_neurons’, where ‘N_neurons’ is twice the number of regions. Each neuron was associated with a weight vector of the same dimension as the input data. The neurons were initialized with random weights using the ‘random_weights_init’ function.

The SOM algorithm was run for a range of iterations from 5 to 60, incrementing by 5 at each step. In each iteration, the SOM was trained on the points representing the cities. The training process involved updating the weights of the neurons based on the input data.

After each training iteration, a scatter plot of the cities was created, and the path determined by the SOM was plotted.The performance of the SOM algorithm depends heavily on the choice of the initial parameters such as the number of neurons, the number of iterations, and the learning rate. These parameters were tuned to achieve a balance between exploration and exploitation.

Performance Evaluation

X-Means Clustering Result:

In our urban waste management optimization project for Toronto, we have applied the X-Means clustering algorithm to effectively segment the city’s vast landscape into more manageable waste collection zones. This sophisticated data-driven approach was employed to analyze the geographical locations of garbage bins across the city, considering the intricacies of urban waste generation patterns. By utilizing X-Means, we were able to intelligently cluster these locations, which resulted in the identification of 12 distinct points. These 12 points, representing critical nodes in our urban waste management network, then formed the basis for implementing the Traveling Salesman Problem (TSP) algorithm.

TSP Algorithm Result:

We established a set of evaluation metrics to evaluate bio-inspired algorithms in optimizing waste collection routes in Toronto. These metrics included the quality of the solution (measured as route length or cost) and the computational time taken by each algorithm. The algorithms tested were Simulated Annealing (SA), Genetic Algorithms (GA), Particle Swarm Optimization (PSO), Self-Organizing Map (SOM), and Ant Colony Optimization (ACO).

Simulated Annealing (SA):

Route Length: 17.086

Time Spent: 14.90 seconds

Route: [0, 6, 4, 8, 10, 11, 2, 1, 3, 9, 5, 7]

Pros: Managed to find a relatively short route.

Cons: Took the longest time to compute among all algorithms.

Fit with Objectives: Effective in finding a good solution, albeit slower.

Genetic Algorithms (GA):

Route Length: 17.086

Time Spent: 2.05 seconds

Route: [1, 8, 6, 10, 4, 2, 3, 12, 11, 9, 5, 7]

Pros: Achieved a good balance between route length and computational time.

Cons: Requires fine-tuning of parameters like mutation and crossover rates.

Fit with Objectives: Efficient in optimizing routes with moderate computation time.

Particle Swarm Optimization (PSO):

Route Length: 21.701

Time Spent: 0.77 seconds

Route: [1, 7, 9, 10, 11, 12, 2, 3, 4, 5, 6, 8]

Pros: Fastest in terms of computation time.

Cons: The route length was not as optimized as other algorithms.

Fit with Objectives: Highly efficient in terms of time, but less effective in route optimization.

Ant Colony Optimization (ACO):

Route Length: 18.837

Time Spent: 1.29 seconds

Route: [1, 10, 5, 6, 8, 7, 9, 11, 2, 3, 12, 4]

Pros: Good balance between route length and time.

Cons: Can be sensitive to parameter settings like pheromone evaporation rate.

Fit with Objectives: Demonstrated a good compromise between solution quality and computation time.

Self-Organizing Map (SOM):

Route Length: 20.488

Time Spent: 0.0014 seconds

Route: [1, 7, 8, 6, 5, 10, 4, 9, 2, 11, 3, 12 ]

Pros: Extremely fast computation.

Cons: Route optimization is not as effective.

Fit with Objectives: Very efficient in terms of computational speed, suitable for quick, approximate solutions.

Performance Summary:

Each algorithm has its strengths and weaknesses, and the choice depends on the priority of the objectives — whether it is the quality of the solution or the computational efficiency. For instance, GA and ACO provide a balanced solution, while PSO and SOM are more efficient in terms of computational time. SA, while slower, offers a high-quality solution. The selection of the algorithm should be based on the specific requirements and constraints of the waste management system in Toronto.

Conclusions & Recommendations

Our extensive study on optimizing waste collection routes in Toronto’s urban environment, through the application of various bio-inspired algorithms, has yielded insightful results. Each algorithm — Simulated Annealing (SA), Genetic Algorithms (GA), Particle Swarm Optimization (PSO), Self-Organizing Map (SOM), and Ant Colony Optimization (ACO) — demonstrated unique strengths and limitations when applied to the task of route optimization.

The Genetic Algorithm (GA) and Ant Colony Optimization (ACO) algorithms emerged as balanced choices, effectively optimizing route lengths while maintaining moderate computational times. The Particle Swarm Optimization (PSO) and Self-Organizing Map (SOM) excelled in computational efficiency, making them suitable for scenarios where rapid route planning is paramount. Simulated Annealing (SA), although slower, distinguished itself by finding routes of superior quality.

Based on our findings, we recommend a strategic and flexible approach to selecting and implementing optimization algorithms for waste collection in Toronto. For scenarios prioritizing route quality, Simulated Annealing (SA) should be considered, while Particle Swarm Optimization (PSO) and Self-Organizing Map (SOM) are better suited for situations demanding rapid decision-making. Genetic Algorithms (GA) and Ant Colony Optimization (ACO) offer a balanced solution and are recommended for regular operational contexts. We also suggest exploring hybrid models that combine the strengths of these algorithms to enhance efficiency. Continued experimentation with parameter settings, particularly for GA and ACO, could further optimize performance. Collaborations with local authorities are essential to integrate these advanced solutions into existing waste management systems, ensuring they align with both operational needs and community expectations. This focused approach aims to not only improve the operational efficiency of Toronto’s waste management but also contribute to its overarching urban sustainability goals.

Google Colaboratory

Citation:

[1] Zhu, Jinxin, and Gordon Huang. “Contract-out planning of Solid Waste Management System under uncertainty: Case study on Toronto, Ontario, Canada.” Journal of Cleaner Production, vol. 168, 2017, pp. 1370–1380, https://doi.org/10.1016/j.jclepro.2017.09.084.

[2] Best, B. J. (2006). Cognitive Approaches to the Traveling Salesperson Problem: Perceptual Complexity that Produces Computational Simplicity. In AAAI Spring Symposium: Between a Rock and a Hard Place: Cognitive Science Principles Meet AI-Hard Problems (pp. 11–16).

[3] Chang, N.-B., Pires, A., & Martinho, G. (2011). Empowering Systems Analysis for Solid Waste Management: Challenges, trends, and perspectives. Critical Reviews in Environmental Science and Technology, 41(16), 1449–1530. https://doi.org/10.1080/10643381003608326

[4] Transportation Services. (2023, June 1). Open data dataset. City of Toronto Open Data Portal. https://open.toronto.ca/dataset/street-furniture-litter-receptacle/

[5] Solid Waste Management Services. (2019). Open data dataset. City of Toronto Open Data Portal. https://open.toronto.ca/dataset/solid-waste-daytime-curbside-collection-areas/

[6] Lu, J.-W., Chang, N.-B., & Liao, L. (2013). Environmental informatics for solid and hazardous waste management: Advances, challenges, and perspectives. Critical Reviews in Environmental Science and Technology, 43(15), 1557–1656. https://doi.org/10.1080/10643389.2012.671097