Tropical Mathematics and Optimisation for Railways, June 2018

The main purpose of this workshop is to bring together specialists in tropical mathematics and mathematical optimisation applied in railway engineering and to foster further collaboration between them. It is inspired by some applications of tropical mathematics to the analysis of railway timetables. The most elementary of them is based on a controlled tropically linear dynamic system, which allows for a stability analysis of a regular timetable and can model the delay propagation. Tropical (max-plus) switching systems are one of the extensions of this elementary model.  Tropical mathematics also provides appropriate mathematical language and tools for various other applications which will be presented at the workshop.

The talks on mathematical optimisation in railway engineering will be given by Professor Clive Roberts and other prominent specialists working at the Birmingham Centre for Railway Research and Education (BCRRE). They will inform the workshop participants about the problems that are of actual interest for railways, and suggest efficient and practical methods of their solution.

Organisers

Professor Clive Roberts and Dr Sergey Sergeev

Confirmed speakers

• Clive Roberts (BCRRE, University of Birmingham)
• Ning Zhao (BCRRE, University of Birmingham)
• Xavier Allamigeon (INRIA and Ecole Polytechnique, France)
• Ton van den Boom (Technical University of Delft, the Netherlands)
• James Hook (University of Bath)
• Michal Kocvara (University of Birmingham, School of Mathematics)
• Zhongbei Tian (BCRRE, University of Birmingham)
• Emeka Henry Chukwumah (BCRRE, University of Birmingham)

Venue

All talks will take place in Lecture Theatre C, Watson Building, University of Birmingham R15 on campus map (PDF, 465 kB).

Schedule

11:00 - 11:30: Clive Roberts, (BCRRE, University of Birmingham)

11:30 – 12:00: Ning Zhao (BCRRE, University of Birmingham)

Title: Railway traction system simulation and optimisation (PDF, 2.4 MB)

Abstract: Energy efficient techniques are receiving increasing attention because of rising energy prices and environmental concerns. Railways, along with other transport modes, are facing increasing pressure to provide more intelligent and efficient power management strategies. This presentation introduces an optimisation method for metro operation to minimise train energy consumption by calculating the most appropriate train trajectory and timetable configuration. Field tests and driver trainings have been carried out to verify the performance and practicability of the optimisation outcomes. The results show that, by using the optimal train trajectory and timetable, the energy consumption can be significantly reduced, thereby improving the system performance and stability.

12:00:  Lunch

13:00 – 13:45  Xavier Allamigeon (INRIA and Ecole Polytechnique, Paris, France)

Title:  Performance evaluation of an emergency call center: tropical polynomial systems applied to timed Petri nets

Abstract: We analyze a timed Petri net model of an emergency call center which processes calls with different levels of priority. The counter variables of the Petri net represent the cumulated number of events as a function of time. We show that these variables are determined by a piecewise linear dynamical system. We also prove that computing the stationary regimes of the associated fluid dynamics reduces to solving a polynomial system over a tropical (min-plus) semifield of germs. This leads to explicit formulae expressing the throughput of the fluid system as a piecewise linear function of the resources, revealing the existence of different congestion phases. Numerical experiments show that the analysis of the fluid dynamics yields a good approximation of the real throughput.

This is joint work with Vianney Boeuf and Stéphane Gaubert.

13:45 – 14:30: Ton van den Boom (Technical University of Delft, the Netherlands)

Title: Model predictive scheduling of semi-cyclic discrete-event systems using switching max-plus linear models (PDF, 353 kB)

Abstract: The first part of the presentation we discuss the scheduling of semi-cyclic discrete-event systems. We discuss some applications in which the discrete event system can be modeled as a switching max-plus-linear system. Dynamic graphs will be used to describe the order relations of the system events. We define the model predictive scheduling design problem to optimise the schedule, and we show that the problem can be recast as a mixed integer linear programming (MILP) problem.

