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.
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.
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.
Share your thoughts
Perseverance Rover: Humanity’s newest feat
February 19th, 2021 marks a new historical event in the space exploration journey, as NASA scientists rejoice.
NASA’s 2020 Mars mission successfully landed on Mars. This mission includes the Perseverance Rover along with other experiments.
While descending to touch down on the red planet, we got a close-up picture of the Perseverance rover, the first-ever high-resolution color image to be sent back by the Hazard Cameras that is most likely to become a classic photograph in the history of spaceflight.
A 360° rotation of its mast allowed the Mastcam-Z instrument to capture its first panorama, and we also got the first-ever audio recording from the red planet thanks to a microphone on the rover.
The camera system covered the whole landing process, showing the intense ride and the so-called « seven minutes of terror » descent sequence.
“Touchdown confirmed! Perseverance is safely on the surface of Mars, ready to begin seeking the signs of past life.” Said NASA engineer, Swati Mohan, during the live stream of the landing.
This landing is a considerable achievement of engineering that took multiple years to attain and was one of the main difficulties of the mission. As a matter of fact, because Mars’s air is so thin, it was more difficult to slow the spacecraft while descending, and it required a parachute and rockets, among other equipment.
Another challenge that the rover faced was the dangerous terrain it was headed to. Jezero Crater, the new home to the Perseverance Rover, was riskier than previous missions, as it presents deep pits, high cliffs, and big rocks making it harder for the rover to touch down.
However, NASA managed to design new pieces that allowed Perseverance to scan the surface and navigate around any obstacles which was a huge success.
The main goal of this mission is to hunt for the remnants of life and to study the Martian rocks up to 3.8 billion years old.
With this new source of data, the knowledge about our neighboring planet will pave the way to the future, when humans will set foot on the Martian soil.