> ## Content Index > Fetch the complete content index at: https://blog.afi.io/llms.txt > Use this file to discover other available public pages before exploring further. # Using route optimization to build a ride share dispatch algorithm - URL: https://blog.afi.io/blog/using-route-optimization-to-build-a-ride-share-dispatch-algorithm/ - Published: 2022-10-25T17:29:10.000Z - Updated: 2025-08-15T18:27:50.000Z - Description: How to use a Route Optimization API to Build a Ride Share Dispatch System - Author: Afian Anwar - Tags: tech It's 2022 and you just raised a bunch of money to start a ride-share company [to compete with Uber and Lyft](https://www.wsj.com/articles/meet-the-startup-aiming-to-take-on-uber-and-lyft-11657620001?ref=blog.afi.io). 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](https://www.wsj.com/podcasts/your-money-matters/why-gas-prices-are-climbing-again-after-months-of-declines/bbe44e9e-92ed-40a1-b3a0-8d78db59be13?mod=Searchresults%5Fpos6&page=1&ref=blog.afi.io). 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." ![](https://storage.ghost.io/c/c6/4d/c64da7e8-63a6-4cff-acdc-2782a6ebc377/content/images/2022/10/Screen-Shot-2022-10-29-at-8.42.16-AM.png) When you book a ride, Uber calls a dispatch algorithm on the backend. 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](https://afi.io/routing%5Fengine?ref=blog.afi.io) as our route optimization API ([docs](https://afi-labs.gitbook.io/afi-routing-engine/-LtOZ1a-Ritq-iWagVx-/?ref=blog.afi.io)). **It's free to use for small-scale testing (reach out to** [**sales@afi.io**](mailto: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. ![](https://storage.ghost.io/c/c6/4d/c64da7e8-63a6-4cff-acdc-2782a6ebc377/content/images/2022/10/diagram3.png) Scenario 1: 3 passengers and 3 drivers. Grids are 1 km x 1 km unit squares. 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. ![](https://storage.ghost.io/c/c6/4d/c64da7e8-63a6-4cff-acdc-2782a6ebc377/content/images/2022/10/diagram2.png) Suboptimal "greedy" solution with a total distance cost of 19 km. 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. ![](https://storage.ghost.io/c/c6/4d/c64da7e8-63a6-4cff-acdc-2782a6ebc377/content/images/2022/10/diagram1.png) Optimal "route optimized" solution with a total distance cost of 15 km. ### Problem Formulation Let's formally define the problem. Our dispatch algorithm will take as: **Input:** 1. A list of available drivers with their real-time locations. 2. A list of passenger bookings with their respective pickup and dropoff locations. 3. The maximum waiting time that a passenger is willing to wait for their driver to arrive. and produce as: **Output:** 1. An assignment of drivers to passenger bookings. If no valid assignment is possible then return "NVA" (no vehicle available). 2. 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](https://afi-labs.gitbook.io/afi-routing-engine/-LtOZ1a-Ritq-iWagVx-/pdp-endpoint/quickstart?ref=blog.afi.io)). 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](https://routing-engine.afi.io/pdp-long?ref=blog.afi.io) **Headers** Content-Type: *application/json* access\_token: *YOUR\_API\_KEY* (email [sales@afi.io](mailto:sales@afi.io) to get access) **Body** ```JSON { "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](https://routing-engine.afi.io/jobs/7267e04f-77a9-4d22-b495-4a0b40c4d1dd?ref=blog.afi.io)). The pairings are contained in the `output.solution` object. Visually, here's what the solution looks like ([map](https://map.afi.io/jobs/7267e04f-77a9-4d22-b495-4a0b40c4d1dd?endpoint=https://routing-engine.afi.io&ref=blog.afi.io)): ![](https://storage.ghost.io/c/c6/4d/c64da7e8-63a6-4cff-acdc-2782a6ebc377/content/images/2022/10/Screen-Shot-2022-10-25-at-10.26.03-AM.png) The dispatch solution visualized **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](https://www.nytimes.com/interactive/2017/04/02/technology/uber-drivers-psychological-tricks.html?ref=blog.afi.io) the company uses to increase revenue) because it keeps the driver busy driving for Uber instead of taking a break and switching to Lyft. ![](https://storage.ghost.io/c/c6/4d/c64da7e8-63a6-4cff-acdc-2782a6ebc377/content/images/2022/11/Screen-Shot-2022-11-29-at-5.01.21-AM.png) Trip chaining pairs a booking that's about to end with a new one nearby. 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](https://afi-labs.gitbook.io/afi-routing-engine/-LtOZ1a-Ritq-iWagVx-/vrp-endpoint/visits?ref=blog.afi.io). 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](https://routing-engine.afi.io/pdp-long?ref=blog.afi.io) **Headers** Content-Type: *application/json* access\_token: *YOUR\_API\_KEY* (email [sales@afi.io](mailto:sales@afi.io) to get access) **Body** ```JSON { "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](https://routing-engine.afi.io/jobs/df13fa71-3222-4248-ad9c-7ec91ab97d8d?ref=blog.afi.io)) that chains `booking_002` and `booking_004` together ([map](https://map.afi.io/jobs/df13fa71-3222-4248-ad9c-7ec91ab97d8d?endpoint=https://routing-engine.afi.io&ref=blog.afi.io)). 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"` . ![](https://storage.ghost.io/c/c6/4d/c64da7e8-63a6-4cff-acdc-2782a6ebc377/content/images/2022/10/Screen-Shot-2022-10-28-at-4.02.46-AM.png) Trip chaining on booking\_002 with booking\_004 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`. ```JSON { "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](https://www.afi.io/?ref=blog.afi.io) 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!](https://yourls.afi.io/newcontact?ref=blog.afi.io) 👋 **As always, if you have any questions or suggestions for me, please** [**reach out**](https://yourls.afi.io/newcontact?ref=blog.afi.io) **or** [**say hello on LinkedIn**](https://www.linkedin.com/in/afian-anwar-a023b143/?ref=the-afi-labs-blog)**.**