MSc Project Proposal:

Vehicle Routing under Dynamic Network Topologies

Download the project proposal


Recent years have shown an increasing interest in the use of autonomous vehicles. One application is the use of driverless water taxis to transport small groups of people between stations along a river. When the stations are at fixed locations, we can model the stations and the possible connections between them using graphs; stations are represented as nodes, while the connections are represented by arcs.

If the river is used for freight transportation as well, the water taxis have to give way to the freighters to avoid collision. Therefore, at certain times the water taxis are not allowed to cross the river, which can be modelled by removing the associated arc in the graph. An example is shown in Figure 1.

Figure 1: The topology of the network changes over time due to the passing freighter

For efficient use of the water taxis, we want to know what the shortest paths in the graph are (in e.g. time or distance), while taking into account that not all arcs are available at all times. Finding shortest paths (in e.g. time or distance) is an important problem in transportation and logistics. To find the shortest path between two nodes in a weighted graph, Dijkstra's algorithm is a well-known method to arrive at the solution. This algorithm works well for static graphs, but once the graph topology changes, it has to be run again to find the shortest path between two nodes.

The main goal of this MSc project is to give an answer to the question:

``How can we determine the shortest paths between nodes when certain arcs are unavialable at known time periods?''

Since water taxis can travel at different speeds, the time it takes to traverse an arc can vary as well. An extension of the work is to associate a time range with each arc -dependent on the minimum and maximum speed of the water taxi- for the travel time. By considering the travel times of an arc as their weights and search for the fastest route (shortest path), we end up with a shortest-path problem with variable weights. Solving this problem makes it possible to find better routes, since it might be faster to slow down a little to take advantage of a link that just became available to travel on.

In [1] a method is proposed to efficiently update the set of shortest paths from a source node to the other nodes when the network topology changes. These ideas might be interesting to create a fast algorithm for updating shortest paths.

Research problems

The focus of this MSc project will lie on developing a shortest-path algorithm that can take into account temporary changes in the network topology. Some of the topics that can be considered are:
* find shortest paths when links are temporarily unavailable
* find shortest paths when the weights of the links can vary between fixed bounds
* integrate the work presented in [1] to efficiently update the set of shortest paths


[1] D. Frigioni, A. Marchetti and U. Nanni - Fully dynamic algorithms for maintaining shortest paths trees
Journal of Algorithms 34 (2000), p. 251-281.