Summary of the impact

Transport crew scheduling research at Leeds University since 1994 produced optimising algorithms and industry-ready software that led to the spinning out of Tracsis in 2004. The software, including upgrades, is used by over 40 bus and train companies who previously relied on manual processes. A minimum estimate of a £230 million saving in crew costs has been achieved in the UK alone over 2008-31.7.2013. Since 2008, the software has been routinely used by bidders in all UK rail franchise tenders, contributing to cost effective, efficient and reliable rail transport. Success led to the Tracsis floatation in November 2007 (market capitalisation: £46.7 million on 22/5/2013).

Underpinning research

Research in transport crew scheduling in this UoA goes back to the pioneering work of Wren in the 1960s, but it is the large body of research since 1994 that led to the Tracsis spin-out in 2004. The necessity for coherent shift working of crews, compounded by numerous constraints on the crews (e.g., limited shift duration, required breaks for crew), the vehicles (route compatibility and traction type), and other geographical and operational constraints, makes transport crew scheduling a difficult (NP-hard) combinatorial optimisation problem. Historically, crew scheduling problems have most frequently been tackled using Integer Linear Programming (ILP). Thus, the challenge is to find better (nearer optimal) solutions, more efficiently, for ever-growing problems.

Prior to the 1990s, crew scheduling research at Leeds was focussed on bus operations. Two successive EPSRC funded research projects GR/K07256 (Wren, Kwan, £116K, 1994-96), and GR/K79024 (Wren, Smith, Proll, Kwan, £256K, 1996-99), switched the focus to the much harder problem of train crew scheduling. While advances in generic ILP solvers and computer hardware played some part in these developments, their impact was limited. First, train crew labour rules and operational constraints lead to considerably more complex formulations. Second, problem instances are much larger. For example, before this research, cutting edge systems could only solve problem instances of up to around 100 crews. However, most UK train operating companies require the ability to schedule more than 150 crews, and several train companies have to schedule more than 300 crews. The exponential complexity of the problem means that even a doubling in the number of crews results in massively larger search spaces. The larger geographical areas covered, with many intermediate stations suitable for changing crews, add further complexity.

The approach taken by the Leeds team was therefore a holistic analysis of every step of the problem, from its formulation, through the generation of candidate solutions, the selection of suitable solutions, and the solvers. Throughout the research and software development, the researchers worked closely with users: trialling the algorithms, enhancing the system, improving the user interface, increasing parameterisation and introducing recommended solution strategies.

The key contributions of the Leeds research underpinning the impact fall under three categories:

1. Generation of candidate solutions: Part of the Leeds research was directed into the development of an appropriate collection of candidate train crew shifts as input to the ILP solver [1,2]. This candidate shift generation process is domain knowledge intensive and requires the use of carefully designed heuristics.

2. Improved Select Phase: Once sets of candidate solutions are generated, the ILP selects a good subset from all the candidate shifts. The Leeds team investigated new formulations and developed algorithms for speeding up the ILP solver [3]. In addition, a special column generation technique was developed [4]. Other column generation approaches construct new shifts dynamically, via subsidiary optimisation problems which may be complex and may not fully reflect the viability of the shift, as their need is recognized within the process. The Leeds technique [4] avoids this difficulty with a one-step generation phase: by optimising over dynamic subsets of the full set of pre-generated shifts. By allowing for the separation of the problem specific domain from the optimising algorithms, it significantly increases flexibility and adaptability to new problems. This approach was further developed under an EPSRC-funded project GR/M23205/01 (Proll, Wren, £141K, 1998-2001).

3. Improved heuristics and hybrid solver: To improve the solver efficiency, new meta-heuristic techniques were proposed and tested [5]. These approaches specifically targeted large and complex problem instances. This research made further progress through an EPSRC+AEA Technology grant GR/S20949/0 (Kwan, £212K, 2003-2006). Work on this grant led to a major breakthrough, in a new hybridised algorithm called PowerSolver, capable of solving bus and train crew scheduling problem instances which were previously deemed too large and complex [6]. The hybridised algorithm uses heuristics to compress problem instances to a manageable size and complexity so they can be solved relatively easily and quickly. A further key new feature of this solver is the ability to improve and refine the solution iteratively (in a fully automated manner).

