What is the best way to go from point A to point B? For a large part of the human history, the answer to this question wouldn’t have required much effort. But the complex transportation networks of today have stimulated the need to develop sophisticated solutions to this problem. Let’s explore The Shortest Path Problem!
On one fine day in 1956, while shopping in the streets of Amsterdam, Edsger Dijkstra thought, what would be the shortest path between Rotterdam and Groningen. And in the next 20 minutes (as per his own estimate :p) the Dutch Mathematician came up with what we today know as the Dijkstra’s Shortest Path Algorithm. Now, whether or not did Dijkstra actually come up with the solution in 20 minutes is irrelevant, because his work paved the way for further development of the field of Operations Research (OR). The Shortest Path problem is the most fundamental problem in OR. In fact, it is core to transportation problems like Traffic Assignment (TA), Traveling Salesman Problem (TSP), and Vehicle Routing Problem (VRP), which we will discuss on another blog. Beyond its application in transportation networks, the Shortest Path Algorithm has found its use in telecommunication network, robotics and computer infrastructure. Let’s look at what Dijsktra came up with.
Given an origin node – r and a destination –s, the objective of the problem is to determine the shortest path between the two. Dijkstra’s solution begins by setting cost and predecessor labels for all the nodes in the network. The cost label g(n) for any node n defines the length of the shortest path from the origin node r to this node n, whereas the predecessor label pr(n) defines the predecessor node for node n in this shortest path from r to n. The solution is initialized by setting g(n) = ထ and pr(n) = undefined, for all nodes except the origin node, for which g(r) = 0 and pr(r) = r. In addition a set of open nodes (a set with all the nodes) and closed nodes (an empty set) is defined. The solution then proceeds by first setting the origin node as the current node – i and visiting all the nodes directly connected to this node. At this point the current node is added into the set of closed nodes. For any node j directly connected to the current node, we compare f(i)+d(i,j) with f(j), i.e. the length of the shortest path from origin to node j via node i is compared with previously recorded value of the shortest path from origin to node j. If the shortest path via node i is shorter than previously recorded shortest path, then f(j) is replaced with f(i) + d(i,j) and pr(j) is set as i. Once all the nodes adjacent to the current node are visited, the node with smallest cost label that is still in the set of open nodes is selected as the current node. Recall, a node is sent from open to closed set if it has been selected as current node. This process is repeated until the destination node has been selected as the current node and sent into the set of closed nodes, at which point we have identified f(s) and pr(s). This completes the Dijkstra’s algorithm.
While the Dijksta’s solution is indeed very neat, it is not the most efficient one. In the solution described above, the solution uses a cost label f(n) as the distance of the shortest path from origin node to node n, thus completely ignoring the fact that we actually need to reach the destination node s. This leads to solution exploring nodes in the network which are far away from the destination and would never be in the shortest path. In A-Star algorithm, the cost label is instead defined as the length of the shortest path from origin node to destination node via node n. This difference is key as the A-star solution explores the nodes towards the destination. One can imagine the search space of Dijkstra as circular, while A-Star would have an elliptical search space. More on this in the results discussed below.
The Shortest Path Problem is more generally known as the Least Cost Path Problem, because beyond finding the shortest path, it can also be used to find the fastest path (which is what we mostly look for when we travel) and more recently it has been used to find the eco-friendliest path. The tailpipe emission are largely U-shaped curve with respect to the vehicle speed, i.e. there is an optimal speed range that minimizes the emissions. Speeds below and above this range produce more tailpipe emissions. Early research in the context of eco-friendly paths minimized fuel consumption instead of tailpipe emissions. These studies assumed that emissions are proportional to the amount of fuel consumed, and hence minimizing fuel consumed would therefore minimize emissions. While this assumption is sound, vehicle dynamics such as acceleration and braking significantly complicate the matter as different emissions are emitted under different vehicle operations. However, for the purpose of this blog we will stick to assuming an eco-driven path to be the one that minimizes fuel consumed.
Below is a shortest path dashboard that I developed using JavaScript. We have a randomly generated grid-like network of 2500 nodes and 9800 links. The distance between any two connected nodes is about 100 meters (not exactly 100 m, but 100 m + some randomness). An additional feature of this network is that like in a typical urban network, links closer to the center have lower speeds, emulating the effect of congestion. In fact the highest speed in the network is 70 km/hr at the edge and the lowest speed is 20 km/hr at the center. This dashboard allows you to pick your choice of origin and destination and returns your choice of least cost path between the two – shortest, fastest and/or the eco-driven path. You can also explore the difference between the Dijkstra’s algorithm and the A-Star algorithm by observing the explored nodes in the network represented by the enlarged light shaded nodes. As discussed above, the explored nodes in Dijkstra form a circular figure, while in A-Star this would be elliptical.
Difference between Dijkstra’s and A-Star algorithm
As discussed above, in Dijkstra’s algorithm, the solution procedure uses a cost label that ignores the fact that we actually need to reach the destination node. This leads to Dijkstra exploring nodes in the network which would never be in the shortest path. On the other hand, in A-Star algorithm, the cost label is defined such that the solution explores the nodes towards the destination. This results in a circular search space for Dijkstra while an elliptical search space for A-Star. One can observe this difference by selecting the node closest to the center as the origin and one of the nodes close to the vertex as the destination. With this pair of origin and destination nodes, Dijkstra explored 1655 nodes, while the A-Star in comparison explored only 234 nodes which is strikingly 85% less.
Comparing different least cost paths
Now as discussed above, the shortest path is more generally known as least cost, since least cost could signify shortest, fastest or eco-driven path, or for that matter any objective that is minimized. In fact, it is totally possible that the shortest, fastest and eco-driven paths are different. Selecting two opposite vertex for the pair of origin and destination, we create a situation wherein the shortest path would be along the diagonal through the congested links closer to the center. The fastest path on the other hand would like to avoid the congestion, and in fact for this pair of origin and destination, the fastest path moves close to the edge. The path with least fuel consumption, in this case, avoids both of these routes, finding a route in between these two extremes. For the chosen pair of origin and destination, the shortest path is 11.6% shorter than the fastest path and 1.5% shorter than eco-driven path; the fastest path is 23% faster than the shortest one and 14% faster than the eco-driven path; and finally, the eco-driven path consumes 1.5% less fuel than the shortest path and 8.25% less compared to the fastest path. Overall, it is important to see that the shortest, fastest and eco-driven paths can be different.
What next?
In this blog we explored the least cost path for a single vehicle traveling between origin to destination, hence we ignored the effect of additional vehicle on the travel time of a link. But when there are multiple vehicles moving between different pairs of origin and destination, we account for deterioration in travel time of the link. In fact, there is an equilibrium that is established in transportation network, known as Traffic Assignment. The shortest path algorithm is fundamental to designing the solution to Traffic Assignment. We will explore selfish and selfless traffic equilibrium on our hypothetical network we created in this blog in upcoming blogs.
Notes for Nerds
Dijkstra’s original paper: Dijkstra (1959)
More on eco-routing: Ericsson et al. (2006), Ahn & Rakha (2008), Nie & Li (2013)
I used the fuel consumption model from here: Scora et al. (2015)