Zoba’s new optimization engine: 12x faster in big markets, more optimal results
This piece is coauthored by Evan Fields, head of Data Science at Zoba, and Ali Kim, software engineer.
A new version of the Zoba optimization engine is now powering Zoba’s recommendations for shared mobility fleets, delivering more-optimal results, 4x faster runtimes overall, and 12x faster runtimes on the largest optimization jobs.
Zoba offers two products that provide optimized recommendations for fleet management actions: Zoba Move and Zoba Price. Zoba Move provides recommendations for physical interventions: rebalances, swaps, and deployments. Zoba Price recommends vehicles to discount in order to induce demand.
Internally, these products are powered by a shared set of models which ensures consistency across products. Each model serves a specific function: estimating demand, calculating optimal fleet distributions, and routing operations staff across tasks. Today, we’re announcing version 2.0 of the optimization engine, which is responsible for finding the vehicle distribution which will maximize network-wide objectives subject to various operational and regulatory constraints, as well as forecasted demand and competition dynamics.
In order to capture complex network dynamics such as time-dependent demand patterns, customer movement probabilities, and inter-vehicle competition for rides, the optimization engine contains a custom simulation of how mobility networks evolve over time. Given an initial distribution of vehicles throughout a network, this simulator predicts when and where rides will start and the destination of each ride. The optimization engine’s job is to find the initial distribution of vehicles which results in the most favorable outcome over time. Typically “most favorably” means “serving the most rides,” but other objectives like profit or revenue maximization are also possible.
Until recently, the optimization engine mathematically represented this simulation and the associated initial state decisions as large linear optimization problems. We used a leading commercial linear optimization solver to solve each instance of this problem.
But wait a second — mobility network dynamics are fundamentally nonlinear! For example, there are diminishing returns to supplying more and more vehicles to a given location at a given time. As the supply increases, each marginal vehicle captures fewer and fewer marginal (expected) rides. Once a location is fully saturated with vehicles, adding one more vehicle won’t capture any additional rides. Therefore the objective function must be nonlinear in the number of vehicles supplied.
However, standard linear optimization modeling tricks allow for approximating nonlinear behavior through the introduction of auxiliary variables and constraints. The absolute value function provides a nice example. Suppose we want to optimize a problem like
minimize |x|
subject to constraints(x)
The absolute value function |x| is decidedly nonlinear. But by introducing an auxiliary variable y, we can capture the nonlinear behavior:
minimize y
subject to constraints(x)
and y ≥ x
and y ≥ -x
Notice that whether x is positive or negative, y must be at least the magnitude of x, i.e. y ≥ |x|. And since we’re trying to minimize y, at the optimal solution we’ll find y = |x|. Voila: nonlinear behavior through an auxiliary variable.
Version 1.0 of the optimization engine used this and similar tricks at scale to capture the physically essential nonlinear behavior of mobility systems in a linear optimization framework. To capture nonlinear network dynamics in a linear framework, we introduced a lot of auxiliary variables: we finely discretized each market in both space and time, and had separate variables representing vehicle counts and ride counts at every location at every time. (This technique is sometimes called building a “time expanded network,” since the formulation includes a copy of the spatial network for each discrete time step.)
Because Zoba optimizes some of the largest mobility markets in the world, the resulting models could get quite large. Larger markets may have thousands of discrete locations, and our time discretization can split a 24-hour period into over a hundred discrete time steps. As a result, our largest linear models had millions of variables and constraints. Even with the industry-leading commercial solver, finding optimal solutions for such large models was too slow. Our largest models were requiring tens of minutes to solve — not practical for a highly dynamic mobility system that evolves constantly.
We were especially troubled by the empirical relationship between market size and model run time. We found that the time required to solve these large linear models was roughly quadratic in the number of variables, meaning that doubling the number of locations in a market would approximately quadruple the time to optimize. As Zoba continues to expand worldwide, hour-long optimizations wouldn’t provide an optimal experience for our customers.
A key observation is that most of the variables and constraints in the linear model are not decision variables representing the optimal vehicle distribution; they’re just auxiliary variables to capture nonlinear behavior. In a market with n locations that we want to optimize for t time steps, there are O(n) decision variables representing things like “how many vehicles to deploy at each location” or “how many batteries to swap in each area of the city.” But there are O(nt) auxiliary variables representing vehicle and ride counts at every location and every time. This observation prompted a natural question: Moving to an intrinsically nonlinear model could eliminate the need for these hundreds of thousands of auxiliary variables. Given that nonlinear models are not as efficiently solvable as linear models, would a moderate size nonlinear model outperform a large linear model?
We’re delighted to answer that question with a resounding “yes.”
Last fall we began investigating alternatives to these large linear models and implemented a proof-of-concept nonlinear optimizer with huge success: solve times improved 12x in larger markets and scaled much better with market size. The plot below shows a representative sample of approximately 200 real-world optimizations Zoba performed, sorted by optimization time on version 1.0 of the optimization engine. Solve time in version 1.0 is shown in blue, and nonlinear solve time is in orange. Notice how performance is comparable for the small jobs which run quickly on both systems, but the large complicated jobs that took hundreds of seconds on the earlier linear optimizer take only a few seconds on the nonlinear prototype.
After observing the performance gains above, we polished the prototype to bring it up to our production standards, which resulted in version 2.0 of the core optimization engine. This upgraded optimization engine directly optimizes over our nonlinear network simulation and thus sidesteps the need for large linear approximations. We leverage problem-specific structure and GPU-accelerated matrix operations to efficiently compute gradients; this supports fast optimization via first order methods (i.e. algorithms which require only objective and gradient information, not higher order derivatives).
Perhaps an even more significant outcome of our new nonlinear approach is that we are no longer restricted to the terms of the commercial linear optimization solver’s license. Under the license, we could only run a few parallel optimizations at a time—quite limiting, considering we run thousands of optimizations a day, many of which coincide with each other during peak times. By moving off of the commercial solver and fully integrating the nonlinear optimization engine into our code base, we are now able to scale the optimization engine horizontally with the rest of our infrastructure; consequently, we can run optimizations in parallel with virtually no limit and low costs.
We talked previously about how the framework of linear optimization allowed us to find the certifiably optimal solution. However, the solution is only certifiably optimal within the linear approximation of our mobility network simulation. On the other hand, nonlinear optimization can’t guarantee global optimality, but by optimizing over the simulation directly it can avoid the approximation error. There are some complications around the fact that time dynamics in our simulation make the problem slightly convex in places, but we’ve been able to implement a solver that works very well in practice. Stay tuned for a future blog post exploring some of the technical strategies we use to ensure good performance in a tricky non-concave, nonlinear world.
In fact, we’ve found that the new nonlinear optimization engine typically produces slightly better results than the prior linearized version. On average, we find that version 2.0 produces results about half a percent better than version 1.0. That difference may seem small, but across the many markets Zoba optimizes, it corresponds to hundreds or thousands of extra rides per day. And in a difficult low margin business like shared mobility, even small marginal gains in rides can have significant effects on profitability!
The model and infrastructure improvements of our new optimization engine have catapulted our products forward. Not only did the solve times in our larger markets go from tens of minutes to tens of seconds, we also unlocked the ability to optimize across large cities which cover thousands of square kilometers and contain tens of thousands of vehicles. Instead of having to deal with the O(nt) auxiliary variables introduced by linear approximation, we now have only O(n) decision variables and measure empirical runtime that’s close to linear in problem size. This means Zoba can efficiently optimize the largest and densest mobility markets in the world. For our customers, this means even your most complicated markets can be optimized in seconds, and following Zoba’s optimized recommendations produces even more fleet revenue than before.
If you’re interested in working on problems like these, get in touch at zoba.com/careers. And if you have a fleet that can benefit from decision automation, we’d love to hear from you at zoba.com.
