Graphs – Finding optimal routes

An example of how the use of graphs can help us find optimal routes to solve various problems.

An example of how the use of graphs can help us find optimal routes to solve various problems.

A graph system can be used for multiple purposes, being in some cases very useful to solve complex problems. In this article will show you how to use this tool to find optimal routes with graphs.

First we will build a two-dimensional 6 x 6 directed graph grid to work on. We will also keep the identifier of the first and last node for later use.

DG = nx.grid_2d_graph(6, 6, periodic=False).to_directed()
positions = nx.kamada_kawai_layout(DG,)
start_node = list(DG.nodes())[0]
end_node = list(DG.nodes())[-1]
6 x 6 Grid type directed network
6 x 6 Grid type directed network

We are going to make a system that finds the optimal route from the initial point (start_node) to the final point (end_node). But we will add a point of complexity to make the exercise more fun.

Let’s imagine that each of the nodes are rooms in a burning building, which have different temperatures. Our goal is to get from the starting point to the exit by getting through the less hot rooms.

So next step, is to randomly assign our network (building rooms), initial hotspots and neighbouring hotspots.

hot_nodes = random.choices(list(DG.nodes()), k=5)
DG.add_nodes_from(hot_nodes, node_temp=0.9)
for hot_node in hot_nodes:
this_neighbors = list(DG.neighbors(hot_node))
DG.add_nodes_from(this_neighbors, node_temp=0.5)
Different temperatures randomly assigned at the nodes of the network
Different temperatures randomly assigned at the nodes of the network

Now we are going to deal with the edges (corridors) that connect our nodes (rooms). These corridors will have an average temperature obtained between the temperature of the rooms they connect.

So, if we traverse each edge of the graph we can calculate the temperature and assign it as follows:

for edge_ori, edge_dest in list(DG.edges()):
    DG.add_edges_from(
        [(edge_ori, edge_dest)], 
        edge_temp=np.mean(
            [DG.nodes[edge_ori]["node_temp"], 
             DG.nodes[edge_dest]["node_temp"]]
        )
    )
Network edges with the temperatures assigned according to the nodes that connect each of them
Network edges with the temperatures assigned according to the nodes that connect each of them

Therefore, if what we want is to find the optimal route from the starting point (in this case, the right end node) to the end point (the left end node), we can use one of the algorithms that solve this type of problem in a computationally optimal way.

Algorithm A*, which works as shown in the following image:

Algorithm A*, which works as shown in the following image.

Thus, if we use this system without taking into account the temperatures of the nodes, we would find one (there may be several) of the shortest routes from the starting point to the end point as the answer.

nx.astar_path(DG, start_node, end_node)
[(0, 0),
 (1, 0),
 (2, 0),
 (3, 0),
 (4, 0),
 (5, 0),
 (5, 1),
 (5, 2),
 (5, 3),
 (5, 4),
 (5, 5)]
One of the shortest routes from the start node (0, 0) to the end node (5, 5)
One of the shortest routes from the start node (0, 0) to the end node (5, 5)

But as we said, this is not what we are looking for, because if we were to go through all the rooms indicated by the shortest route, we would cross rooms and corridors with very high temperatures.

So let’s repeat the process, this time taking into account the temperatures to find the shortest and coldest route possible.

nx.astar_path(DG, start_node, end_node, weight='edge_temp')
[(0, 0),
 (1, 0),
 (1, 1),
 (2, 1),
 (2, 2),
 (3, 2),
 (3, 3),
 (4, 3),
 (5, 3),
 (5, 4),
 (5, 5)]
One of the shortest and coldest routes from the start node (0, 0) to the end node (5, 5).
One of the shortest and coldest routes from the start node (0, 0) to the end node (5, 5).

In this way we already have a system that solves the problem we have stated in a matter of milliseconds.

However, what would happen if, in addition, we remove some nodes from our network, simulating rooms inaccessible by fire? for example:

to_remove = [
    (5, 1), (4, 2), (3, 3),
    (0, 2), (1, 1), (2, 1)
]
for node in to_remove:
    DG.remove_node(node)
Example of optimal routing by removing some of the nodes from the graph
Example of optimal routing by removing some of the nodes from the graph

The route is adapted to the environment and again we obtain the most optimal route taking into account the temperature of the route.

In this way, with the algorithm already prepared, we can generate a much larger environment and make the algorithm face a larger number of decisions to make in order to find the optimal route.

For example, by generating a new graph with 2500 nodes and 150 hot spots to be taken into account.

50 x 50 directed graph with randomised hotspots
50 x 50 directed graph with randomised hotspots

And with the same ease of the already programmed, we obtain the optimal route to the exit.

Optimal route over the graph taking into account the route temperature
Optimal route over the graph taking into account the route temperature

Obviously this is a simple example of the use of graphs to explain how they can be used to solve certain problems. These same tools can be useful to solve different problems that we can find in companies on a daily basis.

Here are some examples of different complexities that can be worked on with a graph system and choice of optimal routes:

  • Optimisation of warehouse space
  • Distribution of goods
  • Fuel savings in vehicle fleets
  • Optimisation of product purchase / sale rules

The code of the exposed example is at https://github.com/ so you can download it and use it yourself.

If you found this post about graphs useful, share it with your contacts so that they can also read it and give their opinion. See you in social networks!

Default image
David Martín
Articles: 2