Student Research Projects

Compute CPDs for public networks

Compressed Paths Databases are a state-of-the-art method to compute and store all-pairs shortest paths. As with most pathfinding algorithms, CPDs assume a static graph to a certain extent; a fine situation when considering cars. In the context of public transportation, we have to encode information about time dependent decisions – e.g., waiting for a bus. We want to extend the capability of CPDs to use time- and mode-dependent information.

Tasks

• Starting with a time-expanded network (edges between nodes have a cost depending on time), determine how bad the CPD will be.
• Find ways to compress the CPD further or change the representation without losing information.
• Find ways to encode time-dependent decisions such as waiting for a scheduled bus or train.

Prerequisites

The CPD code is in C++, knowledge about pathfinding algorithms is a plus.

Driver agents for testing our routing engine

We have a major project for reducing congestion in Melbourne through coordinated journey scheduling and planning. We have built a system that can plan thousands of routes per second, but it has no feedback from the drivers following the routes.

This project will develop a very simple model of all these drivers. Each driver follows the route - more or less accurately - for some time. The driver then reports back to the routing system saying where (s)he is, and requesting an updated route.

For now, we do not seek to model human behaviour, but only behaviour that sometimes deviates from the plan with some probability. We would like to have agents able to miss turns and determine what their next request will be.

Tasks

Create a program capable of:

• querying a REST API with an origin/destination-pair;
• receive a set of directions in form of a list of (nodes, travel_time);
• wait an appropriate time to simulate driving, then have a chance of missing the next node.

At this point, the agent should be able to send a new query to the API for directions. from there, we would like to explore more realistic behaviours - impact of speed, current traffic, or duration between actions.

Prerequisites

The working code in the group is in C++, but this project need not integrate with it. Due to its parallel structure (being able to spawn lots of agents is a must), a functional language such as Haskell would be a great candidate.

Melbourne simulation based on A/B street

Traffic simulation is a tool used by city planners to assess the potential effects of their actions. A/B street is one such tool with a twist: it is a game that lets users explore options to improve traffic in Seattle. As it is based on OpenStreet Maps, our group would be interested to see whether we can spin a similar tool for Melbourne.

Tasks

• Create a model of Melbourne using A/B street.
• Use Compressed Path Databases (ours) instead of Contraction Hierarchies (slower state-of-the-art) for fast_paths.
• Use a personal agent model instead of cars – bonus: see whether they can use public transport.

Prerequisites

The source code for A/B street is in Rust, working code in the group is in C++.

(Parallel) Frank-Wolfe to compute user equilibrium

The Frank-Wolfe algorithm is an iterative process used for route assignment – which route will drivers follow given current congestion. The idea is to compute, iteratively, the congestion on each link of a network – or reduction in travel speed given the number of vehicles on the link. One key component of the algorithm is computing shortest paths, a task that Compressed Paths Database excel at. We would like to leverage our existing pathfinding library to compute user equilibrium faster.

Tasks

• Implement the Frank-Wolfe algorithm for route assignment on arbitrary road networks.
• Potential extension to parallel computing as links are pretty much independent during on step.

Prerequisites

Knowledge in C++ as the candidate may need to use the group’s code. Knowledge in mathematical programming/optimisation is a plus.