It all began with Dijkstra’s algorithm
Algorithms are everywhere. They power our social media feeds, influence our shopping habits, determine our online search results, predict market fluctuations and can even find us an ideal life partner. Today, they are the bread and butter of business success. At ORTEC, we leverage algorithms to solve a diversity of problems for our clients. This blog posts explores how we use algorithms to create optimal transport routes – a must-have for logistics companies. Let’s take a look at some of the mathematical breakthroughs that enable us to drive business optimization.
From A to B
Back in the 1950s, Dutch Computer Scientist Edsger Dijkstra conceived an algorithm to find the fastest path between two points in a network. These points could represent a number of things, including points in a road network. Suppose to want to go to point A from point B – what is the fastest path? Dijkstra’s algorithm can help you find that path by assigning some initial distance values and improving them step by step. This is handy if you have a simple road network in a small city, but what about cases where you have to visit multiple locations spread across the country? Suppose you have a fleet of trucks and you want to travel to 1000 different addresses, what is the optimal order of the places you want to visit and what would the travel times be? These are challenging questions to answer, even for fast computers.
In fact, calculating distances for complex and large road networks takes a long time. There are many hundreds of millions of roads and intersections in the world. The larger the road network, the harder it is to run Dijkstra’s algorithm. We needed to find a more robust approach to solve the complex problems we see in practice.
Pre-processing data to manage complexity
To overcome this overwhelming complexity, we analyze the network and extract key information that allows us to generate optimal routes more quickly, they call this pre-processing – a technique that academics have built on for decades. We examine the network closely and exploit structures that are typically found in road networks. For instance, we know that some roads within a network are very local. An intersection in Brussels is extremely unlikely to be connected by a single straight road with one in Moscow. Similarly, there is an inherent hierarchy to the roads of the world. We know that some roads only cross a neighbourhood while highways connect different countries. The latter are much more important for long routes. Our software can detect the nuances of this hierarchy automatically and insert shortcuts into the network to make finding and traveling across the most important roads much easier.
Leave a Comment
You must be logged in to post a comment.
