Routing and graph theory

Source
The module is created in the context of the i-Locate project. The indoor-outdoor routing system developed in the context of the i-Locate project provides the material used for demonstrations and illustrations. Furthermore, the components of the system define the main components of the training module.
Ownership
The module is developed by the Eindhoven University of Technology (TUE) which is the partner in the i-Locate project responsible for the indoor-outdoor routing system. There are no copyright or other restrictions on the usage and license of the module.
Abstract

The major topics of the module are:

  • Problem and basic concepts of route guidance of individuals and vehicles
  • Constructing a navigation graph for basic uni-modal routing
  • Constructing an extended navigation graph for multi-modal routing
  • Constructing a navigation graph for indoor routing – special features of indoor routing
  • Constructing a navigation graph for integrated indoor-outdoor routing
  • Providing turn-by-turn directions for indoor routing to users
  • Software implementation (system architecture)
  • Demonstration and guidelines for users
  • Structure

    The module consists of the following building blocks:

    1. Theory and basic concepts of route guidance of individuals and vehicles
      • Route choice preferences of individuals, shortest-path routines, link costs functions
    2. Constructing a navigation graph for outdoor routing
      • Graph representation of a street network, graph representation of public transport networks, time-dependent link costs, representing time-tables of public transport
    3. Constructing a navigation graph for indoor routing
      • Dealing with special features such as multiple floors, large spaces, entrance nodes, different transport modes, routing preferences/constraints
    4. Turn-by-turn directions for indoor environments
      • Providing route guidance for indoor environments
    5. Software implementation
      • Data models of street networks and public transport networksProviding route guidance for indoor environments
      • Open standards
      • OpenTripPlanner software
    6. Demonstration and user guidelines
    Learning outcomes

    After completing the module the learner:

  • Understands the concepts of a navigation graph and shortest-path routines
  • Knows methods to map outdoor and indoor transportation networks to a navigation graph
  • Is able to judge the correctness of a graph representation of outdoor and indoor multimodal transportation networks and to identify faults and solutions
  • Is able to judge the correctness of tur-by-turn direction instructions for guiding users through outdoor and indoor multimodal transportation networks and to identify faults and solutions
  • Understands the system architecture of the routing system of i-Locate
  • Is able to structure transportation network data and street network data in the appropriate formats for the i-Locate routing system
  • Is able to structure routing requests in the appropriate format and to understand the routing response of the i-Locate routing system
  • Intended Audience
  • Pilot partners: users of the i-Locate routing system involved in the implementation of the system (at the pilot sites)
  • Technical partners: developers of the i-Locate system
  • Pre-requisites
    No prior knowledge.
    Language
    English
    Format
  • Power point presentation
  • Exercises
  • Software demonstrations
  • Expected workload
    3 ECTS (3 x 28 hour = 84 hour)