  The concept of walkable urban development has gained increased attention due
to its public health, economic, and environmental sustainability benefits.
Unfortunately, land zoning and historic under-investment have resulted in
spatial inequality in walkability and social inequality among residents. We
tackle the problem of Walkability Optimization through the lens of
combinatorial optimization. The task is to select locations in which additional
amenities (e.g., grocery stores, schools, restaurants) can be allocated to
improve resident access via walking while taking into account existing
amenities and providing multiple options (e.g., for restaurants). To this end,
we derive Mixed-Integer Linear Programming (MILP) and Constraint Programming
(CP) models. Moreover, we show that the problem's objective function is
submodular in special cases, which motivates an efficient greedy heuristic. We
conduct a case study on 31 underserved neighborhoods in the City of Toronto,
Canada. MILP finds the best solutions in most scenarios but does not scale well
with network size. The greedy algorithm scales well and finds near-optimal
solutions. Our empirical evaluation shows that neighbourhoods with low
walkability have a great potential for transformation into pedestrian-friendly
neighbourhoods by strategically placing new amenities. Allocating 3 additional
grocery stores, schools, and restaurants can improve the "WalkScore" by more
than 50 points (on a scale of 100) for 4 neighbourhoods and reduce the walking
distances to amenities for 75% of all residential locations to 10 minutes for
all amenity types. Our code and paper appendix are available at
https://github.com/khalil-research/walkability.
