Summary of the impact

Research on designing mathematical methods for optimisation carried out at the University of Southampton has been fundamental to the development of software solutions for transportation problems and has directly led to the growth and commercial success of the niche software company, Logical Transport. Additional beneficiaries are local councils — who have obtained school bus schedules that typically reduced the number of required vehicles by 10-20% and miles driven by 12-15% and have an information management tool for better decision making — and passengers who have experienced improved service quality.

Underpinning research

UK local councils spend £1 billion every year on school-bus transportation. For special needs children, where wheelchairs and escorts are needed and buses can be flexibly configured to hold different numbers of passengers and wheelchairs, the routing and scheduling of buses is very complex. A workable schedule must correctly accommodate the child and their needs, and route the bus to arrive at the address side of the road and not require the bus to make U turns. A good schedule would seek to minimise the number of vehicles, and reduce passenger ride-times and CO₂ emissions. Research carried out by Julia Bennell, Professor of Management Science, Management School (1997-) and Chris Potts, Professor of Operational Research, Mathematics (1986-) has led to the development of software that allows users to schedule passenger transportation for a range of complex scenarios. Research was based on a set of methodologies designed to find good solutions to difficult optimisation problems known as "local search algorithms". Research extended the state of the art in routing by designing new ways of representing the road network, and in optimisation by accommodating a whole range of practical complex constraints while producing fast solution times and guaranteeing a usable final solution.

The underpinning research that led to the impact arises from the fifteen years' experience of developing effective local search methods for a variety of problem types, and the research undertaken with Logical Transport (LT), a niche software company, through

• a short LT funded research project (2004) contributing to the optimisation methodology for the vehicle scheduling component of their main product, LT Enterprise,
• Knowledge Transfer Partnership (KTP) in conjunction with Dr Nik Pearson (Mathematics 2007-2009) (grant 1, 2007-2010) resulting in new routing algorithms and optimisation methods for the many-to-one extension of LT Enterprise,
• Knowledge Transfer Secondment (KTS) (grant 2, 2010-2011) that generalised and improved the optimisation methods resulting in Routeforce add-on to LT Enterprise.

Research by Bennell on designing local search algorithms was fundamental in the work with LT to improve their software. The particular problem shares common features of sequencing that are used in cutting and packing [3.1], machine scheduling [3.4] and shipping [3.5]. Her work on problems with multiple objectives [3.2] directly fed into the more recent work with LT that provides the facility to select one or more KPIs for optimisation. Results of the research are presented in [3.6] and [3.3].

