Ship traffic scheduling in the Göta River
SSPA participates in the GOTRIS (Göta älv River Information System) project, which aims at optimising the route for ships travelling on the Göta River with respect to planned bridge and lock openings as well as ship meeting places. The project’s aim is to develop a prototype system that makes all information about ship traffic on the Göta River available to all modes of transport that are affected by bridge openings and ship port arrivals. By bringing in the stakeholders and having rail, sea and road traffic sharing information and services in a River Information Service (RIS) system, the project demonstrates how traffic can be controlled regarding the passage of bridges and locks, so that disturbances in rail and road traffic can be minimised, whi le ship traffic is optimised. SSPA’s role has been to develop the scheduling module that takes into account all of the constraints for the route on the river. These are typically train traffic, bridge maintenance, other ships as well as speed limits.
The GOTRIS project includes a number of partners, with Viktoria Swedish ICT, The Swedish Transport Administration (Trafikverket), InPort and SSPA being the main players in the process of the prototype system development. Viktoria Swedish ICT handles project management, InPort handles the compilation of vessel routes from Safe Sea Net Sweden as well as the graphical user interface for pilots and rail traffic control. The Swedish Transport Administration’s main responsibility is to act as a centre for all data sources, such as train timetables, AIS data and more. SSPA’s role is to develop a scheduling module that can handle the many constraints imposed on traffic on the river. Ideally the algorithm would give each ship a scheduled route from its current position to the next port and also continue to schedule routes to all ports listed in the Safe Sea Net Sweden’s list of ports for the ship.
Testing the prototype system
The prototype will be tested on pilots, bridge supervisors and rail traffic control. They will each be given a tablet computer with a graphical interface, see figure above. The interface shows estimated arrival times along the river as well as bookings for bridges. This will give the actors more advance notice, thus better ability to plan ahead for incoming traffic.
The Swedish Transport Administration’s server delivers all input data to the SSPA scheduling module. Data consists of train timetables, weather information, pilot bookings, departure times from ports etc. The module schedules all traffic and for each ship it returns a list of holding times at a number of positions along the river. The scheduling module consists of two chained algorithms. The first one is a basic deterministic rule-based approach that computes a baseline route. The baseline route fulfils all ship-related constraints, such as speed limits and bridge bookings, but it doesn’t take into account inter-ship related constraints, such as meetings and overtaking. The second step is an evolutionary algorithm that, based on the baseline route, handles the more advanced inter-ship related restrictions and also, if necessary, reduces the number of speed changes along the route.
An evolutionary algorithm is an optimisation technique based on Darwinian principles, i.e. survival of the fittest. For a given problem, the input values are expressed as a genome with a fitness function constructed for evaluating the problem with the genome input. If it’s a maximisation problem then the higher the value returned from the fitness function the better that set of genes solves the problem.
A large population of input values, i.e. individuals, are created and in each generation all individuals are tested with the fitness function. The best ones continue to the next generation, hence Darwinian. The task for the evolutionary algorithm is to find the individual (in our case the vessel) that either maximises or minimises the fitness, depending on the type of problem being solved.
Evolutionary algorithms have their advantages. They are well-suited when the problem at hand has many viable solutions and a large number of variables and in the case when there is no deterministic algorithm that solves the task optimally. In more casual terms they are usually a good approach when the solution is more easily defined in terms of what it shouldn’t be than how it’s supposed to be.
GOTRIS evolutionary algorithm
In the scheduling module, the Göta River is divided into a long list of segments and the genome is the speed on each of those, so a ship with a route that spans 30 segments has a genome with 30 speed values. In each generation hundreds of route candidates are created, all of them initially a small variation of the base line route.
The fitness function evaluates each route and calculates a value of how well that particular route solves the problem. It is a combination of calculations, a set of sub-functions, one for each restriction. In general, fitness functions are continuous, meaning that a very small variation of the genome will generate a small change in the fitness value. However, there are situations where binary elements are inevitable, e.g. in the case of GOTRIS when the route tries to pass a blocked bridge, then the fitness function will return a very large fixed amount, to indicate that the route is not a good
Objectives of the GOTRIS fitness function
The objective is to reduce fitness according to the following criteria:
- proportional to comfort speed deviation
- if speed is below the ship’s minimum speed
- proportional to the deviation from near segment’s speed
- if the ship tries to pass a bridge that is blocked
- if the ship doesn’t pass the bridge when it has a booking
- if the ship has a meeting outside of the designated meeting zones.
In this context it is easier to discard routes that do not fulfil all constraints than it is to actually calculate a route that does.
The benefit of using an evolutionary method is that it finds solutions that would be hard to calculate with a deterministic set of rules. This is especially true in GOTRIS when it comes to reducing the number of speed changes on the route. It handles this while still taking bookings and meetings into account.
Another advantage is that special logical cases don’t need any separate handling, instead the route is simply discarded when it breaks the constraints. This however comes with a penalty: computational time is long.
There are other alternatives for optimisation, such as the Simplex method, but the fact that evolutionary algorithms always return a solution and that it is possible to further refine a solution by continuing for more generations, makes it a very suitable approach in the GOTRIS project.
The system for scheduling and the ability to get an overview of the upcoming 24 hours of rail and ship traffic makes it possible to utilise resources, such as bridges, more effectively. It also means that planned maintenance can be carried out with less impact on infrastructure and potentially allowing it to put a figure on the capacity of the system as a whole. The environmental impact is also addressed, since the pilot receives an early overview of the speed required to arrive on time for bridge bookings.
The next steps for the GOTRIS project is to evaluate the prototype, getting feedback from pilots and traffic control on how well GOTRIS performs. This input will be used in the design of a future fully operational system.
Photos and illustrations
Pilot user interface in the GOTRIS prototype
Chematic of the GOTRIS area. Graphic: Viktoria Swedish ICT