In the second part we will concentrate on railway traffic management. We present a model predictive controller for online railway traffic management of railway networks with a periodic timetable. The main aim of the controller is to recover from delays in an optimal way by changing the departure of trains, by breaking connections, and - in the case of multiple tracks between two stations - by redistributing the trains over the tracks. We describe how the railway management problem can be solved using centralised model predictive control (MPC) and we propose a distributed model predictive control (DMPC) method to solve the railway management problem for the entire Dutch railway network. Finally, we discuss a method to determine a good partitioning of the network in an arbitrary number of sub-networks that is used for the DMPC methods.

14:30 Tea/Coffee

15:00 – 15:30:   James Hook (University of Bath, UK)

Title: A model for mixed linear–tropical matrix factorisation (PDF, 1.3 MB)

Abstract: Non-negative matrix factorisation (NMF) is one of the most frequently-used matrix factorisation models in data analysis. A significant reason to the popularity of NMF is its interpretability and the 'parts of whole' interpretation of its components. Recently, max-times, or subtropical, matrix factorisation (SMF) has been introduced as an alternative model with equally interpretable 'winner takes all' interpretation. In this talk I will introduce a new mixed linear-tropical model, and a new algorithm, called Latitude, that combines NMF and SMF, being able to smoothly alternate between the two. In our model, the data is modelled using the latent factors and latent parameters that control whether the factors are interpreted as NMF or SMF features, or their mixtures. We present an algorithm for our novel matrix factorisation. Our experiments show that our algorithm improves over both baselines, and can yield interpretable results that reveal more of the latent structure than either NMF or SMF alone.

This is joint work with Sanjar Karaev and Dr Pauli Miettinen of the Max Planck Institute for Informatics.​

15:30-16:00:  Michal Kocvara (University of Birmingham, School of Mathematics)

Title: Structural topology and material optimisation via mathematical programming (PDF, 4.8 MB)

Abstract: Topology optimisation gives answers to the fundamental engineering question: "How to place material within a prescribed design domain in order to obtain the best structural performance?" Topology optimisation and its generalisation, the free material optimisation, help to design lightweight structures, extract CAD shapes, quickly verify the optimised design and design composite parts and 3-D printed components. I will give a brief overview of basic mathematical models of topology and material optimisation and show how modern techniques of mathematical optimisation and numerical linear algebra can help to solve very large scale problems.

16:00- 16:30: Zhongbei Tian (BCRRE, University of Birmingham)

Title: Railway Power Network Simulation and Optimisation (PDF, 3.3 MB)

16:30 – 17:00: Emeka Henry Chukwumah (BCRRE, University of Birmingham)

Title: Why not go by bus? (a case study of Lagos, Nigeria)

Abstract: Congestion is a growing problem in developing cities as it is inextricably linked to economic growth. The concomitant effects sternly impact on cities economic competitiveness and residential attractiveness – for which the city of Lagos, Nigeria is not immune. As such, the study aims to contribute to a sustainable bus transit system in Lagos by improving understanding on how the system could be made more attractive primarily for commuting trips. With the aid of a multiple regression analysis and other statistical methods, the unattractiveness of the system was deciphered from seven established pertinent factors (satisfaction of service qualities, household size, land use - distance between home and work), income, car ownership, car use and accessibility - walk-time from home to bus stop and wait-time for each bus type). Results reveal that, car ownership and income influence the use of both bus services (BRT and Danfo), while the satisfaction of service quality influences the use of the Danfo service only. All other factors were statistically insignificant except the accessibility factors which gave an intuitively incorrect direction of influence. For this, it was concluded that Lagosians are inelastic to accessibility factors. Also, four strategies were then proposed based on these findings and ‘strengthened’ by six policy instruments; all with an aim to increase ridership and obtain a more sustainable bus transit system in Lagos city.

17:00 Tea/Coffee

17:30+  Dinner
Please inform Sergey Sergeev whether you are going to join the organisers and the speakers for dinner.