University of Leeds – Transport Crew Scheduling

A successful business called Tracsis has spent the last few years helping bus and rail firms to construct their crew timetables effectively, saving them over £230 million between 2008 and 2013.

Its software is now being used by 70% of the train companies currently operating in the UK, as well as the UK’s largest bus operator. And it all began at the University of Leeds.

The university’s work on crew scheduling dates back to Anthony Wren from the 1960s onwards, but it was largely focused on bus scheduling until the 1990s. At this point, the UK Government began privatising the railways, and organisations such as the EPSRC funded Leeds researchers to tackle the more thorny issue of rail crew scheduling.

A major breakthrough in their work is PowerSolver, an algorithm which is able to crack scheduling puzzles that were previously considered too complicated and daunting.

Raymond Kwan (middle) with postdoc Research Fellows Linus Lin and Eva Barrena

“In running any public transport service, there are two main resources: Vehicles and manpower”, says Dr Raymond Kwan, who has played a key role in the work for 25 years. “You have to schedule both resources to meet the timetables, or it doesn’t work. It’s complicated logistics. You have to devise a plan so that a train will always have someone to work on it, and the workforce will always be in the right place at the right time. And then – on top of that – it has to run like clockwork.”

Before Tracsis software rolled out in 2004, most train companies organised their crew schedules manually. This was not a simple process. A working timetable needed to be effective without requiring an unsustainable increase in staff, had to meet limits on shift length, and accommodate the required break times for crew members.

Even state-of-the-art systems could only cope with the complexity of crews of 100 or less. Most companies needed to schedule more than 150, or sometimes over 300. The complexity increased further when the transport network became denser.

“It’s an extremely difficult mathematical problem”, says Dr Kwan. “We can formulate a mathematical method to solve the problem, but maths has limitations on how complex it  can be.

“We wanted the most optimal results, but we also want to harness the maths in such as a way that we don’t overburden it. We adopt a similar approach to taking a picture on a camera. It could be tens of millions of megapixels, but when you’re sending it to your friends it’s more compressed while retaining as much of the image quality as possible. To churn out a result, we might compress the problem to a smaller size, deciding what detail to remove. Then we pick out the important characteristics and do another run, and then another. After all of these cycles we end up with a good set of data points.”

Bus and rail companies were trialling algorithms developed at Leeds as far back as 1994 to 1996. In 2004, Tracsis was founded to commercialise the software, and the company has grown into an international operation listed on the London Stock Exchange.

Early customers included ScotRail, First Bus and Translink, and others signed up following trials between 2004 and 2007. The company was floated on AIM in 2007. As of 2013, it employed 200 full-time equivalent staff in offices in Leeds, Derby, Tadcaster and Australia, and had market capitalisation of £46.7 million.

We have worked with a lot of train companies over the last 20 years”, says Dr Kwan. “With this software, we were able to show them that we could save them 2% to 12%, even compared to the most experienced schedulers.

“A big advantage is that by using a computer, the runtime is a lot shorter and can be done within a half hour, as opposed to a manual process that might take several weeks.

“Since the company started in 2004, the platform commercialisation side has become very mature, and there’s a team of developers working on it. The company has expanded a lot. It started with just four people at the beginning.

“We tackle a problem where there is a high potential for savings. The return is high and we produce excellent results, which is why the research has survived.”

Transport companies appreciate Tracsis software as it gives them the opportunity to be more efficient with their operation. For example, in December 2008, Virgin West Coast managed to increase their train services by 30% following modernisation despite only adding six crew members to their roster of 1,600.

It also caters for rescheduling at shorter notice. Tracsis software helped to schedule adjusted train services when the Rugby World Cup came to New Zealand, and it can also respond to the demands of large-scale sporting finals, engineering works or weather disruption.

It has been used by many rail contract bidders to prepare cost-effective and efficient bids.

Dr Kwan says: “Even though they sometimes have to do a bit of work to prepare the data and turn the results into a form they can use, they don’t mind as the savings are so great.”

Tracsis’ reputation in the industry has led to their business being employed to deal with other performance issues, such as safety information management, data monitoring and passenger count surveys. Meanwhile, the team at Leeds has since received an ESPRC grant for a three-year project investigating scheduling for train vehicles instead of crew.

“That’s probably even harder than scheduling crew”, says Dr Kwan. “It’s a very complex and interesting problem, and it’s one we’re working very hard to conquer.”