Routing and Graph Theory: Advanced Module

This training material has been developed in the context of the i-locate project.
Authors: Ion Barosan, Theo Arentze. The material is released under a Creative Commons Attribution Share-Alike License (
The module introduces a methodology for indoor navigation graphs, together with a short description of the technologies supporting the routing: the OpenTripPlanner and The General Transit Feed Specification (GTFS). The OpenTripPlanner is an open-source multimodal route planner used to plan multi-modal walking, wheelchair, biking, car and transit trips. The GTFS is an internationally accepted format for public transportation schedules and associated geographic information. A GTFS file Is a group of zipped (compressed) CSV files( comma separated values ), which together contain enough information to support route and journey planning software.

The methodology presented in the module specifies the concreate steps for creating an indoor navigation graph. These steps guide the user from defining the nodes for entrances and places where to change the direction during the navigation, to how these nodes are connected in order to form a navigation graphs. Depending of the characteristics of the rooms/corridors/halls the user may choose a specific way to build the navigation graph. One specific node in the graphs is an anchor node. An Anchor node can link the entrance of the building to an outdoor node. The outdoor node can be a parking node or pedestrian location node. Also, an anchor node must be used to connect floors with each other in the building.

The following units are presented in the course:

  • How to Create The Graphs for Indoor Navigation for Small Corridors and Small Rooms;
  • General Rules – Algorithm for Indoor Navigation Graphs;
  • How to Create The Graphs for Indoor Navigation for Wide Corridors with Obstacle;
  • How to Create an Anchor Node for the Entrance of the Building;
  • How to Create an Anchor Node Between Floors – Stairs and Elevators.
Learning outcomes
The main outcome for the trainee is to be able to create indoor navigation graphs, based on the topology of the building. Depending of the kind of the room/corridor/hall the trainee has to choose the proper way to construct the graph. Also, he/she shall be able to connect indoor graphs with outdoor graphs using the anchor node.
Intended Audience
Users who need to create indoor navigation graphs.
General knowledge about routing and navigation for indoor and outdoor environments.
Pptx presentation.
Expected workload
The methodology presented in the module can be learned in one-two days, including the creation of a few indoor graphs as experiments.