Optimizing Network Design and Vehicle Routing

The Future: On-Demand Urban Air Transportation

On-demand aviation has the potential to radically improve urban mobility, giving people back time lost in their daily commutes. The Uber Elevate team is working towards transforming the world through aerial ridesharing at scale. Uber is developing shared air transportation—planned for 2023—in and around cities. Uber is working with Elevate Network partners to launch fleets of small, electric, vertical takeoff and landing (eVTOL) aircraft in Dallas, Los Angeles, and a to-be-announced international market.

The Problem: Skyport Network Design and Vehicle Routing

Optimization of operations is critical to the success of Uber’s futuristic venture. The fact that eVTOLs are restricted to uniquely constructed ‘Skyport’ stations for vehicle departure and arrival makes routing complicated. The Uber team applies mathematical optimization to address the problems of network design and vehicle routing.

1. Network Design – The first is a network design matching problem that seeks to identify the optimal locations for Skyports. It takes as input trip origins and destinations, runs a modified clustering algorithm to determine where building infrastructure makes the most sense, and determines the optimal subset of the clustered set to induce the highest expected number of riders leveraging the custom-built demand choice model.

2. Vehicle Routing – The second is a vehicle routing problem, seeking to optimize the routing of vehicles to serve trips after the network has been designed. It is far more complicated than a traditional vehicle routing problem due to the need for vehicle recharging and rider pooling. Determining when, where, and how often every vehicle across the network should recharge, to maximize throughput, minimize downtime and not exceed grid capacity, introduces many structural difficulties for a model to solve efficiently. Similar to uberPOOL, riders will be matched with others taking similar trips, making it more cost efficient for all parties. Determining the right balance between system efficiency and rider experience is both delicate and difficult and requires carefully constructed models and optimization.   The problem also has the uncertainty associated with a completely new mode of transportation, where collecting data for this service is extremely complicated. Other things to consider are the behavioral elements of how riders make tradeoffs among a number of alternate modes and integrate them within the complex network optimization models.

The Solution

Uber’s proprietary Flux Optimizer – a demand forecasting and network optimization tool- was able to address Uber Elevate’s network design and vehicle routing problems. The size of the model largely depends on the specific instance – ranging from the hundreds of thousands to multiple millions of integer variables. Using a path-based model to track energy feasibility has improved runtime even when scaling the number of integer variables by an order of magnitude. Solution run times range from a few seconds to multiple hours depending on user inputs, number of trips, etc. It solves the network design problem in one stage, and the vehicle routing problem, with rider matching and battery recharging, in a subsequent stage. Most of the time spent is for generating paths that are used in the routing model. The Uber team created a simple UI that enables users to inspect entities throughout the day or for a specified segment of each mission day. They can verify that the solution is acting appropriately and visualize highly complex solutions and interactions, as well as perform independent studies. Flexible analysis allows users to input various vehicles, batteries, operational or noise requirements, and price points.

Why Gurobi?

We have wrapped the core Gurobi Mixed-Integer Linear Programming (MILP) solver to support our custom use cases, which rely on some computational tricks that are powerful and easy to use. Gurobi Presolve routines have been considerably valuable to us to tighten the original formulation, particularly when we began using leg-based models, which had variable upper bound inequalities. The team had some success with heuristics like RINS and with solution pools to provide users multiple solutions to evaluate. The models require a lot of customization. For example, adding lazy constraints to a subset of constraints of the model has proven extremely useful. The callback methods are extremely flexible and easy to use, which makes implementing algorithms like branch-and-cut an easy task.

Expected Impact

Currently, as there is no baseline, the impact of optimization is difficult to measure. Maximizing the number of riders served by eVTOLs as well as finding the right Skyport locations and getting them as precise as possible, has a significant impact on revenue. Efficient utilization of vehicles, ensuring vehicles are spending as little time on the ground and charging at the right volumes and right places is critical to the success of this venture. Uber conducts analyses on different vehicle concepts that are influencing the specifications of a new fleet of vehicles- faster, capable of higher payload, or flying longer ranges. Uber expects urban aerial ridesharing to evolve into a premium product and accommodate a “meaningful share of trips in a city” which will permit it to offer the service at low price points.

About Uber Elevate

The Uber Elevate team is transforming the world into one that is simultaneously safer and more efficient through aerial ridesharing at scale. Imagine soaring above congested ground traffic – with Uber Air. This future is closer than you think. Starting in 2023, Uber Air will enable shared, multimodal air transportation between suburbs, cities, and ultimately within cities. We’re working with our Elevate Network partners to launch fleets of small, electric VTOL (Vertical Take-off and Landing) in Dallas, Los Angeles, and a to-be-announced third international market.

For more information visit: www.uber.com/elevate.