Working directly with LT, Bennell and Potts used their research experience with these methodologies to improve LT scheduling and routing algorithms in LT Enterprise. During the KTP, Bennell, Potts and Pearson developed a detailed algorithm for a `many-to-one' vehicle scheduling problem i.e. passengers are transported from many starting points to one destination. Significant methodological innovation was required to deal with problem constraints including a fleet of mixed vehicles types, variable travel times, flexible vehicle seating for wheelchairs, and requirements for escorts. The main outcome was a scheduling software extension to LT Enterprise, (many-to-one) that allows the user to create and analyse school bus schedules and generate management information for decision making. For the KTS, Bennell and Potts working with Pearson (employed since 2009 by LT as a senior researcher) extended the KTP research to look at day-care scheduling, where there are many pickup locations and a few destinations. This resulted in the development of the next generation of scheduling software called RouteForce.

References to the research

Publications

Grants

Prof Chris Potts and Prof Julia Bennell, KTP: Resource scheduling algorithms, DTI, January 2007 - Dec 2009, £100k.

Prof Julia Bennell and Prof Chris Potts, KTS: Day care scheduling algorithms, EPSRC, May 2010 - July 2011, £20k.

Details of the impact

Research by Bennell and Potts and the development of many-to-one and RouteForce have directly led to commercial gains for Logical Transport (LT), financial and carbon emission savings for local councils and other transport providers, and improved experience for passengers.

Benefits to Logical Transport and private industry

As a result of LTs collaboration with Southampton, LT has grown from five employees and a single product to fifteen employees, with a 58% increase in turnover between 2009/10 and 2010/11 and moving from a net loss to net profit [5.1]. Since 2010, LT has used the Many-to-One scheduling software as part of its core scheduling product [5.2]. This has largely been used in its consultancy services where LT perform a full analysis of the school bus requirements for their clients. Four local authorities and two private schools used this service and the introduction of RouteForce in 2012 attracted two further local authority clients.

Many-to-One and RouteForce have provided LT with the tools to realise a significant competitive advantage as they can deal with differing needs of passengers, flexible capacity vehicles and restrictions in the real road network. Competitors' routing software sees passengers as homogeneous and fails to take into account practical issues such as arriving on the address side of the road or the difficulty in making U-turns. The Southampton-developed tools allow for efficient scheduling of passengers to vehicles according to any of five key performance indicators: number of vehicles, mileage, CO₂ emissions, vehicle time on road, passenger time in vehicle. LT can prioritise different KPIs for clients. [5.3]

LT software that includes the capabilities developed via the collaborations, are used by a range of clients for transport scheduling, such as the National Express Hoppa Service (2009) [5.4] for transferring passengers between hotels and airport terminals. As a result, National Express are able to provide a fixed schedule service during peak times and flexible scheduling during off-peak hours. This has delivered improved customer service in off-peak hours, while reducing operational overheads and environmental impact. Introduction of the demand response service has resulted in a 30% drop in expenditure for National Express without sacrificing customer service. Alan Willson (former Director of Business Development at LT) said: "(the routing engine developed in conjunction with the University of Southampton) undoubtedly helped to secure the deal with National Express."

The financial benefit to LT is quantified in a statement in 2009 by Dale Howarth, Business Development Manager at LT, said: "Over the past two years our revenues have increased by over 300%. Our relationship with the University of Southampton has, and continues to be a significant contributor to this success". [5.5]

Advantages to local authorities and schools

School transport represents a major expenditure for local authorities and schools. The pressure on public finances in recent years has meant that the cost of school bus services has come under particular scrutiny. Since 2010, LT have worked with Bristol, Camden, Devon, Enfield, Halton and Telford local authorities on school/day care transportation scheduling and [name of college removed for publication], Trowbridge and St Dunstan's School on school bus scheduling. London Borough of Camden run a fleet of 11 fully accessible buses for 173 special needs school children, 23 buses for adult transportation to day care, and 5 demand responsive buses for adults who cannot access public transport. Each bus costs £100k per year. The study showed a 20% reduction in vehicles and a 61% reduction in miles driven (2013). The Transport manager, Callum Johnson, cited the impact of LT software as one of management information for decision-making including capacity analysis, and accurate reporting of passengers that is important for supporting their safeguarding policy. They are about to implement Routeforce, which he states "will make a massive difference" in their ability to reduce costs and environmental impact [5.6]. At [name of college removed for publication], Trowbridge, the study showed a 19% reduction in vehicles and a 19% reduction in miles driven, with an estimated minimum cost saving of £100K per annum (2012).

Benefits to passengers

The studies undertaken by LT for the mentioned councils using Many-To-One and Routeforce have shown higher quality service in terms of ride time and/or reduced fuel emissions through better routing. School children and day-care patients benefit from shorter ride times and users of National Express Hoppa Services benefit from a more responsive service. Since the software considers seat configuration, passengers that have very special needs can be accommodated, for example, requiring an escort and vacant seats next to or in front. This provides a better service for these children and aids their social integration.

Sources to corroborate the impact

5.1 Statement provided and contact for further corroboration:: Director, Logical Transport 5.2 Many2One website: http://www.many2one.co.uk/about-logical-transport.html and Kids 2 School
http://www.many2one.co.uk/online_school_transport_planning_scheduling.html

5.3 Contact: Senior Analytical Consultant, Logical Transport

5.4 Case study, Logical Transport:http://www.logicaltransport.com/hoppa.html

5.5 Presentation by Dale Howarth "How Logical Transport Ltd have successfully used a Knowledge Transfer Partnership to improve competitiveness/productivity" at a seminar organised by Solent Synergy Ltd on "How Local University Expertise can Improve Business Performance", held at Quob Park, Titchfield Lane, Wickham, 28 January 2009.

5.6 Contact: Transport Manager, Camden Council, London Borough of Camden.