Enhancing School Bus Routing through Multiple Real-world Data Integration
By Ruiqian Li, Linghan Mei, Mei Mei as part of course project of ECE1724H: Bio-inspired Algorithms for Smart Mobility. Dr. Alaa Khamis, University of Toronto, 2023.
Introduction
Efficient routing of school buses is a critical issue in urban planning that directly impacts the safety, punctuality, and overall health of students. The school bus routing problem (SBRP) is a logistical challenge that requires balancing multiple criteria, including minimizing travel time, ensuring safety, and optimizing operating costs. The motivation behind this project was the need to enhance the existing routing system by incorporating real-time traffic data, safety statistics related to crime rates, and roadway conditions (factors that are often overlooked in traditional models).
The challenge was to develop a routing system that not only found the shortest paths but also avoided areas with heavy traffic and high crime rates. The goal of this project was to create a more comprehensive and practical approach for the SBRP, one that aligns with the realities that school transportation services face daily. The goal was to ensure that the proposed routes were not only efficient in terms of distance and time but also safe and reliable, avoiding routes that could put students at risk or cause unnecessary delays.
To solve this problem, this article used the Ant Colony Optimization (ACO) algorithm and improved it with additional heuristic information. The algorithm simulates the behavior of ants searching for food to find the optimal path for a school bus. In our adaptation, the pheromone trajectories used by ants to communicate with each other are similar to school bus routes, which are improved iteratively to approach the optimal solution. The ACO algorithm was chosen because of its ability to provide high-quality solutions in a reasonable timeframe and its inherent adaptability to incorporate multiple heuristics.
Literature Review
In exploring the complexities of the school bus routing problem (SBRP), various methodologies have been employed to optimize routes while balancing economic and social objectives. A significant contribution in this field is the approach that models overbooking in school bus systems. Researchers have recognized that the probability of a student using the bus service can vary significantly, leading to the innovative use of chance-constrained programming to better utilize bus capacity while minimizing the risk of late arrivals [1]. This mathematical formulation responds to real-world district policies, where the likelihood of students riding the bus ranges from 22% to 77%, and effectively addresses the NP-hard nature of SBRP.
Furthermore, the field of routing is not limited to outdoor spaces but extends to indoor environments, each presenting unique challenges. The adaptation of routing algorithms to dynamically changing environments, especially in outdoor settings, involves considering traffic movements and jams. This research area has seen the development of bio-inspired algorithms, highlighting their applicability across various domains including operations research, management, transportation, and geographic information systems [2].
Lastly, the ant colony optimization (ACO) algorithm, a bio-inspired heuristic, has been effectively applied to the vehicle routing problem (VRP), an integral aspect of logistics and distribution. This study emphasizes the importance of optimizing control parameters such as the number of ants, and the relative importance of trail (alpha), visibility (beta), and pheromone decay (rho). Through meticulous experimentation, optimal settings for these parameters were identified, demonstrating the algorithm’s effectiveness in minimizing route costs and achieving high performance in VRP scenarios [3].
In integrating these insights with the extended ACO approach proposed in this review, which incorporates not only distance but also safety parameters like traffic dynamics, crime rates, and road quality, a more comprehensive solution to SBRP is achieved. This approach, while ensuring the shortest and safest path, aligns with the multifaceted nature of SBRP and reflects an advanced, adaptable solution suitable for the evolving urban landscapes and societal needs.
Problem Formulation and Modeling
Sets and Indices:
- I: Set of bus passes that include main roads and intersections, student houses, indexed by i.
- J: Set of roads connecting the bus stops, indexed by j.
- K: Set of buses, indexed by k.
Parameters:
- dij: Distance between bus passes i and j.
- tij: Average travel time between bus stops i and j considering the usual traffic.
- cij: Traffic condition factor for road j, higher values indicate worse traffic condition
- sij: Safety factor for road j, higher values indicating less safety (e.g., high crime rates).
- rij: Road quality factor for road j, with higher values indicating poorer road conditions.
- Ck: Capacity of bus k.
- Si: Number of students at bus stop i.
Objective Functions:
Maximize the overall safety of the route:
Minimize the overall route distance:
Subject to:
- Each student house is visited exactly once by the bus:
In this article, we use an upgraded Ant Colony Optimization (ACO) algorithm to find the optimal school bus routing solution for students’ homes. The nodes are composed of different passing points (homes, main roads, and intersections) and one drop-off point (Thorncliffe Park Public School). The ants will visit each node exactly once and deposit the amount of pheromone that is proportional to the inverse of the weights of heuristic information which includes the distance, traffic volume, crime rate, and road consideration of each path. In other words, if the ant traversed a long route, a heavy-traffic route, or a block involved in a high criminal rate, it will deposit less pheromone, which implies that there is less probability that the other ants will choose.
The updated heuristic information weights:
The pheromone can be updated as follows:
Decision-Making Process of Updated ACO
The probability of the ants choosing the path can be expressed by the formula below with the new updated pheromone and heuristic information stated above:
Finding the nodes and edges of the school and its surrounding area
Converting the map to a representation consisting only of nodes and edges has several advantages, especially from the point of view of computational analysis and simplification
After processing the code above, the map can be represented as follows:
Traffic Incident Map
The dataset of traffic incidents can reflect the traffic conditions around the school and it helps to find the optimal route.
Traffic Map Visualization by Heat Maps
A heat map is superimposed on a geographic map showing the concentration or frequency of traffic accidents at different locations.
Proposed Solution
Here is a map that contains students’ homes and some important points that the school bus will pass through such as intersections, and the highway of Don Valley Parkway. The reason I selected these points will be helpful to visualize how the algorithm works.
note: The red marker is the starting/end point Thorncliffe Park Public School
Here, we will use the home address of student 1 (Roanoke Apartment) as a reference point to help us understand how the heuristic information of “traffic_volume” in the algorithm works when considering finding the best path. Also, to better visualize the results, I will perform the algorithm on a network graph based on their real coordinates.
The traffic_volume includes all the heavy-traffic paths with a relatively high weight to discourage the route that contains these paths from being selected. Here, I contain the Don Valley Parkway(DVP) as one of the traffic_volume elements because the data shows this road is one of the most congested in the all-day segment, especially after 4:00 a.m. in the afternoon, which also happens to be the time when school buses need to take students home. Considering that this is a highway, school buses traveling at high speeds on a highway that is prone to traffic accidents also pose a risk to student safety.
The parts above influence the path selection process and it makes the ants less likely to choose the paths with heavy-traffic paths by setting eta to a relatively lower value.
This part above influences the pheromone update process. This part is important because the path (such as heavy traffic) with higher cost will receive fewer pheromones. Without this part, there would be no penalty in the cost function for paths with high cost so the pheromone update process would not be able to differentiate between paths with different levels of traffic paths.
In summary, we include the DVP as a path of traffic_volume and set it's a relatively high weight, which is high enough to discourage the algorithm from choosing this path when routing, and then make use of it to define the cost function and finalize the algorithm to compute the result.
Implementation of how traffic_volume affects the algorithm to select the path in an optimized way:
Here, again we only pick up some typical points based on their real coordinates for better to visulize, and we assume that the direct path between two adjacent nodes are a straight line to easier to implement.
Here it clearly shows that the school bus performs the ACO to find the best route starting from the school and picking/dropping student 4, then student 1, and finally student 3. The final route will get around or avoid going through the DVP path because it is predefined as a heavy-traffic path in the heuristic information of traffic_volume so the bus can save more time and reduce the risks from students being involved in the accident. However, it is being noticed that there is still going to be a chance that the DVP is selected in the next iteration, this could happen in a scenario such as if the alternative path is completely blocked due to endangered events or under construction, and the selection of DVP is still a good choice for bus’s routing.
Implementation of how crime_rate affects the algorithm to select path in an optimized way:
I first looked up the data that includes the Crime Data by Neighbourhood that reflects the crime rate per 100,000 population, and the counts are available for Assault, Auto Theft, Break and Enter, Robbery, Theft Over, Homicide and Shooting and firearm Discharges. [1] However, it is funny that almost the whole area of Toronto is highly concentrated with criminal rates and this dataset is not considered as helpful and typical data to help me to analyze.
Instead, I collected some data [2] of all shooting-related occurrences reported to the Toronto Police Service from the City of Toronto Open Data website as shown below and noticed that there were many shootings around Don Mills Road.
Therefore, it is necessary to assign a relatively high weight to heuristic information on criminal_rate to make the school bus choose a better path. As can be seen below the bus detours the high-crime rate road and makes a detour to continue the path.
Implementation of how road conditions affect the algorithm to select paths in an optimized way:
The implementation of road conditions, particularly those impacted by construction activities, plays a critical role in the optimization of path selection within routing algorithms. Utilizing the infrastructure viewer of Toronto City, we were able to identify roads near schools that are currently under construction.
To integrate this real-world data into the ACO algorithm, we assigned heavier weights to the roads affected by construction. This weight increase is designed to reflect the decreased desirability of these routes due to factors such as increased travel time, potential delays, and reduced safety. The higher weight acts as a deterrent, guiding the algorithm to prefer paths with smoother traffic flow and fewer disruptions, thus optimizing the route selection process.
In conclusion, by factoring in the ongoing construction activities near schools and other critical areas, the enhanced ACO algorithm can make more informed decisions, leading to optimized route selection that mitigates the impact of road disruptions and aligns with the project objectives of reducing travel time and improving route reliability.
Performance Evaluation
Test if the ACO is converged
To visualize the convergence of our Ant Colony Optimization (ACO) algorithm, plot the best route cost found in each iteration against the number of iterations.
The cost decreases rapidly in the initial iterations and then slows down, it indicates that the algorithm is quickly finding better solutions at the start. This is common in optimization algorithms where initial improvements are more significant.
Plot the run times of your Ant Colony Optimization (ACO) algorithm for different colony sizes (20, 40, 60, 80)
The run time does not increase linearly with colony size, suggesting that the computational complexity is not strictly proportional to the number of ants. It decreases with an increase in colony size before increasing again, it indicates that there is a sweet spot where the algorithm performs optimally in terms of speed. The non-monotonic relationship between colony size and run time suggests that the problem may not scale as expected with the number of ants, and other factors might be influencing the run time.
The run time first decreases and then increases as beta values rise, this suggests a non-monotonic relationship. It means that there is an optimal range of beta values that balance the heuristic importance with computational efficiency. The lowest point on the plot indicates the beta value that resulted in the fastest run time. This value might be considered optimal in terms of computational speed for the given settings and problem instance.
Adaptation
The implementation of an adaptive Ant Colony Optimization (ACO) algorithm aims to dynamically adjust its operational parameters in response to the evolving performance of the solution space. This approach is particularly effective in environments where conditions can change unpredictably, such as urban traffic management. By allowing the algorithm to modify its behavior during the optimization process, we ensure that it remains robust and efficient under a wide range of scenarios.
Key Adaptations:
- The core idea behind the adaptive ACO is the dynamic tuning of parameters. In our case, we have identified that a beta value of 1.5 and a colony size of 40 yield optimal results. However, these parameters may not always be ideal under different conditions or problem instances.
- Our adaptive algorithm incorporates a feedback loop that monitors the convergence behavior after each iteration. By evaluating the quality of the routes discovered, the algorithm can decide whether to adjust its exploration (alpha) and exploitation (beta) parameters, as well as the evaporation rate and the number of ants (colony size).
- To inform the adaptation process, we established performance metrics such as solution quality (route cost), solution stability (variance in route cost), and convergence speed (number of iterations to reach a stable solution).
The study of adaptation within the ACO algorithm involved running multiple experiments with varying environmental conditions, such as different traffic patterns and road closures due to construction.
- The adaptive ACO demonstrated an ability to quickly respond to changes in road conditions by rerouting to avoid areas with heavy traffic or construction.
- Our experiments revealed that the algorithm’s performance is sensitive to the beta parameter, which balances the heuristic desirability of a route against the accumulated pheromone trail. The adaptability of the beta parameter allowed the algorithm to maintain a balance between exploring new routes and exploiting known good routes.
- The study also showed that while a colony size of 40 was effective for most scenarios, there were instances where increasing or decreasing the number of ants led to better solutions, especially when dealing with more complex road networks.
Conclusions & Recommendations
This project successfully implemented an enhanced Ant Colony Optimization (ACO) algorithm to address the complex School Bus Routing Problem (SBRP). The key achievements include: By incorporating factors such as real-time traffic data, crime rates, and road conditions, the project provided a more realistic and comprehensive solution than traditional models. The adapted ACO algorithm effectively simulated the foraging behavior of ants, applying this biological model to optimize school bus routes. This approach proved efficient in balancing the multifaceted aspects of SBRP, like safety, punctuality, and cost. The algorithm’s ability to avoid routes with heavy traffic, high crime rates, and poor road conditions enhanced the safety and punctuality of school bus routes.
During the project, we faced several challenges:
- Data Complexity: Integrating diverse datasets (traffic, crime, road quality) was challenging due to varying formats and scales.
- Algorithm Calibration: Balancing the weight of heuristic information in the ACO algorithm required fine-tuning to avoid biased path selection.
- Computational Limitations: Managing the computational load, especially when scaling the model for larger networks, was a significant challenge.
The results indicated:
- Effective Route Optimization: The algorithm successfully identified routes that minimized travel time while maximizing safety.
- Dynamic Adaptability: The system demonstrated a robust response to changing traffic conditions and urban dynamics.
- Balanced Heuristics: The integration of different parameters (safety, traffic, road conditions) was well-balanced, leading to practical route choices.
To refine the proposed solution and extend its applicability, we recommend incorporating more granular data, like weather conditions and special event schedules, to further improve routing accuracy. Continue to refine the algorithm, particularly in balancing heuristic weights and improving computational efficiency for large-scale applications. Furthermore, testing and adapting the model to various urban settings would significantly broaden its applicability and effectiveness. Integrating machine learning techniques could also be a transformative step. By predicting traffic patterns and potential safety hazards, the system can plan routes more proactively, enhancing safety and efficiency.
Exploratory Spatial Data Analysis
Implementation with real-world data
References
[1] “School Bus Routing with Stochastic Demand and Duration Constraints,” Hernan Caceres , Rajan Batta, Qing He, 27 Apr 2017. https://pubsonline.informs.org/doi/abs/10.1287/trsc.2016.0721
[2] “A Review of Routing Algorithms for Intelligent Route Planning and Path Optimization in Road Navigation”, Noopur Tyagi, Jaiteg Singh & Saravjeet Singh, 06 October 2022, https://link.springer.com/chapter/10.1007/978-981-19-4606-6_78
[3] “Solving Vehicle Routing Problem using Ant Colony Optimisation (ACO) Algorithm”, Wan Amir Fuad Wajdi Othman, Aeizaal Azman Abd Wahab Syed Sahal Nazli Alhady, Haw Ngie Wong, November 2018, https://www.researchgate.net/publication/328743319_Solving_Vehicle_Routing_Problem_using_Ant_Colony_Optimisation_ACO_Algorithm
[4] Toronto Police Services, “About Neighbourhood Crime Rates,” City of Toronto Open Data, Apr. 4, 2023. https://open.toronto.ca/dataset/shootings-firearm-discharges/
[5] Toronto Police Services, “About Shootings & Firearm Discharges,” City of Toronto Open Data, Nov. 21, 2023. https://open.toronto.ca/dataset/shootings-firearm-discharges/
[6] Alaa Khamis. Optimization Algorithms: AI techniques for design, planning, and control problems. Manning Publications, ISBN 9781633438835, 2023. GitHub, https://github.com/Optimization-Algorithms-Book/Code-Listings (accessed Dec. 17, 2023).
