Building an in-house card service at Eats | Coupang Engineering

When customers use the Eats app, they simply choose a menu and enter their address for food delivery right to their doorstep. However, in those fleeting moments, Eats performs complex calculations in the background using complex location technology. Here are some ways to do it:

• Calculation of delivery routes. Eats Delivery Partners (EDP) travel by motorbike, car, bicycle and on foot to find the optimal delivery route for each mode of transport respectively.
• Estimated time of arrival (ETA) calculation. Even on the same route, the ETA may differ significantly due to traffic or weather conditions. An accurate ETA helps us find the optimal delivery route
• Identify an optimal input for delivery. Customers can order food from a park or from a specific building. Large areas, such as an apartment complex, are called areas of interest (AOI). An important job is to identify the optimal entry point of the AOI and guide the EDP to the closest entry.

The goal of all the above calculations is to find an optimal route for EDP and make food delivery more efficient, in order to pursue a win-win CX.

While all of the mentioned card use cases were encountered at a basic level using third-party services, we encountered some issues and limitations when growing the Eats business rapidly.

• Ineffective. Third-party maps did not reliably provide accurate routing and ETAs. Additionally, we found that third-party maps often assigned PDEs to non-optimal routes or incorrect points of interest.
• Unstable. Using third-party cards results in high latency and long mean time to repair (MTTR). Since mapping services are critical to our business, these unstable performance issues have become detrimental to the customer experience.
• Not scalable. Reliance on third-party applications has also limited our business scalability. Requests per second (RPS) restrictions have limited our ability to quickly respond to growing customer orders.

To overcome the problems of third-party maps, we have created our own map services. Generally, map services are highly dependent on data, and internal map services are divided into 3 layers: online services layer, data layer, and data producer layer. We also leverage a machine learning platform to improve data accuracy.

A central element of the internal map is the route service, which is responsible for route planning, ETA and distance calculation, and more. The following sections detail the three key stages we went through to develop the route service.

During the first stage of the route service development, we focused on creating a system that could improve the accuracy of our ETA.

First, a routing engine was built to calculate the ETA. However, since we were starting from scratch, there was less data to work with and the results weren’t very accurate. To improve accuracy, an algorithm model is trained based on business features, such as historical EDP tracking data, vehicle type, delivery region information, etc.

Statistically, the result of the algorithm model and the routing engine was not bad. However, these models could not reflect real-time changes, such as traffic. Additionally, we saw some poor results due to distribution.

To improve ETA calculations and route planning, speed with traffic history is produced by data mining based on commercial data. The extracted speed is attached to the road segment and used to calculate the route weighting and ranking during planning.

Segment speed calculations

There are two methods to get speed from EDPs:

• Speed ​​calculated from distance. A segment is the smallest granularity of the route. A track is the delivery route of the EDP, and track points are a series of EDP location data for a given segment. The distance between two track points and the delta time of the two track points are downloaded. The speed accuracy depends on the delta time accuracy, which is achieved through the EDP application.
• Speed ​​downloaded by GPS from EDP. GPS speed is accurate when the EDP is traveling on a road with no tall buildings on either side. But if the EDP moves between tall buildings, the GPS signal is impacted and the downloaded speed is inaccurate.

We use a combination of these two speed calculation methods to obtain an accurate segment speed used for ETA calculation and route planning.

Map matching and noise filtering

To perform accurate speed calculations, we first map the EDP route using map matching, which converts geographic coordinates into a real-world road segment. Map matching helps us filter out inaccurate locations and find the target road segment.

After map matching, we preprocess the route for speed calculations by adding or filtering track points using point density:

• If the travel time between two points is too long, then the track is split into two sub-tracks.
• If the travel time between two points is too short for cars or motorbikes, the points are set as noise and are removed.
• If there are too few points in a track, the track is deleted.

For example, in the image below, there are paired EDP track points on three segments. The points marked by the circle and the ellipse are deleted because the travel time between them is too insignificant.

After noise filtering, we calculate the overall speed of the course. The detailed formula can be seen below, where V is the speed and Vxi is the speed between track points, calculated by the distance and time between point i and i+1. First, we calculate the average of Vi as the final speed over a segment. Then, to smooth out the gap between Vxi, we add more velocity data, denoted Vyj, to calculate the final velocity. We use these speeds to derive the duration of each segment, the duration of the final trip and the ETA.

If the point of interest (POI) is a building in a large apartment complex (AOI) with multiple entrances, we want to determine the optimal waypoint for the EDP to minimize delivery time, taking into account the mode of transportation of EDP. These nearby destination directions have a big impact on the entire Eats delivery scenario.

If the EDP delivers by car, the route should be planned to lead to a suitable parking space for the EDP. If there is more than one entry in the AOI, the route should be planned so that the waypoint leads to the closest entry to the POI. If the EDP delivers to a large fleet, the route from the EDP to the customer is as close as possible.

To find specific waypoints, we used the following methods:

• POI data. We use data from previous EDP deliveries, satellite images and other data to determine the best waypoint for EDP and improve ETA accuracy.
• Spatial index. We divided the AOI into small cells and built a spatial index per cell that can be quickly queried. Below is a park that we have divided into small cells. By placing the customer in a small cell, we can easily determine the nearest entrance as a waypoint for the EDP, thus reducing the delivery time.

Performance and cost

After switching to our internal routing service from third-party services, we saw the following achievements:

• Steering service P99 latency reduced by 70% (from 350ms to 100ms). After tracking optimization, P99 is less than 50 ms.
• The system scalability bottleneck has been resolved. Currently, the directions service handles 10 times more traffic than before, with P99 latency of less than 50ms.
• Engineering costs decreased by approximately $2 million per year.
• Business metrics, such as total delivery time, IT wait time for food, and operating costs all improved. User experience metrics have also seen improvements.

In this article, we’ve provided you with a quick introduction to the internal route service used in Eats. However, a mapping system is complex and consists of many subsystems, and there is still a lot of work to be done. We are continually evolving our flexible system to achieve design innovation and productivity for Eats and hope to share more updates in the future.

You are welcome to join us if you are interested in any of these complex issues, refer to our open positions.