Options and tools for finding the shortest route.
Solving the optimization problem has been continuously developed for such a period of time. At the very beginning, as the first well-known approach, the so-called simplex method was introduced in the mid of 19th century. Later, many optimization methods were deliberately published and widely accepted.
In amongst, finding the shortest path is one of the most popular methodology involved in the optimization field. This writing aims at providing not only the general idea but also some useful tools in enhancing the shortest path. Specifically, the widely popular example from the American car association will be employed as a pictorial problem in order to enable the better understanding of the concept and the efficiency of each tool to be used. The objective of the mentioned problem is to find the shortest route from Birmingham (B’ham) to Virginia beach (Va Bch). Duration to be taken for travelling along each particular route is already depicted in the following picture. As can be carefully noticed, the problem gives us the travelling duration. Hence, the shortest route in this problem is the one with the lowest going time.
Two different approaches namely the linear programing and the Dijkstra algorithm will be applied to unravel this challenge. In the first attempt, as a linear programing, we are going to transform all given information into both the objective function and constraints. Eventually, we optimize them by utilizing both Excel solver and lpsolve library of R-programming as preferable alternatives. Meanwhile, in our second endeavor, the opensource graph database called Neo4j is our chosen tool for solving this problem by exploiting the Dijkstra algorithm.
Linear Programing Approach
In this approach, we need to formulate the decision variables and use them to come up with the objective function and constraints as mentioned. Basically, our goal is to indicate the shortest route from Birmingham to Virginia Beach. On the other word, we need to verify whether each specific path is a composition of the shortest route or not. Therefore, decision variables should represent each path.
The possible values of each decision variable are 0 and 1. Particularly, the value of the decision variable equals to 1 when the shortest route from Birmingham to Virginia Beach consists of this corresponding path and vi versa. For instance, the value of xn is 1 when xn is a composition of the shortest route. In the meantime, the value of xn is 0 when xn is not a part of the shortest route. Additionally, when the specific path is selected to be a part of the shortest route, the duration taken must be logically multiplied as its coefficient. As a consequence, the objective function of this linear programing problem is mathematically demonstrated as followings.
To generate our constraints, obviously, apart from the starting point (e.g. Birmingham) and the destination (e.g. Virginia Beach), all other nodes (cities) must be one of two possible scenarios, specifically whether the shortest route passes the node or not. Regardless what the case is, the summation of all input and output paths attached to the node ought to be zero since they are not the departure or destination node. On the other hand, as the departing and arrival node, this summation becomes -1 and 1 respectively. (let us assume that the values of minus one and one correspondingly represent outbound from and inbound to the interested node.) Finally, we have derived our constraints as per discussed.
These constraints can be written in terms of the cross product of a matrix as followings.
Up to this point, we have formulated all necessary inputs. Now let’s use the lpSolve library of R-programming to get the answer.
- Import the library
```{r}
# Import the lpSolve library
library(lpSolve)
```2. Use the formulated cross product of the matrix to finish the code
```{r}
# Formulate the objective function and constraints# The Objective function
# Orderly set the coefficient of each decision variable in the objective function
f.obj<-c(2.5,3,1.7,2.5,1.7,2.8,2,1.5,2,5,3,4.7,1.5,2.3,2,1.1,3.3,2.7)# Constraints must be written in the cross product format
f.con<-matrix(c(-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,1,1,0,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,1,0,0,-1,-1,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,-1,-1,0,0,0,0,0,0,0,0,
0,0,0,0,0,1,1,0,1,0,-1,-1,0,0,0,0,0,0,
0,0,0,0,0,0,0,1,0,0,0,0,-1,-1,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,1,0,1,0,-1,-1,0,0,
0,0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,-1,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,-1,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1), nrow = 11, byrow=TRUE)# Set the direction
f.dir<-c("==","==","==","==","==","==","==","==","==","==","==")# Set right hand side
f.rhs<-c(-1,0,0,0,0,0,0,0,0,0,1)
```
3. Find the optimized value
```{r}
# The optimized value
# Please change "min" to "max" if it needs to do so.
lp("min",f.obj,f.con,f.dir,f.rhs)
```
The result indicates that the shortest route (duration) from Birmingham to Virginia Beach is 11.5 hours.
4. Find the values of all decision variables
```{r}
lp("min",f.obj,f.con,f.dir,f.rhs)$solution
```
The result illustrates that the values of x1, x4, x8, x14 and x18 are one while all other decision variables have a value of zero. This means these 5 decision variables are a composition of the shortest route from Birmingham to Virginia Beach as shown.
5. Find the sensitivity
```{r}
# Sensitivities
lp("min",f.obj,f.con,f.dir,f.rhs,compute.sens = TRUE)$sens.coef.from
lp("min",f.obj,f.con,f.dir,f.rhs,compute.sens = TRUE)$sens.coef.to
lp("min",f.obj,f.con,f.dir,f.rhs,compute.sens = TRUE)$duals
lp("min",f.obj,f.con,f.dir,f.rhs,compute.sens = TRUE)$duals.from
lp("min",f.obj,f.con,f.dir,f.rhs,compute.sens = TRUE)$duals.to
```
In summary, the output demonstrates that the shortest route from Birmingham to Virginia Beach is the one via Atlanta-G’ville-Charl-Raleigh with the duration taken of 11.5 hours.
Personally, the advantages of using this library to solve the optimization problem are as followings. Firstly, R is the opensource programming. Apart from legally using without any charge, its feature will be incessantly improved. Secondly, it is relatively compatible with data stored in the database compared with using spreadsheet as solving equipment. Finally, the fewer steps are required to get the task done especially when the problem becomes more complex or the amount of input data turns very tremendous. Nevertheless, it requires coding.
The other helpful method to solve the optimization problem is to use Excel solver. The procedure begins with all decision variables. The picture below illustrates each decision variable with its beginning and ending point as well as the corresponding duration taken. The column of C presently remains blank. This will be filled later by the solver. Likewise, the value in this column is able to be merely zero or one depending on whether the corresponding path is a part of the optimized shortest route or not.
The solver parameters are set as followings.
Next, let us investigate the formula of our objective function and constraints. Similarly, as can be noticed from the column of N, apart from the departure and destination nodes which the summation of all inputs and outputs equals to -1 and 1 respectively, other nodes must have this value remains zero regardless the shortest path will pass them or not.
Completely, the solver gives us the same result. The shortest route from Birmingham to Virginia Beach is the one with x1, x4, x8, x14 and x18.
Dijkstra Algorithm Approach
A completed description of how does Dijkstra algorithm work is not our main purpose in this document. Nevertheless, for better understanding, its brief introduction will be shown as followings. According to this algorithm, we are going to start with where our origin (i.e. B’ham) can directly reach. We indicate its corresponding cost (time taken from B’ham) and finally left all remaining as the infinity.
Among three nodes that are able to be directly achieved from B’ham, the lowest cost results from going to Atlanta, we select it and redo the process again.
Up to this point, some readers might have the particular questions. Firstly, what is the explanation for having the value of 3B’ham instead of 1.7Atlanta at the column of Chatt. The reason is because our starting point is B’ham, therefore, to reach Chatt via Atlanta requires 4.2 (2.5 + 1.7) hours. From B’ham, we can directly reach Chatt with the time taken of 3 hours. This is definitely better than going to Chatt via Atlanta with the time taken of 4.2 hours. Secondly, what is the clarification for the value of 5Atlanta instead of 2.5Atlanta at the column of G’ville. Again, our problem is to find the shortest route from B’ham. Thus, the time taken at the column of G’ville must be 5 hours (2.5 + 2.5) which is the summation of the time taken from B’ham to Atlanta and Atlanta to G’ville. Eventually, the lowest cost for this turn is in consequence of choosing 3B’ham. With this recurrence, this algorithm reveals the same result as our effort of using the linear programing.
Instead of the manual calculation, for this writing, our focus will be mainly on how to use the well-known and effective graph database called Neo4j in order to solve our interested problem by the implementation of Dijkstra algorithm. Apart from path finding algorithms, this library provides a lot of useful functions such as centrality, community detection, link prediction, and similarity algorithms. Initially, we need to install the plugin named Graph Data Science Library (gds) otherwise we won’t be able use this algorithm on the platform. The picture below might help readers without this required library on their Neo4j to discover its right location.
After the installation is completed, the method to verify its existence is to use the following command on Neo4j browser.
CALL gds.list();It should return all available functions in this library.
Firstly, let us construct the corresponding graph according to the problem by using this following command.
CREATE (a:Location {name: "B'ham"}),
(b:Location {name: "Atlanta"}),
(c:Location {name: "Chatt"}),
(d:Location {name: "G'ville"}),
(e:Location {name: "K'ville"}),
(f:Location {name: "A'ville"}),
(g:Location {name: "Charl"}),
(h:Location {name: "G'boro"}),
(i:Location {name: "L'burg"}),
(j:Location {name: "Raleigh"}),
(k:Location {name: "Va Bch"}),
(a)-[:ROAD {cost: 2.5}]->(b),
(a)-[:ROAD {cost: 3}]->(c),
(b)-[:ROAD {cost: 1.7}]->(c),
(b)-[:ROAD {cost: 2.5}]->(d),
(c)-[:ROAD {cost: 1.7}]->(e),
(c)-[:ROAD {cost: 2.8}]->(f),
(d)-[:ROAD {cost: 2}]->(f),
(d)-[:ROAD {cost: 1.5}]->(g),
(e)-[:ROAD {cost: 2}]->(f),
(e)-[:ROAD {cost: 5}]->(i),
(f)-[:ROAD {cost: 3}]->(h),
(f)-[:ROAD {cost: 4.7}]->(i),
(g)-[:ROAD {cost: 1.5}]->(h),
(g)-[:ROAD {cost: 2.3}]->(j),
(h)-[:ROAD {cost: 2}]->(i),
(h)-[:ROAD {cost: 1.1}]->(j),
(i)-[:ROAD {cost: 3.3}]->(k),
(j)-[:ROAD {cost: 2.7}]->(k);Next, let us demonstrate the graph built by using this command.
MATCH (n) return n;It should return the subsequent graph.
The further step is to name this graph as “carGraaph” by using this following command.
CALL gds.graph.create(
'carGraph', # desired name on this line
'Location',
'ROAD',
{
relationshipProperties: 'cost'
}
);Finally, we will use the built-in function of the graph data science library to explore the shortest route as followings.
MATCH (source:Location {name: "B'ham"}) # indicate the departure
CALL gds.beta.allShortestPaths.dijkstra.stream('carGraph', {
sourceNode: id(source),
relationshipWeightProperty: 'cost'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs
RETURN
index,
gds.util.asNode(sourceNode).name AS sourceNodeName,
gds.util.asNode(targetNode).name AS targetNodeName,
totalCost,
[nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS nodeNames,
costs
ORDER BY index;This will return the shortest route from the particular node to all remaining nodes.
The result absolutely insists the output as per the linear programing approach previously did. As can be seen, in addition to the shortest route from Birmingham to Virginia Beach, the output offers the best route from our specific origin, namely Birmingham, to all nodes in graph accordingly. For instance, it shows that the shortest route from Birmingham to Lynchburg (L’burg) is the one via Chattanooga (Chatt) and Knoxville (K’ville) with the time taken of 9.7 hours.
Conclusion
Both the linear program approach and Dijkstra algorithm state the identical result regardless tools to be used. Personally, to solve this question, I prefer using Dijkstra algorithm via the graph data science library. How about you? Let make the shortest route into real life.
PS. This medium is a part of homeworks of the advance AI subject (graph theory section) at school of Big Data Engineering, Dhurakij Pundit University.
