Introduction

Route optimization is very useful nowadays. The route suggested by your GPS is made based on different factors and is using data science to improve your trip by saving you time and effort. In this article, we’re going to talk about a specific experience of a route optimization program made for an Asian delivery service called GOGOVAN, where the idea came from, and how it started.

What is GOGOVAN?

Every day, GOGOVAN drivers arrive at warehouses across Asia to pick up thousands of orders that their business partners have asked them to deliver to their clients. These orders can be a range of things — from that long-awaited new phone to an anniversary present that was ordered at the last minute. All of them will be of different sizes, shapes, and weights. For each one of them, there will be a person waiting and hoping this time the courier company gets there on time… This is why at GOGOVAN, they do everything in their power to ensure smooth and timely deliveries with a quality of service that will amaze customers. Every delivery route is carefully planned manually and double-checked by the Operations Team, to make sure it never fails.

The problem they were facing

In the past, GOGOVAN’s Operations Team had to manually sort out the delivery routes, usually on the morning of pickup, and ensure they meet all the delivery time requirements for that day. As you might imagine, that is not a particularly exciting nor easy task. It took one person approximately 1 hour to create a sub-optimal route for 100 waypoints. For requests bigger than that, this time grew exponentially. GOGOVAN instantly realized that this process was simply begging for some automation.We feel sorry for the Operations Team who had to do such mundane work each early morning, but when the order volume grew, that task was slowly becoming mission impossible. The delivery service company saw it as an opportunity to develop a cutting-edge technology that will become a core component of GOGOVAN’s Data Science stack.

How did the solution start?

GOGOVAN is very client and driver-centric. Consequently, they always try to analyze a problem from their perspectives in order to understand how the solution could impact and benefit both. After a lot of brainstorming, these are the goals they came up with:

• All orders need to be delivered on time.
• Ensure drivers are not rushed to make it on time by using buffer times and real-time distance.
• Save fuel by reducing the distance driven.
• Minimize idle time for drivers — no one likes waiting with a trunk full of packages.
• Improve vehicle utilization.
• Fully automate the process.
• The algorithm needs to be growing with the problem.

They realized that the problem they are facing is widely known as Vehicle Routing Problem (VRP):
VRP can be described as the problem of creating a set of optimal routes from one, or many, depots to multiple customers, subject to a set of constraints. The objective is to deliver goods to all customers, at the same time minimizing the cost of the routes and the number of vehicles.

The Solution

With VRP being a widely recognized problem, there are indeed a lot of companies out there who seem to be tackling the problem. However, GOGOVAN somehow did not feel satisfied with previous solutions… They created their own with the help of the folks at Google who spent months coding all the different algorithms they wanted to test. They built their tool of Route Optimization and it looks like this:

The volume of orders submitted to Route Optimizer quickly increased from 500 items per warehouse to more than 1000. The algorithm’s runtime and memory usage jumped incredibly quickly — from 1 minute and 500 MB to 10 minutes and 5 GB. As they tested it for higher and higher volumes, they finally reached the maximum — for 2000 waypoints the module used up 25GB of RAM. They used a renowned clustering algorithm — DBSCAN. What they have is a state-of-the-art method that groups together geographical points. However, it has its downside: each cluster has to have the same radius. With the combination of the operations know-how, data science and research expertise, large volumes of data, and open-source state-of-the-art contributions, they arrived at a robust in-house solution that:

• Is more up-to-date, performant, and has customizable algorithms and iteration logic.
• Is cheaper, more efficient, and more scalable.
• Allows developing tangible intellectual property assets and building a competitive advantage around it.

Conclusion

In this article, we presented an approach to the Capacitated Vehicle Routing Problem with Time Windows for a large number of waypoints (up to 5000). By using a recursive-DBSCAN method GOGOVAN was able to significantly reduce runtimes and memory usage while maintaining a similar quality of results as in the baseline Google Optimization Tools method. The algorithm was of great help to the Operations team reducing hours of mundane manual work to a few minutes of CPU time. GOGOVAN decided to be a leader in the field by not using a BlackBox solution but developing its own.