Custom Routing in AnyLogic

AnyLogic has a built-in routing solution. Whenever you are using a moveTo block in a network (Note: I am explicitely excluding GIS networks here, as the situation there is a bit different), AnyLogic will use its own solution to calculate the best route to your choosen destination. But what is THE best route? AnyLogic finds the route with the shortest distance.

However in a lot of situations this is not flexible enough:

• You want to completely avoid some routes, for example toll routes
• You want to have the fastest route and some parts of the network have speed restrictions
• You want to avoid already congested routes, like the traffic avoidance in a modern navigation device with internet access

Networks

Did I just say modern navigation device? How does such a device calculate a route? First of all it holds all the connection possibilities in a graph network, consisting of edges and vertices. Here is a table with these terms translated:

Routing

If you have an origin and a destination inside this network, how does a navigation device select a route through this interconnected system?

First you need to attach a cost to each edge, which you have to pay if I want to use it, like a road toll. The most intuitive case would be to use the length of the edge as it cost. This is exactly what AnyLogic does internally, and that is (simplified) also what your navigation device does when you set it to find the "shortest route". How to find the cheapest option now to go from A to B? Easy, just try every possible route and add the cost of the edges along the way. Let's note this down:

We just take the route with the lowest attached costs and there we go, this is the shortest route. In more complex networks this brute-force procedure is not feasible, because there are too many possibilities. This is where more clever algorithms are needed, that find the same cheapest solution, but with much less effort. One of those algorithms is the Dijkstra.

JUNG

Good news: No need to implement this or other route selection algorithms ourselves, somebody has already done so. Actually pretty nicely, including the infrastructure to import and define networks with nodes and vertices, several solving algorithms and much more. The Java package is called JUNG (Java Universal Network/Graph Framework). There is a manual for it. It is Open Source, and is used in social networks, web graph analysis, graph theory and data mining.

How to get this into AnyLogic? As any other Java package:

• Download the package

• Find the JARs that you need, in this case these four:

  • collections-generic.jar
  • jung-algorithms.jar
  • jung-api.jar
  • jung-graph-impl.jar
• Reference those four files in the "Dependencies" tab of your project properties in AnyLogic
• In your Main properties, under "Advanced Java", import the package into your class: import edu.uci.ics.jung.*;

Preparing the network

We saw that AnyLogic has elements that match the vertix and edge concept, nodes and paths. But there is one thing it doesn't have: the cost. The path element in AnyLogic has properties like location, length and visual properties, but thats about it. Good enough to implement a distance based routing. But this is what AnyLogic can already do, and we want to be more flexible.

Therefore it is necessary to extend the Path element of AnyLogic with cost information, here in the form of a function to retrieve the cost. For now it will return only the length of the path.

public class SpecialPath extends Path{
 Path path;

 public double getCost(){
  return  path.length();
}

Using JUNG in AnyLogic

The network

Now that my AnyLogic network has all the necessary information, I need to feed it into JUNG. I assume I have got a Collection (ArrayList), holding all my Nodes. Also, I create a variable on the canvas, named graph, of type Graph<INode,SpecialPath> with the initial value new SparseMultigraph<INode,SpecialPath>(). Then I loop through them to build the JUNG version of the network. All nodes get added to the network. For each node I also check for connected paths. If I find a connected path, I create a corresponding "Special Path" and add it to the network.

 for (PointNode n:nodes){
  graph.addVertex(n);
  for (int  i=0;i< n.getConnectionsCount();i++){
   if (!edges.contains(n.getConnection(i))){
    SpecialPath  es = new  SpecialPath(n.getConnection(i),n);
    graph.addEdge(es,n,n.getConnection(i).getOtherNode(n),EdgeType.UNDIRECTED);
   }
  }
}

Cost function

I have to tell Jung what to consider as my edges' cost. I do this with a Transformer:

Transformer<SpecialPath,Double> wtTransformer =
 new Transformer<SpecialPath,Double>() {
  public Double transform(SpecialPath link) {
  return  link.getCost();
 }
}

Getting the result

DijkstraShortestPath d = new  DijkstraShortestPath(graph, wtTransformer);
List<SpecialPath> solution = d.getPath(start,end);

Surprisingly, this is the easiest part, this is it! I get a List of SpecialPaths to follow.

Using the result

Because I cannot use the SpecialPaths directly with a moveTo block, I have to reconvert them to normal Path elements. Inside of the Agent to be moved, I save a list of those Paths and a counter. Then all I do is a simple loop: The Agent now moves along the Path elements until it reaches the destination.

Adding traffic awareness

Let's try to build a traffic aware routing. We add a field traffic to our exisiting SpecialPath class. Every time an Agent enters the moveTo block, it adds 1 to the traffic counter of the current Path element he is about to enter. Whenever it leaves the moveTo block, it reduces the traffic counter of the Path element it is about to leave. The getCost() function gets also updated:

public class SpecialPath extends Path{
 Path path;
 int traffic;

