Accessibility Score of Healthcare Facilities in Toronto
By Yang Chen, Liangjing Xie and Qi Zhang as part of course project of ECE1724H: Bio-inspired Algorithms for Smart Mobility. Dr. Alaa Khamis, University of Toronto, 2023.
Problem Characterization
- Accessibility
Accessibility analysis has been widely applied to examine the spatial layout of essential urban public service facilities, including parks, medical service centers, shopping complexes, schools, and others [1–4]. Among them, medical service facilities, as a critical component of public service infrastructure, significantly affect residents’ access to hospitals through their spatial distribution and accessibility. This in turn has a profound impact on the quality of daily life for residents. Lower spatial accessibility to medical service facilities can increase the time and financial costs of seeking medical care, especially for low-income groups. This not only intensifies their financial burden but also may reduce the frequency of their medical visits, negatively impacting their overall health.
Therefore, our project, focusing on the coordinates of 20 buildings in downtown Toronto, analyzes the spatial patterns of accessibility to urban medical service facilities, based on the distribution of medical facilities in the target area.
2. Routing
In terms of routing, we have employed distinct strategies for the planning of vehicle travel routes and pedestrian walking paths.
Urban vehicle driving routes are more sensitive to road conditions. For vehicle routes, we used bio-inspired algorithms (including Simulated Annealing and Firefly Algorithms), taking into account real-time road traffic accidents, historical road traffic volume, and the number of intersections along the path, modeling the routing problem as a multi-objective optimization problem.
Pedestrian actual walking paths are less affected by road traffic conditions. For pedestrian routes, we used the shortest path algorithm (Dijkstra’s algorithm) to calculate the actual transit paths used for computing accessibility scores.
3. Travel Time
In the context of travel time computation, our approach involves employing a multi-objective routing strategy for vehicle trajectories. Under the constraints of optimization, the average travel speed of vehicles along the derived path exhibits stability. Given the relatively compact nature of the study area, a specific numerical value can effectively represent the average travel speed of vehicles throughout the entire trajectory. Consequently, this allows for the calculation of the travel time for vehicles along the specified path.
Conversely, the determination of pedestrian walking routes relies on the shortest path algorithm. The practical walking speeds of pedestrians may vary significantly across different segments of the route, rendering it impractical to represent the overall pedestrian walking speed with a single constant value. To address this variability, we leverage historical pedestrian flow data to establish real-time walking speeds for pedestrians on each segment of the path. This dynamic approach enables the accurate calculation of pedestrian travel time along the entire route.
4. Scoring
In the scoring process, we conducted an analysis focusing on three types of medical facilities: hospitals, life labs, and pharmacies. Taking into consideration the importance of these facilities in residents’ daily healthcare processes and the quantity of medical facilities within the region, we assigned reasonable weights to the three types of medical facilities. Specifically, hospitals were given a weight of 0.6, life labs a weight of 0.3, and pharmacies a weight of 0.1.
We determined the accessibility of each building by calculating the weighted average travel time from that building to the surrounding target medical facilities. Normalizing the scores for each of the 20 buildings, we obtained a numerical value ranging from 1 to 100 as the accessibility score for each building in our study.
5. Project Objectives
Our overarching goals are twofold:
(1) To furnish Toronto residents with valuable insights into the ease of accessing healthcare facilities from their respective living areas, enabling them to make informed decisions about their healthcare options.
(2) To provide essential guidance to the Toronto City Council by pinpointing the buildings in greatest need of additional healthcare facilities. This information will aid the council in making informed decisions to enhance healthcare access and equity throughout the city.
Literature Review
- Accessibility
In the research on the accessibility of medical service facilities, the two-step floating catchment area (2SFCA) method, gravity model approach, and minimum travel cost method are commonly used approaches [5].
The fundamental concept of the two-step floating catchment area (2SFCA) method [6] involves two separate steps in which you center your search around both the supply points and demand points to calculate the accessibility of each service facility. The gravity model approach [2] is a method used for accessibility analysis, and its fundamental concept is derived from Newton’s law of gravity. This method posits that within a city, the ‘potential attractiveness’ of service facilities to residents is directly proportional to the size of these facilities and inversely proportional to the distance from residents. The minimum travel cost method [7] is an approach used in accessibility analysis that subdivides the study area into n×m grid cells. This method calculates the accessibility of service facilities by setting different travel costs for various roads or paths to measure the total distance or average distance between the grid cells and surrounding facilities.
In the context of the various research methods discussed, both the two-step floating catchment area method and the gravity model approach often rely on population data within residential units as their statistical units. However, in densely populated and highly dynamic urban areas such as Toronto, obtaining stable and accurate population data can be a significant challenge, making it difficult to analyze the accessibility of various residential areas effectively. On the other hand, the minimum travel cost method involves dividing the study area into grids, which can lead to an artificial separation of road networks and neighborhoods. This approach may not accurately reflect the true accessibility of different communities.
To address these challenges, our project opted to focus on 20 specific buildings within the target research area, as opposed to utilizing residential units or grid-based divisions. These selected buildings are evenly distributed across the entire map area, align with the actual road network, and correspond to the practical mobility needs of individuals. This approach provides a more realistic and detailed analysis of accessibility.
2. Shortest Path Algorithm
Dijkstra’s algorithm is applicable to both directed and undirected graphs, assuming that all edge weights are non-negative. In contrast to Dijkstra’s algorithm, the Bellman-Ford algorithm can handle graphs with negative-weight edges. It can also detect the presence of negative-weight cycles in the graph. However, its time complexity is relatively high (O(VE), where V is the number of vertices and E is the number of edges). The Floyd-Warshall algorithm is a dynamic programming approach used to find the shortest paths between all pairs of vertices. Its time complexity is O(V³), making it suitable for dense graphs. Unlike Dijkstra’s algorithm, the Floyd-Warshall algorithm can handle multiple source points simultaneously but is less efficient for a single source point. The A* algorithm is a heuristic algorithm commonly used for graph search and path planning. A* builds upon Dijkstra’s algorithm by incorporating an estimate of the target vertex to expedite the search. It is suitable for scenarios where estimating the target cost is necessary.
When seeking the shortest path between two points within the downtown area of Toronto, Dijkstra’s algorithm is a reasonable choice for several reasons. Firstly, in the road network of the Toronto downtown area, path weights (such as distance or time) are likely to be non-negative, aligning with the fundamental assumption of Dijkstra’s algorithm. Secondly, for large sparse graphs without negative-weight edges, such as road networks, Dijkstra’s algorithm (especially when optimized with a priority queue) is generally more efficient than the Bellman-Ford algorithm. Additionally, when finding the shortest path between two specific points, Dijkstra’s algorithm is more efficient than the Floyd-Warshall algorithm, which is designed for calculating the shortest paths between all pairs of vertices. Lastly, Dijkstra’s algorithm is relatively straightforward and easy to understand, making it widely popular in practical applications.
3. Bio-inspired Algorithm
In addressing the vehicle routing problem in the downtown area of Toronto, we employed Simulated Annealing (SA) [9] and Firefly Algorithm [10] as bio-inspired heuristic algorithms. Apart from Simulated Annealing and Firefly Algorithm, Genetic Algorithms (GA) [8], Particle Swarm Optimization (PSO), and Ant Colony Optimization (ACO) are frequently used in the literature for multi-objective optimization problems and dynamic environment path planning.
Genetic Algorithms simulate natural selection and genetic mechanisms, generating new solutions through selection, crossover, and mutation operations. In path planning problems, GA is particularly suitable for handling highly complex search spaces. However, compared to SA and Firefly Algorithm, GA may have a slower convergence speed, and parameter tuning can be relatively complex (Goldberg & Holland, 1988). PSO mimics the social behavior of bird flocks or fish schools, finding optimal solutions through particle collaboration and information sharing. While PSO performs significantly well in single-objective optimization problems, it may not be as flexible as SA and Firefly Algorithm in handling multi-objective and dynamic environment path planning scenarios (Kennedy & Eberhart, 1995). ACO simulates the foraging behavior of ants, seeking optimal paths by mimicking ants leaving pheromones on routes. However, ACO often requires longer convergence times and more challenging parameter adjustments.
Each of these algorithms has its characteristics, demonstrating distinct strengths and limitations in different path planning scenarios. SA and Firefly Algorithms strike a better balance, effectively handling multi-objective optimization problems while maintaining a good balance between global and local searches.
Problem Formulation and Modeling
- Data
Our project leverages multiple datasets to enhance the route planning algorithm. These datasets include:
- Traffic Data: We collect real-time traffic incident data, historical traffic volume, and other relevant traffic statistics.
- Geographical Data: This includes data about road networks, intersections, and other geographical features relevant to route planning.
- Health Service Locations: We incorporate data about health service locations such as hospitals, pharmacies, and life labs, specifically focusing on the Toronto area.
2. Exploratory Spatial Data Analysis (ESDA)
Exploratory Spatial Data Analysis finds application in geography, geoinformatics, and related spatial fields, enabling the examination and depiction of spatial patterns and relationships within datasets. To illustrate the route map derived from traffic and geography data, we present visualized datasets sourced from an open data library for a comprehensive overview.
The preceding plot displays three types of healthcare facilities investigated in our specific area of focus. It illustrates a limited number of hospitals (depicted as red dots) serving the region, whereas there is a higher concentration of lifelabs laboratories (represented by blue dots) catering to patients. Additionally, there is a significant presence of pharmacy stores (indicated by green dots), ensuring convenient accessibility for residents in downtown Toronto.
The optimized route calculation from residence buildings to health service facilities takes into consideration the significant impact of traffic volume. Crossroads are categorized into three levels based on their daily 15-minute traffic volumes. The depicted plot illustrates this classification, with red dots representing the nodes experiencing the highest traffic volumes and blue dots indicating those with the least traffic volume.
The path-finding algorithm takes real-time traffic incidents into account, actively avoiding map nodes associated with high severity levels in the optimized route. In the visual representation, red dots indicate roads with the highest severity level, while purple dots denote incidents of medium-to-high severity. Additionally, blue and green dots represent incidents of medium-to-low and low severity, respectively. As an illustrative example in the map above, the area around King’s College Circle at the University of Toronto is marked with a red dot, signifying a road closure due to construction, making it unavailable in our algorithmically determined path.
3. Mathematical formulation of the problem
We have chosen 20 buildings within the downtown area of Toronto for our study and computed their accessibility scores regarding medical facilities. We focused on three types of medical facilities: hospitals, life labs, and pharmacies, with corresponding weights of 0.6, 0.3, and 0.1, respectively.
We consider two modes of transportation: walking and driving.
For walking, we employed the Dijkstra algorithm for pathfinding. Subsequently, based on the pedestrian traffic volume along each edge of the path, we calculated real-time walking speeds. The pedestrian travel time on the path was then determined. The relationship between pedestrian traffic volume and walking speed is expressed as follows:
For driving, we employ Simulated Annealing and Firefly algorithms for pathfinding, modeling it as a multi-objective route planning problem. The factors we consider include path length, real-time traffic incidents, historical traffic volume, and the number of intersections passed on the road. The function we aim to minimize is:
The calculation formula for the accessibility score is:
Proposed Solution
- Firefly Algorithm
The Firefly Algorithm, drawing inspiration from the flashing behavior of fireflies, belongs to the swarm intelligence family of optimization algorithms. In our specific use case, we implemented three key parameters: iterations, population size, and gamma.
To initiate the algorithm, a population of fireflies is randomly placed in the search space, and an objective function is defined. In our scenario, the objective is to determine the most optimized route from selected residential buildings to health service locations. The algorithm then assesses the fitness of each firefly based on the defined objective function.
As the optimization unfolds, fireflies adjust their positions, moving toward others with their movement guided by the brightness, which reflects their fitness. The degree of attraction between two fireflies is influenced by their brightness, distance, and a light absorption coefficient known as gamma.
Post-movement, the brightness of each firefly is updated according to its fitness value. The next generation of fireflies is then selected based on these updated brightness values, and the process repeats. This iterative cycle continues until the algorithm reaches the predefined number of iterations.
In summary, the Firefly Algorithm dynamically orchestrates the movement and evolution of a firefly population, continually refining their positions to converge towards optimal solutions for the specified optimization problem in our case — finding the most efficient route to health service locations from residential buildings.
2. Simulated Annealing
The Simulated Annealing algorithm is an optimization algorithm that is inspired by the physical annealing process. In this algorithm, a worse result may be accepted in order to find the global optimum solution.
In our implementation, we have two parameters: temperature and number of iterations. We predefined the cooling schedule to reduce the complexity of tuning parameters. At the beginning of the algorithm, a random route is generated. In each iteration, new routes will be generated based on the current route. Then the defined objective function is used to evaluate the new routes. The algorithm decides whether to accept the new route based on the current temperature and the evaluation. After that, the temperature is cooled down according to the cooling schedule. As the temperature cools down, it is less and less possible that the algorithm accepts a worse route. We repeat the process until it reaches the iterations we set for the algorithm.
3. Implementation
Performance Evaluation
1. Firefly Algorithm
1.1 Iteration
In our optimization process, the final optimized route is obtained within a pre-determined number of iterations, and we anticipate improved results with a higher iteration value. To assess the impact of iteration settings on the quality of the solution, we conducted a test comparing the costs of optimized routes under different iteration configurations.
The evaluation of route cost takes into account factors such as distance, the number of turns, traffic incident severity, and traffic volume. Specifically, in this test, we set the firefly population size to 26, and gamma is assigned a value of 2. Each iteration test is executed three times, allowing us to not only gauge the overall performance but also assess the stability of the outcomes across multiple runs.
This systematic approach to testing iteration variations, coupled with the consideration of multiple factors in route cost evaluation, enables a comprehensive analysis of the Firefly Algorithm’s performance and the robustness of the optimized routes generated for our specific use case.
Based on our analysis of the iteration versus cost figures, it is evident that the cost value tends to stabilize when the iteration value exceeds 25. Considering the proportional relationship between execution time and iteration value, where 25 cycles take approximately 4 minutes and 12 seconds, and 30 cycles take around 4 minutes and 56.5 seconds (using an i7–6700k processor with 64GB memory), we have made the decision to set the iteration value to 25 in our test report.
This choice strikes a balance between achieving stable and optimized results while managing the computational resources required for the optimization process. By opting for an iteration value of 25, we aim to ensure an efficient use of computational time while still obtaining reliable and effective solutions for our specific scenario involving 20 buildings in the Firefly Algorithm.
1.2 Population size
Population size, denoting the number of fireflies in the swarm, serves as a crucial parameter influencing the exploration of potential solutions concurrently. A larger population size implies a broader exploration, potentially leading to better coverage in the calculated route. To assess the optimal population size for route optimization, we conducted a test spanning population sizes from 2 to 50. The evaluation focused on comparing the total cost of routes between U Condominium and three specified health service locations. The results are presented below:
The plot indicates that the total cost approaches 6650. In the context of the Firefly Algorithm, it’s noteworthy that selecting a larger population size demands greater computing power. Considering a balance between achieving optimized output and maintaining reasonable computing time, we have determined that a population size of 26 is the most suitable choice. This decision aims to harness the benefits of a sufficiently large population for effective route optimization while managing computational resources efficiently.
1.3 Gamma
Gamma, as a parameter in the Firefly Algorithm, plays a pivotal role as the attractiveness scaling factor. It is instrumental in the equation that models the attractiveness between two fireflies, taking into account their brightness and distance. To comprehensively evaluate the impact of gamma on route optimization, we conducted tests covering a range of gamma values from 1 to 12. The total cost results from these tests are gathered for analysis.
It’s noteworthy that, through our analysis, we have identified that setting gamma to 3 yields a favorable balance between achieving a reasonably low route cost and ensuring comprehensive solution coverage. This particular configuration appears to offer a well-optimized and effective solution within the context of our route optimization problem using the Firefly Algorithm.
2. Simulated Annealing
2.1 Temperature
Temperature is a critical parameter for the Simulated Annealing algorithm to determine whether or not it accepts a new solution. The higher the temperature, the more likely the SA will accept a bad solution.
From the graph, we can see that total cost doesn’t change too much when initial temperature changes from 10 to 190. However, we can find that when the initial temperature is 130, the costs in all numbers of iterations tend to be converging and the lowest. To have a consistent and optimum result, we determine the initial temperature should be around 130.
In order to decide the temperature more precisely, we tested the temperatures from 110 to 150 with the number of iterations set to 30. From the result, we can see that there is no obvious ascending or descending trend. Thus, we decide to choose 139 as the initial temperature since it generates the best result.
2.2 Iterations
In each iteration, the simulated annealing algorithm generates and evaluates new solutions. Then temperature is updated for a new iteration. Thus, the number of iterations would affect the generation and adoption of new solutions, which makes it an important parameter in the algorithm. To comprehensively evaluate the impact of iterations on route optimization, we conducted tests three times covering a range of iteration values from 1 to 50. The total cost results from these tests are gathered for analysis.
From the figures above, it is hard to see the number of iterations has a significant impact on the cost of the solution. Considering the balance between achieving stable and optimized results while managing the computational resources required for the optimization process, we didn’t test the number of iterations beyond 50. Given our test results, we determine 30 is an optimal value for this parameter leading to a stable and efficient solution.
3 Comparison between Firefly and SA
Upon comparing the results obtained from the Firefly Algorithm with those from Simulated Annealing (SA), a notable distinction emerges: the route cost generated by the Firefly Algorithm is markedly lower than that produced by SA. Furthermore, a visual inspection of the route maps generated by both algorithms reveals that the Firefly Algorithm generates a path that is notably straighter and smoother when navigating to the destination.
The Firefly Algorithm offers simplicity in comprehension and implementation within the source code. Additionally, it demonstrates efficiency and robustness when addressing pathfinding issues in our specific use case. Nevertheless, determining the optimal parameters for the Firefly Algorithm is a time-consuming process. In our scenario, we conducted a total of 90 test cycles to compare iterations, population size, and gamma values. Another drawback is the algorithm’s lack of memory for past iterations, preventing effective utilization of information from previous search steps.
The Simulated Annealing Algorithm is easy to understand and implement. Its design allows it to explore the solution space more thoroughly. However, its parameter tuning process is time consuming and difficult. In our experiments, the parameters don’t seem to have an obvious effect on the solutions, making it hard to determine the optimal parameters. Also, Its probabilistic nature seems to lead the algorithm to a worse solution very commonly, which causes much uncertainty when conducting the tests and is quite harmful when generating an optimum solution in limited trials.
3. Results
We have included our test results for finding the best-fit parameters in Firefly and SA algorithm in the shared fold:
We also run the path finding with two algorithms for 20 selected residence building in downtown Toronto. The route maps are used to evaluate the performance of the algorithms.
Conclusions & Recommendations
This study aimed to evaluate healthcare facility accessibility in downtown Toronto through a quantitative scoring system that integrates pedestrian and vehicular traffic data. Utilizing advanced optimization algorithms such as the Firefly Algorithm and Simulated Annealing, the primary objective was to assess and optimize routes to healthcare facilities, offering insights into urban healthcare access challenges.
The methodological approach included data collection on traffic patterns, pedestrian flows, and healthcare facility locations, and the Firefly Algorithm and Simulated Annealing were applied. The unique scoring system considered factors like distance, travel time, and traffic conditions, providing a holistic measure of accessibility.
Even though this study contributes to understanding and addressing urban healthcare accessibility challenges through advanced algorithms and comprehensive data analysis, as the scope of the problem expands, the computational time required by the bio-inspired algorithms, namely SA and Firefly, becomes a noteworthy concern. Hence, enhancing the computational efficiency of bio-inspired algorithms emerges as a crucial and meaningful avenue for future research. Also, refining the Firefly Algorithm and Simulated Annealing could lead to more accurate and efficient route optimizations. This might involve tweaking algorithm parameters or developing hybrid algorithms that combine the strengths of both. Incorporating machine learning techniques could also be recommended for future research, which would enable the algorithms to learn from large datasets, improving their predictive accuracy and adaptability to changing urban environments.
In addition to the current study’s methodology, there are opportunities to enrich insights and further enhance the holistic evaluation of healthcare facility accessibility in urban settings. One avenue for future research involves integrating additional data sources, such as socio-economic data, public transportation schedules, weather patterns, and healthcare facility capacities. By incorporating these diverse factors, the scoring system can offer a more comprehensive perspective on accessibility challenges, contributing to a more informed decision-making process for urban planners and policymakers.
Furthermore, the potential for real-time data utilization represents a critical aspect of future research directions. The existing study primarily relies on static data, but incorporating real-time information could significantly improve the dynamism and accuracy of the accessibility scoring system. Real-time data, encompassing fluctuations in traffic patterns, weather conditions, and other relevant variables, would enable a more adaptive and responsive assessment of healthcare accessibility in the ever-changing urban landscape.
In conclusion, this project represents a step forward in understanding and improving healthcare accessibility in urban areas. By leveraging advanced algorithms and comprehensive data analysis, it provides an approach to a pressing urban challenge.
Reference
[1] Wolch J, Wilson J P, Fehrenbach J. Parks and park funding in Los Angeles: An equity-mapping analysis[J]. Urban geography, 2005, 26(1): 4–35.
[2] Luo W, Wang F. Measures of spatial accessibility to health care in a GIS environment: synthesis and a case study in the Chicago region[J]. Environment and planning B: planning and design, 2003, 30(6): 865–884.
[3] Guy C M. The assessment of access to local shopping opportunities: a comparison of accessibility measures[J]. Environment and planning b: Planning and design, 1983, 10(2): 219–237.
[4] Pacione M. Access to urban services — the case of secondary schools in Glasgow[J]. Scottish Geographical Magazine, 1989, 105(1): 12–18.
[5] Higgs G. A literature review of the use of GIS-based measures of access to health care services[J]. Health Services and Outcomes Research Methodology, 2004, 5: 119–139.
[6] Radke J, Mu L. Spatial decompositions, modeling and mapping service regions to predict access to social programs[J]. Geographic Information Sciences, 2000, 6(2): 105–112.
[7] Yu S, Zhu X, He Q. An Assessment of Urban Park Access Using House-Level Data in Urban China: Through the Lens of Social Equity. Int J Environ Res Public Health. 2020 Mar 31;17(7):2349. doi: 10.3390/ijerph17072349. PMID: 32244280; PMCID: PMC7177907.
[8] Arunadevi J, Johnsanjeevkumar A, Sujatha N. Intelligent transport route planning using parallel genetic algorithms and MPI in high performance computing cluster[C]//15th International Conference on Advanced Computing and Communications (ADCOM 2007). IEEE, 2007: 578–583.
[9] Sankararao B, Yoo C K. Development of a robust multiobjective simulated annealing algorithm for solving multiobjective optimization problems[J]. Industrial & engineering chemistry research, 2011, 50(11): 6728–6742.
[10] Yang, X. S. (2008). Nature-Inspired Metaheuristic Algorithms. Luniver Press. ISBN 978–1–905986–10–1.
