TL;DR
This paper tackles the challenge of improving urban walkability by strategically placing new amenities like grocery stores and schools. They introduce novel optimization models (MILP and CP) and a fast greedy algorithm, demonstrating significant improvements in walkability scores and reduced walking distances in Toronto's underserved neighborhoods.
What Problem Does This Paper Address?
Urban development, particularly due to historical zoning practices and underinvestment, has led to unequal access to essential services and amenities, resulting in "walkability deserts." This spatial inequality disproportionately affects low-income and minority communities. Improving walkability is crucial not only for public health and economic development but also for environmental sustainability by encouraging active transportation and reducing greenhouse gas emissions. While existing research has explored walkability, there's a need for more realistic and computationally efficient methods that can optimize amenity placement within existing urban fabrics, considering factors like existing amenities and resident preferences for choice.
Methods
The authors formulate the "Walkability Optimization" (WALKOPT) problem as a combinatorial optimization task. They propose two main modeling approaches:
- Mixed-Integer Linear Programming (MILP): This approach uses a detailed set of variables and constraints to precisely model the problem. It considers multiple amenity types, the "depth of choice" (e.g., multiple restaurant options), existing amenities, and resident behavior.
- Constraint Programming (CP): This offers a more compact formulation, particularly beneficial when "depth of choice" is not a factor, by using index-based decision variables.
Recognizing the computational complexity of these exact methods, they also develop a Greedy Algorithm. This algorithm is motivated by the submodular nature of the objective function in simpler cases (single amenity type, no depth of choice). The greedy approach iteratively selects the amenity-location pair that yields the greatest marginal improvement in walkability, offering a scalable heuristic for more complex scenarios.
Datasets
The case study uses data from the City of Toronto, Canada, focusing on 31 "Neighbourhood Improvement Areas" (NIAs) identified as facing inequitable outcomes.
- Geographical Boundaries: Publicly available data for NIAs.
- Pedestrian Network: The "PedNet" dataset from the City of Toronto, providing walkable paths (sidewalks, crosswalks).
- Residential and Candidate Locations: Derived from OpenStreetMap and mapped to the PedNet. Candidate locations for new amenities were specifically parking lots.
- Amenity Locations: Existing locations for grocery stores, restaurants, and schools were obtained from OpenStreetMap.
Key Insights and Ideas
- Submodularity as a Driver for Efficient Algorithms: The discovery that the walkability objective function is submodular (in simplified cases) is a key insight, justifying the use of a greedy algorithm as an efficient heuristic. This highlights how theoretical properties can lead to practical algorithmic improvements.
- Realistic Modeling of Resident Behavior: The inclusion of "depth of choice" for amenities like restaurants, alongside considering existing amenities, makes the model more aligned with real-world urban planning challenges than previous approaches that might have assumed a blank slate.
- The Power of Strategic Amenity Placement: The study demonstrates that even with a limited number of new amenities, significant improvements in walkability can be achieved, particularly in areas that currently lack them. This suggests that targeted interventions can be highly effective.
- Trade-offs Between Exactness and Scalability: The comparison between MILP, CP, and the greedy algorithm clearly illustrates the classic trade-off between finding optimal solutions and the computational resources required, especially as problem size increases.
Key Results
- Improved Walkability Scores: The optimization framework, particularly with the MILP and Greedy algorithms, significantly improved the average "WalkScore" in the studied neighborhoods. In some cases, adding just 3 amenities of each type increased the WalkScore by over 50 points.
- Reduced Walking Distances: The allocation of new amenities effectively reduced walking distances. For 75% of residential locations, walking distances to amenities were reduced to 10 minutes or less.
- Algorithm Performance:
- MILP: Found optimal or near-optimal solutions but struggled to scale with larger network sizes, especially in the "MultiChoice" scenario (considering depth of choice).
- CP: Showed better scalability than MILP in some scenarios but was generally slower.
- Greedy Algorithm: Was orders of magnitude faster than MILP and CP, scaling well across all scenarios. It consistently produced high-quality solutions, with a Mean Relative Error (MRE) below 0.7% across all groups and scenarios.
- Impact of Depth of Choice: Considering "depth of choice" (e.g., multiple restaurant options) significantly increased the computational difficulty for both MILP and CP.
Limitations and Future Work
The authors acknowledge several limitations and suggest future research directions:
- Further Realism: Future work could incorporate factors like:
- Population density at residential locations.
- Construction costs for new amenities.
- Area/size constraints of candidate locations.
- Service capacity of amenities.
- Beyond Distance: The current model focuses on travel distance. Future work could incorporate other accessibility factors like the safety and quality of walking paths, potentially through penalties.
- City-Scale Application: The current experiments were on neighborhood-scale instances. Testing the methods at a full city scale would be a valuable next step.
- Alternative Data Sources: While PedNet was used, OpenStreetMap could enable broader case studies in other cities.
Summary updated