Curb Management: Less is More
The curb has always served a variety of functions for its users: pickup and dropoff access for both people and goods, vehicle parking and movement, public space, and more.
However, in the last ten years or so, those users have increased in both number and type—notably rideshare services, bike- and scooter-share stations, and explosive growth in e-commerce delivery. All three of these uses are here to stay, and there are more (such as delivery robots, autonomous vehicles, and even drones) on the near horizon.
Given the rather intense and immediate need for our urban curbs to do more things for more people, managing them can no longer be a matter of pouring concrete, applying paint, or erecting signs every so often—improvements to the physical infrastructure have reached a ceiling in their ability to help. Efficiently allocating curb space in today’s transportation ecosystem must take into account the ever-changing demand of different modes, for different lengths of time, at different times of day, days of the week, and weeks of the year. In other words, modern curb management needs to be multi-modal, digital, and dynamic.
The good news: not only is this possible, it can also result in outcomes that positively impact nearly every stakeholder: reduce congestion, lower vehicle emissions for cleaner air, and increase safety for drivers, riders, cyclists, and pedestrians.
This, of course, is not a terribly new concept in the world of transportation. A recent technical report from the National Academies for Sciences, Engineering, and Medicine, builds a strong and comprehensive case for dynamic curb management. There are several organizations, from third-party logistics companies to public agencies to Silicon Valley innovators like Lacuna, that are pursuing solutions and creating the digital infrastructure needed to power them.
Breaking Down the Challenge
In particular, dynamic curb management requires us to solve two related, but distinct and equally important, problems:
Understanding the time-varying demand for curb access across modes: high-quality data that describes what types of vehicles are using the curb, when, where, and for how long
Building a scalable algorithm that allocates curb access to different uses or users based on current and predicted demand
I was recently an integral member of a cross-disciplinary research team that tackled the second problem—and developed a groundbreaking curb allocation algorithm.
To understand how our algorithm should work, we started with some fundamental tools from numerical optimization. Current academic consensus holds that every optimization problem has three key components that are then tailored for a solution’s purpose, and for us, doing so was quite straightforward:
Decision Variables
One of three different types to which every curb space is allocated per hour. We identified the three types as paid parking, commercial vehicle loading/unloading, and public transit.
Objective Function
maximize the total curb usage across the modes and time, in terms of total vehicle minutes spent at the curb.
Constraints
Intended to reflect sensible transportation policy preferences, our goals are:
Avoid excessively switching the allocation to a curb space over time.
Avoid any of the allocation types from being disproportionately over- or under-represented.
Avoid having allocations of the same type directly adjacent to each other.
Our Approach
In most modern optimization applications, defining the three components is usually the easy part. The real challenge is the variable computation time to solve them, depending on what approach we use. For instance, the simplest approach, called a brute-force algorithm, enumerates all possible combinations of values of the decision variables, and picks the best one. Using standard desktop processors, computing the best allocation for a few hundred spots through brute force could take several hours—an unworkable amount of time given the need to recompute allocations multiple times a day.
To solve the curb allocation problem in a more efficient manner, our approach uses an elegant technique from the optimization literature called Dantzig-Wolfe decomposition. The key idea is to exploit the underlying local structure of the possible solutions—in our case, the best allocation for a particular curb space depends only on itself and the immediately adjacent spaces, rather than in the context of the city as a whole. By harnessing a structure that allows us to scale the problem down instead of up, our algorithm doesn’t solve one big problem so much as break it down into several much-smaller subproblems that it solves in parallel.
The Results
Curb allocation during the day
Curb allocation at night
We evaluated the algorithm with simulations on nearly 300 curb spaces—each of which was allocated to one of our three allocation types—in Seattle’s Belltown neighborhood, which our team frequently uses for experimental evaluations thanks to its mixed-use zoning and corresponding diversity of curb users.
Across all simulations, the approach computed optimal allocations for all spaces within 20 seconds—a dramatically smaller amount of time than the brute-force approach, and one that enables recomputations as often as once per hour.
Thanks to a rather counterintuitive approach, we created a curb management algorithm that successfully scales to the city level and operates efficiently in real-world scenarios.
Dig Into the Technical Details
This work was conducted in a long-running collaboration with Pacific Northwest National Laboratory on its Dynamic Curbs project. I’m proud to share that the team published our findings in a technical paper for IEEE’s 2022 Intelligent Transportation Systems Conference — one of the world’s premier conferences for research on intelligent transportation systems.