4. TRACS II: This large body of research, combining elements from all of the above aspects, led to a new crew scheduling system called TRACS II [7], which was then improved further in TrainTRACS and BusTRACS incorporating contributions from the Leeds team. It was the TRACS II system that triggered the establishment of the Leeds spin-out company Tracsis.

Key researchers:
[text removed for publication]

References to the research

(in RAE2008 submission) The advances in mathematical solvers in the last 20 years are still inadequate for large complex driver scheduling problems not atypical in UK. This paper, published in an international, peer reviewed journal, reports on a major breakthrough hybrid method, which does not require problem sub-division and yields cheaper solutions. The new approach has generic applicability to other Set Covering problems.

(in RAE2008 submission) This paper, published in a premier international journal on scheduling, describes the full "industry standard" TRACS II system.

References [6] and [7] illustrate the quality of the research (see notes).

Details of the impact

Tracsis plc — from algorithm to the Leeds spin out:

Rail and bus companies were involved from the first stages of the development process, providing expert knowledge and performing trials on our algorithms. Bus and rail companies trialled algorithms developed by the Leeds team as early as 1994-1996 (under EPSRC grant GR/K07256) [A]. This directly led to the adoption of TRACS II by First Bus in 2000 and ScotRail in 2003 [A,B].

The University of Leeds founded the spin-out company Tracsis in 2004 to further commercialise its TrainTRACS and BusTRACS crew scheduling software. ScotRail, First Bus (all companies in the group) and Translink (in Northern Ireland) were initial clients of Tracsis. From 2004 to 2007, further pilot trials of TrainTRACS were carried out with more train companies, and the trials successfully led to new licences bought [B].

Significance

1. The scheduling software developed from the research is mission critical responsible for operations planning in many transport companies. At the time, these companies relied on staff and time-consuming manual processes to schedule their crews [A,B]. The use of automatic optimising software has freed up their time to be more creative in considering a wide range of what-if scenarios. This has the benefit of not only achieving the most efficient schedules, but also schedules balanced against a host of robustness and local issues that result in greatly enhanced reliability of services. Ultimately, the public transport users benefit [A,B].
2. The flexibility and power of the software is routinely used for short-term rescheduling, due to weather or engineering works [A,B]. The software can also be used to provide the best options of public transport at large events such as football match finals. The scheduling scenarios often involve an acute imbalance of demands across the network, special constraints, and very limited resources. Notably, the software was used for scheduling the Rugby World Cup train services in New Zealand, 2011 [B].
3. Rail franchise tendering is a means of getting the best value and quality of train services for the public. Since 2008, the TrainTRACS software has been used by nearly all shortlisted bidders in all the UK rail franchise tenders, contributing to cost effective, efficient and reliable rail transport. This has the impact of raising the standard of the proposed services with the confidence that when a bidder wins, the services can be delivered with respect to crew resources [B].
4. Tracsis has provided new employment. As of June 2013, Tracsis is an international company employing about 200 full-time-equivalent staff with offices in Leeds, Derby, Tadcaster and Australia [B].
5. As evidence of the success of Tracsis, its distinctive contribution and far-reaching impact, Tracsis has won the 2013 Small Cap Company of the Year Award (supported by the London Stock Exchange) and the 2011 Yorkshire Post Excellence in Business Award, presented by the Deputy Prime Minister. The judges of the 2011 award praised Tracsis as: "a prime example of university knowledge being commercialised and performing well in its market" [C,D].

Growth and reach during the REF period:

