Using route optimization to build a ride share dispatch algorithm
How to use a Route Optimization API to Build a Ride Share Dispatch System
It's 2022 and you just raised a bunch of money to start a ride-share company to compete with Uber and Lyft. You've hired drivers and built a fancy app that passengers can use to book a ride. The first thing you need to do is find a way to connect passengers to the nearest available driver. You don't want to keep your customers waiting too long for their ride, plus gas is expensive.
In this blog post, we will build a simple but powerful dispatch algorithm that can efficiently match passengers with drivers.
By efficient, I mean that the algorithm will match passengers to drivers in such a way that minimizes the overall distance traveled by your vehicle fleet.
The algorithm will also take into account time-window constraints. For instance, you might want to ensure that drivers can reach their assigned passengers within 15 minutes or less. The algorithm also considers driver shift times so that you don't give jobs to drivers who won't be able to do them because they are ending work.
As a bonus, the algorithm can also handle trip chaining, so that your drivers can be assigned their next passenger while still on a trip. This boosts the utilization of your fleet and keeps your drivers busy and happy. It's very similar to what's used by ride share companies such as Uber and Lyft as well as food delivery companies like DoorDash.
What does a Ride Share Dispatch Algorithm do?
A dispatch algorithm answers the question: given a set of passenger booking requests, which drivers should I assign to each booking?
Uber answers this question every time you request a ride on their app. The app either tells you, "Hey! We found a driver. His name is Joe and he will be at your location in five minutes." or, "I'm sorry, all our drivers are busy right now. Please try again later."
We will use a route optimization subroutine to find the optimal assignment of drivers to bookings that minimize the overall distance traveled by your vehicle fleet. We don't want to assign just any driver to a booking or even the nearest driver. We want to make sure that the total distance traveled by drivers to their assigned passenger pickup locations is as small as possible.
For convenience, we will use the Afi Routing Engine as our route optimization API (docs). It's free to use for small-scale testing (reach out to sales@afi.io for a developer API key) but more importantly, it handles time windows, driver shift times as well as load and capacity constraints—features that are going to be required by our dispatch system.
Why Can't we Match Passengers with the Nearest Available Driver?
You might think the quickest way to solve the dispatch problem would be to simply match passengers with the nearest driver. So, when a booking request comes in, we check to see how far away each driver is from the booking's pickup location and choose the nearest one.
In mathematics, this kind of approach is termed "greedy", and it is suboptimal because the driver-passenger assignment it produces is highly dependent on the order in which you process the bookings. Here's an example to show you what I mean.
Suppose I have three passengers 1, 2 and 3 and three drivers, blue, purple and green. I then match passengers with the nearest driver, starting with passenger 1, then 2 and 3.
Using this algorithm, I get a dispatch solution (above) of 1-green, 2-purple and 3-blue with a total distance cost of 3+3+13 = 19 instead of the optimal solution (below) of 1-blue, 2-purple and 3-green with a much smaller total distance cost of 11+3+1 = 15.
Problem Formulation
Let's formally define the problem. Our dispatch algorithm will take as:
Input:
- A list of available drivers with their real-time locations.
- A list of passenger bookings with their respective pickup and dropoff locations.
- The maximum waiting time that a passenger is willing to wait for their driver to arrive.
and produce as:
Output:
- An assignment of drivers to passenger bookings. If no valid assignment is possible then return "NVA" (no vehicle available).
- Estimated arrival times for both the pickup and dropoff for each booking.
For this algorithm to work, you need to "manage state". This means you need to know exactly where all your drivers are, if they are available (without a passenger on board) and the pickup locations of your passengers. If you are running a modern ride share company, you should already have this data collected in real-time from your driver and passenger apps.
Worked Example
Consider the following scenario. It's 8 pm in Vancouver (just after dinner) and three booking requests come in at the same time. Three drivers are on the road and we don't want passengers to wait more than 15 minutes for a driver.
Bookings
| booking_id | pickup_location | dropoff_location |
|---|---|---|
| booking_001 | Brassneck Brewery (49.2657714, -123.1017201) |
3450 E Hastings St (49.2814623, -123.0292998) |
| booking_002 | Zakkushi on Denman (49.2912, -123.1384817) |
2083 Alma St (49.2688767, -123.1857463) |
| booking_003 | Granville Island Brewing (49.2709294, -123.13623) |
5251 Oak St (49.2385564, -123.1309102) |
Drivers
| driver_id | current_location | status |
|---|---|---|
| green | 704 W 6th Avenue (49.2615745, -123.1414875) |
FREE |
| blue | 5155 Victoria Drive (49.2378779, -123.0677532) |
FREE |
| purple | 401 Granville Street (49.2851193, -123.1164933) |
FREE |
We'll be framing our dispatch problem as a pickup and delivery route optimization problem with time windows, so we'll call the /pdp-long endpoint (docs).
Here's what we need to change.
Because it is 8 pm right now, we'll set "shift_start": "20:00" on each of the fleet objects (drivers).
Also, since we don't want any passenger to wait more than 15 minutes for a pickup, we'll set the time windows on the pickup object to "start": "20:00","end": "20:15". This way, if a driver cannot pick up a passenger within 15 minutes, the algorithm will return an "NVA" - no vehicle available.
Lastly, since we only want drivers to handle one booking at a time (no Uber Pool / Lyft Line style ride sharing), we need to set "load": 1 on the visit (booking) object and "capacity": 1 on the fleet (driver) object.
Here's what the full JSON request looks like:
Endpoint POST https://routing-engine.afi.io/pdp-long
Headers
Content-Type: application/json
access_token: YOUR_API_KEY (email sales@afi.io to get access)
Body
{
"fleet": {
"green": {
"start_location": {
"name": "green-start",
"lat": 49.2615745,
"lng": -123.1414875
},
"capacity": 1,
"shift_start": "20:00"
},
"blue": {
"start_location": {
"name": "blue-start",
"lat": 49.2378779,
"lng": -123.0677532
},
"capacity": 1,
"shift_start": "20:00"
},
"purple": {
"start_location": {
"name": "purple-start",
"lat": 49.2851193,
"lng": -123.1164933
},
"capacity": 1,
"shift_start": "20:00"
}
},
"visits": {
"booking_001": {
"pickup": {
"location": {
"name": "Brassneck Brewery",
"lat": 49.2657714,
"lng": -123.1017201
},
"start": "20:00",
"end": "20:15",
"duration": 1
},
"dropoff": {
"location": {
"name": "3450 E Hastings St",
"lat": 49.2814623,
"lng": -123.0292998
},
"duration": 1
},
"load": 1
},
"booking_002": {
"pickup": {
"location": {
"name": "Zakkushi on Denman",
"lat": 49.2912,
"lng": -123.1384817
},
"start": "20:00",
"end": "20:15",
"duration": 1
},
"dropoff": {
"location": {
"name": "2083 Alma St",
"lat": 49.2688767,
"lng": -123.1857463
},
"duration": 1
},
"load": 1
},
"booking_003": {
"pickup": {
"location": {
"name": "Granville Island Brewing",
"lat": 49.2709294,
"lng": -123.13623
},
"start": "20:00",
"end": "20:15",
"duration": 1
},
"dropoff": {
"location": {
"name": "5251 Oak St",
"lat": 49.2385564,
"lng": -123.1309102
},
"duration": 1
},
"load": 1
}
},
"options": {
"polylines": true
},
"cache": false
}This produces the following route solution (output). The pairings are contained in the output.solution object. Visually, here's what the solution looks like (map):
Dispatch Solution
| booking_id | driver_id | pickup_location | ETA |
|---|---|---|---|
| booking_003 | green | Granville Island Brewing (49.2709294, -123.13623) |
20:02 |
| booking_001 | blue | Brassneck Brewery (49.2657714, -123.1017201) |
20:07 |
| booking_002 | purple | Zakkushi on Denman (49.2912, -123.1384817) |
20:03 |
Congratulations! You've just built a basic but workable dispatch system. If you were the passenger that made booking_003, you'd be matched with driver green and could start tracking him on your app.
Before we go on, I need to explain the difference between the "stateful" state of the world (where your drivers are, which ones are available right now, which booking requests have just come in, etc.) and the "stateless" nature of the /pdp-long endpoint used in our dispatch system.
/pdp-long knows nothing about where everything is, how long you expect passengers to wait etc. You must take data from your stateful system (your real time database) and send it over to /pdp-long. Also, /pdp-long is stateless - for the same inputs, /pdp-long will always give the same output.
Trip Chaining
One of the hallmarks of modern dispatch systems is trip chaining. This happens when a new booking is assigned to a driver who is already on a trip. If you use Uber you might have gotten a "Your driver is completing a trip nearby." message. This is trip chaining in action.
It might be annoying for the passenger because it often results in longer wait times but it's great for Uber (and one of several psychological tricks the company uses to increase revenue) because it keeps the driver busy driving for Uber instead of taking a break and switching to Lyft.
Let's modify our example and add trip chaining to the dispatch algorithm.
To our three bookings, we'll add a fourth booking_004 with a pickup in the west side of Vancouver near where booking_002 ends.
We'll also add the constraint that driver purple has already been matched to booking_002. This is done by adding "type": ["driver-purple"] to both booking_002 and the driver purple. This is part of the routing engine's skill and types functionality. It acts as a hard constraint, forcing visits with a specific type to only be served by drivers with that same skill.
By adding "type": ["driver-purple"] we effectively force that booking to be served by driver purple, even if it may not be the most route-optimal way of doing things.
In practice, this doesn't always guarantee that the booking will be matched to the driver it was already assigned to. You may consider shift times, time windows, vehicle capacities and other constraints that may prevent the booking to be feasibly assigned to the driver.
Here's what the modified JSON looks like:
Endpoint POST https://routing-engine.afi.io/pdp-long
Headers
Content-Type: application/json
access_token: YOUR_API_KEY (email sales@afi.io to get access)
Body
{
"fleet": {
"green": {
"start_location": {
"name": "green-start",
"lat": 49.2615745,
"lng": -123.1414875,
"id": "green_start"
},
"capacity": 1,
"shift_start": "20:00"
},
"blue": {
"start_location": {
"name": "blue-start",
"lat": 49.2378779,
"lng": -123.0677532,
"id": "blue_start"
},
"capacity": 1,
"shift_start": "20:00"
},
"purple": {
"start_location": {
"name": "purple-start",
"lat": 49.2851193,
"lng": -123.1164933,
"id": "purple_start"
},
"capacity": 1,
"shift_start": "20:00",
"type": [
"driver-purple"
]
}
},
"visits": {
"booking_001": {
"pickup": {
"location": {
"name": "Brassneck Brewery",
"lat": 49.2657714,
"lng": -123.1017201
},
"start": "20:00",
"end": "20:15",
"duration": 1
},
"dropoff": {
"location": {
"name": "3450 E Hastings St",
"lat": 49.2814623,
"lng": -123.0292998
},
"duration": 1
},
"load": 1
},
"booking_002": {
"pickup": {
"location": {
"name": "Zakkushi on Denman",
"lat": 49.2912,
"lng": -123.1384817
},
"start": "20:00",
"end": "20:15",
"duration": 1
},
"dropoff": {
"location": {
"name": "2083 Alma St",
"lat": 49.2688767,
"lng": -123.1857463
},
"duration": 1
},
"load": 1,
"type": [
"driver-purple"
]
},
"booking_003": {
"pickup": {
"location": {
"name": "Granville Island Brewing",
"lat": 49.2709294,
"lng": -123.13623
},
"start": "20:00",
"end": "20:15",
"duration": 1
},
"dropoff": {
"location": {
"name": "5251 Oak St",
"lat": 49.2385564,
"lng": -123.1309102
},
"duration": 1
},
"load": 1
},
"booking_004": {
"pickup": {
"location": {
"name": "3755 W 6th Ave",
"lat": 49.2674138,
"lng": -123.1878527
},
"start": "20:00",
"end": "20:15",
"duration": 1
},
"dropoff": {
"location": {
"name": "Vancouver International Airport",
"lat": 49.1966913,
"lng": -123.183701
},
"duration": 1
},
"load": 1
}
},
"options": {
"polylines": true
},
"cache": false
}This produces a route solution (output) that chains booking_002 and booking_004 together (map). This works because booking_004 was scheduled for a 20:14 pickup, which is still within the 15 minute maximum wait time we've set i.e. start": "20:00","end": "20:15" .
The chaining is seen in the route solution (excerpt below) that pairs both the pickup of booking_004 right after the dropoff of booking_002.
{
"purple": [
... earlier visit data excluded
{
"location_id": "booking_002",
"location_name": "2083 Alma St",
"arrival_time": "20:12",
"finish_time": "20:13",
"type": "dropoff",
"load": {
"unit": 1
},
"duration": 1,
"distance": 4234,
"travel_mins": 8.47,
"waiting_mins": 0,
"working_mins": 9.47
},
{
"location_id": "booking_004",
"location_name": "3755 W 6th Ave",
"arrival_time": "20:14",
"finish_time": "20:15",
"type": "pickup",
"load": {
"unit": 1
},
"duration": 1,
"distance": 223,
"travel_mins": 0.45,
"waiting_mins": 0,
"working_mins": 1.45
},
{
"location_id": "booking_004",
"location_name": "Vancouver International Airport",
"arrival_time": "20:31",
"finish_time": "20:32",
"type": "dropoff",
"load": {
"unit": 1
},
"duration": 1,
"distance": 7872,
"travel_mins": 15.75,
"waiting_mins": 0,
"working_mins": 16.75
}
]
}If driver purple had already picked up the passenger from booking_002, you'd set the pickup location of booking_002 to be the real time location of the driver and set duration:0 on the pickup object so that the route's ETA is not affected.
Final Thoughts
So, now you know how a basic ride share dispatch algorithm works. This is just a starting point. The system we described here only attempts to minimize the overall distance traveled by the vehicle fleet. Production versions of Uber and Lyft's dispatch systems are much more complicated as they also take into account driver ratings, fairness (preferentially giving bookings to drivers who aren't earning as much) and revenue.
Also important (and maybe the topic of a future blog post) is the concept of "rematching", where drivers on the way to pick up passengers have bookings swapped post assignment to minimize overall travel time.
Afi Labs builds custom transportation and logistics management software. From route optimization, live tracking to proof of delivery and driver apps, we've got you covered!
đź‘‹ Say Hello!