 public double getCost(){
  return  path.length()+traffic;
}

This cost function is very simple. If 10 agents are on one Path with length 10 meters, it's cost are equal to a Path with no traffic and a length of 20 meters. Of course this has to be balanced quite carefully to get a traffic management that makes sense.

Another thing to note: The traffic is taken into account at the time of the movement start for the whole route. By the time a specific path is being passed the traffic might have significantely changed! To cope with this, a traffic prediction, a central traffic registration or regular recalculations of the route might be necessary.

Visualisation

Since we do have the traffic information now anyway, why not visualise it? This will look cool and help to find bottlenecks quickly. The code assumes that you have a Line element somewhere, called "line", which gets replicated edgesSpecial.size()-times. This line is then used as a semi-transparent overlay to the network, and gets updated regularly.

int index=0;
double maxTrafficDensity = 0.1;
for(SpecialPath p:edgesSpecial){
		if(p.traffic>=0){
			double n=min(maxTrafficDensity,p.traffic/p.distance);
			int r = (int) ( (255 * n) / maxTrafficDensity);
			int g = (int) ((255 * (maxTrafficDensity- n)) / maxTrafficDensity) ;
			int b = 0;	
 			line.get(index).setX(p.path.getStartPoint().getX());
 			line.get(index).setY(p.path.getStartPoint().getY());
 			line.get(index).setEndX(p.path.getEndPoint().getX());
 			line.get(index).setEndY(p.path.getEndPoint().getY());
 			line.get(index).setColor(new Color(r,g,b, 30));
 			line.get(index).setLineWidth(10);
 			line.get(index).setVisible(true);
		}
		else{
		line.get(index).setVisible(false);
		}
	}
	index++;
}

And GIS Networks?

The whole article was referencing normal AnyLogic networks. For GIS networks, it is a bit different. There are 3 different cases:

1. A manually created GISNetwork with GISPoints and GISRoutes. Then the procedure is similar to the one in the article. You can use your own routing.

For the next two cases, the network data comes from external sources. This makes our procedure of importing the network data into JUNG impossible. Here you have to use the routing providers given by AnyLogic:

2. Most of the time you will probably use a predefined network ("Open Street Maps"), which is nothing less then our worldwide traffic networks saved in big graph networks online. Services like Open Street Map not only provide the network data, but also the routing itself! In this case, AnyLogic is not doing the route finding, but rather only making a request to the online service to provide the route to you, which is why GIS models typically require internet connection to work. For these requests, AnyLogic already offers some choices for the network:

   • 3 different network/routing providers
   • 4 network types (car, rail, bike, foot)

   And also one choice on the cost function:

   • Shortest/Fastest

   Since AnyLogic is aware that there is so many more choices on the internet, it offers you kind of an interface to access any route provider. You can activate this under GISMap - Advanced "Use custom route provider".

3. Use of PBF/OSM files: Here you download and import parts of a online providers network data locally into your model. The routing then gets done offline, by AnyLogic, using one of 5 routing algorithms that you can choose from. However you cannot influence the cost functions of this 5 algorithms, meaning you are still stuck with distance based routing only. This option is great however when you need offline access to standard distance routing on a large real-life public network.

Conclusion

It is fairly simple to integrate a custom routing into AnyLogic. This is a great example of how powerful the use of external Java packages in AnyLogic can be. Care needs to be taken for the definition of a balanced cost function and into considerations of time dependant effects, such as oscilating traffic.