1. In November 2007, Tracsis was floated on the London Stock Exchange (AIM) and the IPO raised £2 million [B]. Tracsis is successful with increasing turnover and profit: year ending 31^st July 2008 (£0.81 million, £0.39 million), 2009 (£2.31 million, £0.72 million), 2010 (£2.65 million, £0.58 million), 2011 (£4.08 million, £1.11 million), 2012 (£8.67 million, £3.01 million), 2013 (£10.83 million, £2.59 million); its market capitalisation is £46.7 million on 22/5/2013 [B,E,F]. Looking forward, the peak share price was 207.5 pence on 22/10/2013 and the market capitalisation was £52.7 million.
2. The software is being used by 14 out of the 20 UK train companies operating passenger rail services, all UK bus companies in the First group (the UK's largest bus operator, covering local services across the country), and more recently penetrating the freight train sector as well. There are also overseas clients in Sweden, New Zealand and Australia [B,F].
3. Since 2008, all the train operators who have adopted TrainTRACS have conducted pilot trials and evaluated the savings they could achieve. Tracsis estimate overall savings at 2-12% over traditional methods [B] (a figure of 12% is quoted as "typical" in [F]). In the UK the salary of a train driver ranges from £32K to £50K per annum. Since crew costs account for up to 50% of total operating cost, TrainTRACS and BusTRACS have brought huge savings for transport operators. To estimate these cost savings, we shall consider rail and bus transport separately.

(a) The UK rail passenger train operating cost, including the leasing of train units and track/infrastructure access charges, was about £6 billion in 2008-09 (McNulty Report, Table 3.5 [H]); we estimate crew cost to be 40%, i.e., £2.4 billion per annum. The train companies using TrainTRACS cover about 70% of the UK passenger trains [F]. Conservatively estimating the savings at 2%, 4% or 8% gives annual savings of £2.4bn x 70% x (2%, 4%, 8%) = £33.6m, £67.2m or £134.4m saving p.a. on crew scheduling cost to the UK rail industry alone [A,B].

(b) BusTRACS is used by about 25 bus companies in FirstGroup. In 2013, FirstGroup has sold part of its bus operations in London to Tower Transit, but Tower Transit has retained the use of BusTRACS. FirstGroup and Tower Transit together have about 9,000 buses. BusTRACS is also used by Translink in Belfast, which has about 300 buses. Unlike trains, buses only need one crew member per bus. However, accounting for rest days, annual and sick leaves the number of drivers employed would be more than the number of buses operated. Therefore, a low estimate of 11,000 drivers is justified. Assuming an average driver costs £38k per annum, total driver cost is £418 million. Therefore at 2%, 4% and 8%, the estimated cost savings are £8.36m, £16.7m and £33.4m per annum for UK bus companies [B].

(c) At 2% savings, we therefore estimate a minimum of £230 million overall savings brought by TrainTRACS and BusTRACS to bus and train companies over the entire period 1.1.2008- 31.7.2013; at 4% and 8%, our estimates are £460 million & £920 million, respectively [A,B,H]. (d) In December 2008 (after the West Coast Route Modernisation was completed), Virgin West Coast implemented a 30% increase in their train services and TrainTRACS was used to schedule their crews [B,G,I]. Only 6 crew members were added to their existing 1600 crew (an increase of 0.37%) [G,I].

4. The consistent savings and benefits accrued from using TrainTRACS have gained Tracsis respect and trust in the rail industry. This good reputation has enabled Tracsis to expand the TrainTRACS core business to include closely related planning processes of train unit scheduling and train crew rostering, and to related rail problems of performance and safety information management, data acquisition and monitoring, passenger count surveys [B,F].

Sources to corroborate the impact

A. Testimonial from the Director of Business Planning, First ScotRail, 2013.

B. Testimonial from the Chief Executive Officer of Tracsis Plc, 2013.

C. Announcement of The Small Cap Awards 2013, press release 25^th April 2013 http://www.smallcapawards.com/small_cap_awards_winners_announcement.pdf

D. "Fast track from academia to driving transport networks". Yorkshire Post, 18 October 2011.

E. Tracsis plc Interim and Final Results — regulatory reports and accounts 2008 to date.

F. Research analysis article on Tracsis, the Small Company Sharewatch, July 2012.

G. Kwan, RS "Case studies of successful train crew scheduling optimization". Journal of Scheduling, vol. 14, pp.423-434. 2011. DOI:10.1007/s10951-010-0212-y.

H. "Realising the potential of GB rail — final independent report of the rail value for money study — detailed report", Department for Transport, May 2011 (herein referred to as "the McNulty report"), http://www.rail-reg.gov.uk/upload/pdf/rail-vfm-detailed-report-may11.pdf.

I. "Implementing VHF", interview with Virgin Trains' Chief Operating Officer C. Gibb, in: "West Coast Route Modernisation", Special Supplement, Modern Railways, May 2009, 52-53.