Requirements of a cab aggregator
A cab aggregator takes a person in a cab from a pickup point to a destination. Uber, Ola and Lyft are examples.
A person books a cab on the phone and sees a price. On accepting it, the request goes out to nearby cabs, from a smaller radius to a larger one, and one of them accepts. The cab moves from its location A to the pickup B, and then to the destination C.
Food delivery picks up only from restaurants and drops at addresses already in the profile. A cab picks up and drops anywhere on the map, so it is the most complex case.
The core requirements:
- Pricing, calculated in real time from who the customer is, the pickup and the drop.
- Surge pricing. When demand is more than supply the price goes up, dynamically.
- Ride matching with a nearby driver.
- Driver location updates, which feed the ride matching.
- Estimated time of arrival, which decides the next ride a driver picks up.
Profile creation, driver insurance and reviews are not core.
Ride Matching
Ride matching finds a nearby driver for a user who wants a ride from a source to a destination.
The world map is split into squares with a side of one kilometer, because a person does not walk more than one kilometer. Each region holds its demand: the number of interested customers divided by the number of drivers.
The supply for a square is an educated guess: all the drivers in the three by three block around it, which is nine squares. A smarter guess takes more time, and the customer drops off. The higher the demand, the higher the price.
Ride matching optimizes several factors: the driver wants to keep driving and earn, and the customer wants to reach quickly. Proximity is defined in terms of time, not distance, because a river or a road block sends a nearby driver all the way around. A driver 15 minutes away is likely to be cancelled.
Calling Google Maps for every request costs a lot, so the estimated time of arrival is built in-house.
Matching Drivers with Live Rides
A driver on a live ride is matched to a new pickup when the time to finish the current ride and then reach the pickup is within the threshold.
Ride matching for available drivers:
- The drivers in the nine squares around the pickup are queried.
- Each driver whose estimated time of arrival is within a threshold, such as five minutes, is sent the request.
- If none accepts, the size of the square is increased. A driver accepts, or the ETA is too high and the ride is cancelled.
A driver on a ride is a candidate when the ETA from current location to destination, plus the ETA from destination to pickup, is less than or equal to the threshold.
The first ETA is constantly calculated and stored for every driver, so it is an order one computation. The second is calculated on the fly, and running it for 500 drivers is expensive. Two filters apply: the driver's time to reach the destination is within the threshold, and the destination is in the squares near the pickup.