EPSRC logo

Details of Grant 

EPSRC Reference: EP/M007243/1
Title: Train unit scheduling optimisation
Principal Investigator: Kwan, Professor RSK
Other Investigators:
Researcher Co-Investigators:
Project Partners:
First ScotRail Limited Tracsis plc
Department: Sch of Computing
Organisation: University of Leeds
Scheme: Standard Research
Starts: 19 January 2015 Ends: 21 July 2018 Value (£): 577,062
EPSRC Research Topic Classifications:
Artificial Intelligence Mathematical Aspects of OR
EPSRC Industrial Sector Classifications:
Transport Systems and Vehicles
Related Grants:
Panel History:
Panel DatePanel NameOutcome
17 Jul 2014 EPSRC ICT Prioritisation Panel - July 2014 Announced
Summary on Grant Application Form
Efficient passenger rail is a key factor of success for the UK economy. Growing and modernising the UK rail infrastructure such as the HS2, Crossrail and many other projects must be complemented by optimised operations planning to maximise its passenger carrying network capacity.

After a timetable has been finalised, a fleet of train units is scheduled. Each train unit is assigned to serve some train journeys in a sequence and no timetabled journey is left uncovered. Obviously all the train connections for each unit must be feasible, i.e. the unit must be at the right place before its next scheduled departure is due, and the scheduling task is like solving a hugely difficult jigsaw puzzle that the minimum number of train units is to be used. Moreover, some timetabled journeys at peak times may demand more seats than a single train unit can provide. Thus the train units may be purposefully scheduled to overlap in their assignments to achieve the desired combined seat capacity.

Train operating companies are motivated to seek automatic optimised train unit scheduling methods for several reasons. There are very high costs to lease, operate and maintain the train units making them a critical resource for most UK train operating companies, how to spread the train unit resource amongst competing demands is a big challenge. The potential saving in an optimised train unit schedule is very attractive. Good train unit schedules can be derived manually based on experience and local knowledge, but that is usually a very time consuming and tedious process making it impractical to consider many what-if options available to the planners.

Existing research in passenger train unit scheduling is mainly from the Netherlands and Italy, whose models have not included some UK features and have tackled smaller problems than those usually found in the UK. This project builds on recent research in collaboration with ScotRail, which has led to promising results for part of the ScotRail network around Glasgow and Edinburgh. This project aims at yielding fully operable schedules in real life practice to demonstrate the validity and quality of research, and hence further more extensive industrial collaboration is planned.

This 36 month project consists of three parallel work streams. The planned research is grounded on an exact mathematical approach, under which advanced solution techniques and appropriate formulation variations are sought to improve and refine its computational performance. One research fellow will be responsible for this work stream.

While the mathematical approach has superior optimisation power, computational time escalates exponentially to becoming impractical beyond small to medium sized problem instances. In another work stream, the second research fellow will investigate a new method that could make a step change. Recognising that there is a practical limit on how large a problem instance the mathematical optimiser can solve 'comfortably' a heuristics is used to compress and transform, analogous to compression of an image file, the problem instance into a much smaller one for the mathematical solver to be applied. Over a number of cycles, more and more is learnt about the key data points to be retained in the compressed instance whereby the hybridised algorithm would converge to the optimal or very near optimal solution.

In the third work stream, both research fellows will be engaged in activities with our industrial collaborators to ensure that the most realistic model is built, the solution schedules produced are fully operable and testing and evaluation are as thorough as possible. The activities include short placements, regular contacts, on-site testing/evaluation and three seminar workshops that other train companies will also be invited.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.leeds.ac.uk