Fleet Planner is a cloud-based API for computing efficient routes for vehicles to perform tasks at various geographical locations. Fleet Planner can be used to power a ride-hailing platform, to deliver packages, to collect and distribute shared bikes or scooters, and much more.
Drivers on today’s ride-hailing apps generally prioritize their own profit over the productivity and efficiency of the service as a whole. Ride-hailing platforms may give out incentives to drive around certain areas at certain times, but they can’t force drivers to operate when and where they’re needed. Drivers will position themselves in areas where they’ll make the most money, so it’s not possible for the service provider to position each vehicle in a way that optimizes profit for the entirety of the ride-hailing fleet.
Soon, in addition to human drivers, ride-hailing platforms will be powered by self-driving vehicles. Without human drivers making their own decisions about positioning and operating hours, next generation ride-hailing platforms will be able to fully control the utilization of their fleets. But here’s the catch — creating routes for a fleet of vehicles while optimizing for the right thing (speed, efficiency, etc.) is really, really difficult.
Self-driving fleet operators will need to decide how many vehicles should be deployed at a given time in a given place to make the service accessible to as many customers as possible. They’ll need to make sure the vehicles are used efficiently and also figure out where to locate depots for drained vehicles to return to.
Traditionally, these issues have been well-characterized by the Vehicle Routing Problem (VRP), an NP-hard problem that generalizes the well known Traveling Salesman Problem. But there are several limitations to directly applying VRP in practice. First, while optimal solutions can be found for a small set of passengers and vehicles, the complexity of the problem grows exponentially as the number of vehicles and passengers increases. Second, traditional VRPs are solved with prior knowledge of all relevant information and for all requests at once. However, in practical applications, dynamic requests force plans to be updated over time. Each request requires thousands of time and distance estimates between points to calculate costs like those shown in Figure 1. Those estimates need to come from accurate and reliable mapping and routing services.
Building a service that addresses all of this is time- and cost-intensive; it requires the best routing and infrastructure engineers. That’s why we’ve developed a tool that does the work for you.
rideOS’s Fleet Planner finds the most efficient set of routes for a fleet of vehicles to traverse in dynamic scenarios.
Use Case #1: Taxis vs. Shared Rides
Sharing rides can reduce congestion as well as increase fleet utilization. However, if dispatched improperly, shared rides can take so much longer than single-passenger rides that, to many riders, the lowered cost isn’t worth it. Fleet Planner can optimize dispatches to increase fleet utilization without compromising trip quality.
Using New York City taxi data, we simulated the difference between shared rides and single-passenger taxi trips, and compared the simulations on:
- Fulfill rate: Number of completed trips divided by the number of requests
- Percentage of idle time: Percentage of vehicles’ driving time with no passenger
- Average vehicle miles per passenger: Vehicle miles driven divided by the number of completed trips
- Ride time: Difference between pick up time and drop off time
- Wait time: Difference between request time and pick up time
- Total time: Ride time plus wait time
Assuming passengers do not accept proposed trips if their drop off ETA is greater than 50% of the fastest path ETA plus 10 minutes, we found that:
- More trips are completed (i.e., not canceled) for shared rides (~80%) compared to taxis (60%).
- Average miles per completed passenger and percentage of idle time (i.e., empty vehicles) are much lower for shared rides.
- Shared rides lead to lower wait times but slightly higher ride times, which leads to reduction in total median time.
It’s clear from these results that an efficient and scalable system for matching and dispatching shared rides can serve NYC’s urban population effectively — and actually deliver more trips without sacrificing trip quality.
Use Case #2: Scooter Pick-up for Charging
Scooter companies employ people, “chargers,” to pick up low-battery scooters throughout the city and bring them to charging stations. The more efficient the routes are for picking up and charging scooters, the faster the turnover of available scooters on city streets, which means more overall trips can happen in a day.
Assuming scooters run out of battery according to a certain spatio-temporal distribution, we simulated an eight-hour window of pick-ups where chargers were dynamically dispatched over time to pick up scooters and bring them to a charging station.
Our results show that, compared to a “greedy assignment” strategy where chargers pick up scooters as their capacity allows, Fleet Planner’s strategic dispatching leads to a 35% reduction in low-battery scooters per minute. In other words, Fleet Planner makes more scooters available for consumers, simply by making it more efficient for chargers to pick up and recharge them.
Try our interactive scooter optimization simulation here!
Practical fleet routing applications involve thousands of vehicles and passengers. Fleet Planner is built around a microservices architecture designed to be scalable from the get-go.
In a simulation with a dataset consisting of 1,000 vehicles with 40,000 passenger requests during a four-hour window in one city (which translates to 240,000 trips a day), Fleet Planner performed 100,000 simulated miles without any degradation in runtime. For comparison, in San Francisco, ride-hailing companies are known to serve 200,000+ trips every day. Fleet Planner can comfortably manage the scale of today’s ride-hailing demand and can even support different request types, including pre-scheduled trips.
There are several existing off-the-shelf solutions, such as jsprit or Google OR-Tools, that work well in static scenarios with a handful of vehicles and stop locations known in advance. But in real-world situations where new requests and unexpected changes happen constantly (e.g., last-minute cancellations), they’re not able to scale quickly the way Fleet Planner can.
In a comparison test between Fleet Planner and jsprit, a popular java-based VRP solver, we streamed a set of requests (~900 requests spread over a four-hour window) and had the solvers compute a set of plans in response. Fleet Planner performed significantly better in terms of runtime and showed a 15% reduction in ride time. Additionally, by default, jsprit minimizes total vehicle costs (i.e., distance) with passenger constraints (e.g., time windows) — it would need to be reconfigured to optimize for passenger ride time.
Fleet Planner supports all kinds of next-generation transport — users can tune the planner for specific applications such as ride-hailing, scooter pick ups, parcel deliveries, and more.
Fleet Planner is built on rideOS’s state-of-the-art Map Services, which include AV-flexible path finding, real-time traffic, and multiple basemaps. Since we’ve built these Map Services in-house, they provide extremely accurate and customized estimates to Fleet Planner.
Having accurate time and distance estimates is critical to ensure vehicle efficiency and quality of service. For instance, below are two very different plans for the same pickup and delivery requests. On the left, the plan is for bikers, where minimizing distance is most important. On the right, the plan is for vehicles, where minimizing travel time is most important.
These customized cost estimates are used by Fleet Planner’s core solver, which explores the space of solutions according to the priorities of the operator. The solver has a flexible objective function that models both fleet costs (e.g., vehicle distance) as well as passenger/goods cost (e.g., wait times). To get to the optimal solution faster, the solver employs heuristics such as ignoring directions that lead to infeasible solutions, drawing on similar solutions from past requests, and learning from historical data.
The end result is a highly flexible and efficient solver for practical fleet routing applications.
Try it today
Fleet Planner provides multi-vehicle, multi-passenger dispatch as a service. It’s available for use today. To try it out, visit our Developer page or email contact@rideos.ai for more information.
