Using ant colony optimization for route planning through Klang Valley
Due to the lockdown ecommerce has boomed and understandably many merchants are struggling to cope with the extreme increase in demand. Companies have had to scale their fulfillment processes to many times their regular demand. They aren’t optimized and definitely have not been tested at scale.
One of the perceived bottlenecks was thought to be logistics. My guess is that processes before it are the greater limitation. Nevertheless, I’ve been asked a couple of times about route planning, and using “machine learning” to optimize it.
I recommended using an off-the-shelf solution. Route planning is a well studied problem and there are plenty of alternatives. The benefit of building it in-house comes from integration with existing systems. That isn’t immediately required and there are insufficient resources to tackle it at the moment.
I did, however, want to look into how feasible it would be for a small team to execute. After all, the traveling salesman problem is infamous and ant colony optimization is well known for producing a good solution. So, I decided to implement an MVP that would calculate the optimal delivery route through Klang Valley. At the same time, I would also implement nearest neighbor and compare the results.
The MVP resulted in an ~18% improvement compared to nearest neighbor – a significant improvement.
The entire experiment, including writing this blog post, took about two days. It has no recurring costs. It also required only quite basic programming: uploading a file, nearest neighbor algorithm, using a gem, writing to a file. It does have limitations but gets most of the way there with minimal investment. Any organization where the routing is the bottleneck, and available solutions are unsuitable, could do this.
For an even easier starting point, organizations could consider implementing just the nearest neighbor and allowing their users to fine tune the route using a drag and drop list.
Routing in general, and ACO specifically, definitely aren’t arcane and inacessible tools. They could be easily, and cheaply, implemented in any organization that could benefit from them.
Knowing what’s possible
The bigger issue seems to be that IT teams of smaller organizations are often missing a very underrated but very valuable skill: knowing what’s possible. “Knowing what’s possible” has two meanings.
First is the actual knowledge of tools that exist and how much effort it takes to use them.
From a technical perspective, I knew that geocoding, Google Distance Matrix, PostGIS, and ACO all existed and had either used them previously, or read enough to be able to quickly evaluate whether it would be feasible to use them.
“Knowing what’s possible” also includes either knowing about off-the-shelf solutions or being able to tell the likelihood that one exists. Even though I have ever looked up routing software, I was certain that there was plenty of options to choose from.
Having a team member with this type of experience, or at least ambition, is crucial. It speeds up the IT strategy and moves it beyond building everything in-house and constantly re-inventing the wheel.
Second is knowing what type of problem is suitable for an IT solution. It’s very succinctly described in this XKCD:
The senior team-member must be able to communicate what is and isn’t suitable to the users.
The most effective way I’ve found for this is with real examples of what’s being discussed, rather than hypotheticals. “Detecting a bird is not possible, but we can tell when and where the picture was taken, make of the camera and which way the person was facing.”
It’s also pointless to explain the technical detail as to why things aren’t possible. That doesn’t help the user or move the discussion along. The more important aspect is the consequences. “We can’t detect birds because image recognition is difficult and we’d have to build our own models” is useless. “Detecting things in pictures is expensive and slow” is what actually matters.
Communicating what is possible, on the other hand, is even more important. Users often aren’t aware of all that tech can accomplish. For instance, explaining that information could be moved between systems would be useful. The technical details on how things are done often are not.
Or send me feedback. It will take less than 20 seconds.