Alternate route/Nearby suggestions where direct routes are not available

Nearby search suggestions

Scenario:

• During peak season on any travel-related e-commerce platform customer faces the problem of not finding the travel options for desired locations. This situation is typically caused by increased demand. This problem has existed for a while now and we at redBus have developed a nearby search engine to assist customers in discovering nearby routes to opted locations. It helps suggest the best nearby route options when the desired route isn’t an option. The competent and steadfast recommended alternate source or destination will always be in the configured range.

Solution & Implementation:

• Our approach to the search engine algorithm involves utilising high-performance data stores, intelligent lookup logic, and efficient tech stacks.

System architecture and flow

Step 1 : Lookup for possible alternatives

• As demonstrated in the figure above, the Inventory master map will perform the initial lookup for any input query to the engine. Combining location intelligence and real-time inventory data leads to the construction of the inventory map. For a specified range, this step will do a series of spatial queries around the source and destination to get possible alternate routes. The alternate route’s rank and distance from the original source or destination will determine the accuracy of the suggestion.
• Here the rank of routes is decided based on a few decision parameters. The weight given to each parameter determines the performance score, which acts as a rank. From the result set, a configured number of routes will be extracted and sent to the next layer.
• The cost-effectiveness and accuracy of these queries make them ideal for this operation. Below is the plot of p95(in ms) for spatial lookup queries. For each query it scans through millions of routes(real time, not cached) and with that it marginally takes 3 milliseconds to ascertain possible alternatives from the above step(this includes sorting as well).

p95 for Alternate routes lookup queries

Step 2. Inventory meta info lookup:

• After that, these routes will be mapped into the route meta-store so that, depending on the date of journey, route-specific attributes such as availability, pricing etc. can be attached. Some of the routes in this layer will be filtered according to established business rules.. This layer offers extremely effective real-time route-specific information lookup.

Step 3. Sorting and processing:

• Following the previous phase, alternative routes with various combinations will be combined and sorted according to provided parameters. The engine will attach the tags for optimal route suggestions. Finally, each route’s accurate ad hoc road distance and additional travel time are determined.

For any query to search engine, below is p95 for latency for fully optimal sorted route suggestions(1 week plot).

Alternate suggestions p95 latency plot

Outcomes :

Below picture shows how well this discovery engine produces results on user interface.

Example results for few cases.

Final Thoughts:

Much engineering work has been done to achieve the accuracy and production standards mentioned above. This discovery engine leveraged tech stacks like Erlang/OTP, MySql, SolR, Redis, DalmatnerDb, Grafana and many more. To keep this article more focused, several technological and implementation elements have been purposefully omitted. Many thanks for your time. Be part of the redBus community for more exciting tech crack stuffs like this!