Impact case study database
Saving time and money through industrial scheduling and optimisation algorithms
1. Summary of the impact
University of Stirling research has decreased demands on personnel time and delivered economic benefits for three industrial partners. The diverse impacts all share core combinatorial optimisation challenges, solved using our applied research into computational modelling, metaheuristic design, and search techniques (Figure 1).
Impact 1: Enhanced workforce scheduling for all 23,000 field engineers at British Telecommunications plc via our engineer scheduling system, underpinning savings to December 31 2020 of GBP1,293,000 for BT.
Impact 2: Our novel approaches to the automation of software bug fixing saved GBP1,460,000 in development costs at Janus Rehabilitation Centre (Iceland). An additional saving of at least GBP4,200,000 (to 2020) to the Icelandic economy comes from Janus’s use of our predictive modelling.
Impact 3: At KLM Royal Dutch Airlines, our research on automatically improving computer code increased the reliability of scheduling for 200,000 flights (reaching ~60,000,000 passengers), reducing KLM’s costs and saving a total of 2 years of personnel time. These benefits drove a fundamental shift in best practice towards adoption of automated software tuning across KLM and Air France development teams.
2. Underpinning research
Metaheuristics are a well-established family of techniques including stochastic local search and evolutionary algorithms. The underpinning research for our impact in this area has largely been funded by the EPSRC programme grant Dynamic Adaptive Automated Software Engineering (DAASE) EP/J017515/1, of which, University of Stirling led the Hyperheuristics research theme. This project explored automated search techniques for optimisation problems in both employee scheduling and software engineering. Specifically, finding the best algorithm to efficiently solve a given problem to a required quality, and understanding how different approaches to formulating problems affect search efficiency. Our novel approaches included development of new search operators, new encodings for solutions, new approaches to guide the search process and automated approaches known as hyperheuristics to tailor these to a particular application.
Employee scheduling is the assignment of duties to employees over a period so that certain organisational and personal constraints are satisfied. Our research has developed techniques for this and similar scale problems elsewhere, that were adapted and applied to employee scheduling problems at BT [see Impact 1]. Stirling’s Li proposed several hybrid methods to solve challenging combinatorial problems at an industrial scale. These have included Evolutionary Ruin & Stochastic Recreate (ER&SR) algorithm, combined with the Taguchi design of experiments method for parameter setting [ P1], Multi-Objective Simulated Annealing [ P2], and Variable Neighbourhood Search (VNS) combined with simulated annealing [ P3].
Search based software engineering (SBSE) applies search-based techniques like evolutionary algorithms to software engineering problems, such as improving existing source code. This spans from tuning hard-coded parameters, to moving lines of source around, to modifying individual keywords, variables and operators. Objectives targeted by the search include minimising failed tests (i.e. fixing bugs), increasing accuracy of computational models, minimising run time (i.e. increasing speed), or minimising energy consumption. We developed new SBSE approaches, including code micromutations [ P4], and automatically generating test cases [ P5]. One of the first real-world deployments for these two approaches was in Janus Rehabilitation management software [see Impact 2]. We also investigated systematic approaches to hyper-parameter tuning for improving the accuracy of machine learning software [ P6] and the fitness landscapes formed by different search operators [ P4]. This underpinned our work with KLM where we applied search-based methods to tuning their simulation software, Opium [see Impact 3].
The value placed on this work by each partner is demonstrated by their commitment to ongoing research collaboration. BT have funded a PhD studentship and supported an EPSRC Fellowship proposal with Brownlee. KLM have supported EPSRC project EP/N029577/2 on which Brownlee is a co-i. Janus are now partners on the (external, Lancaster University) EPSRC project EP/S005730/1 on which Haraldsson was a named researcher before returning to Stirling as a lecturer. The work with Janus has also led to ongoing collaboration between Haraldsson, the Icelandic Government, and two Icelandic rehabilitation associations [ E6].
An overview of the underpinning research and the impacts it led to is illustrated in Figure 1.
Figure 1. Overview of how Stirling research feeds into impact with each company
3. References to the research
(Stirling staff and postgraduates in bold text)
Li J., Bai R., Shen Y. and Qu R. (2015) Search with Evolutionary Ruin and Stochastic Rebuild: a Theoretic Framework and a Case Study on Exam Timetabling. European Journal of Operational Research 242, pp. 798-806. DOI: 10.1016/j.ejor.2014.11.002
Peng K., Shen Y. and Li J. (2015) A Multi-Objective Simulated Annealing for Bus Driver Rostering. Communications in Computer and Information Science, vol. 562, pp. 320-336, Springer. DOI: 10.1007/978-3-662-49014-3_29
Reid K., Li J., Swan J., McCormick A. and Owusu G. (2016) Variable Neighbourhood Search: A Case Study for a Highly-Constrained Workforce Scheduling Problem. Proc. of the 2016 IEEE Symposium Series on Computational Intelligence, IEEE Press. DOI: 10.1109/SSCI.2016.7850087
Haraldsson, S.O., Woodward, J.R., and Brownlee, A.E.I. and Cairns, D.E. (2017) Exploring Fitness and Edit Distance of Mutated Python Programs. In: Proc. EuroGP 2017, Amsterdam, Netherlands (LNCS 10196), pp. 19-34. DOI: 10.1007/978-3-319-55696-3_2
Haraldsson, S.O., Woodward, J.R. and Brownlee, A.E.I. (2017) The Use of Automatic Test Data Generation for Genetic Improvement in a Live System. 2017 IEEE/ACM 10th International Workshop on Search-Based Software Testing (SBST), Buenos Aires, 2017, pp. 28-31. DOI: 10.1109/SBST.2017.10
Brownlee, A. E. I., Burles, N. and Swan, J. (2017) Search-Based Energy Optimization of Some Ubiquitous Algorithms. IEEE Transactions on Emerging Topics in Computational Intelligence 1(3), pp. 188-201. DOI: 10.1109/TETCI.2017.2699193
Funding:
The above publications arose from the GBP6,800,000 (Stirling: GBP2,031,015) EPSRC programme grant Dynamic Adaptive Automated Software Engineering (DAASE) EP/J017515/1, Stirling PI: Edmund Burke Jun 2012 – Aug 2015, Gabriela Ochoa, Sep 2015 - May 2019.
P1 was also supported by Ningbo Natural Science Foundation (grant 2012A610026) and Natural Science Foundation of China (grants 70971044 and 71171087).
P2 was also supported by the Major Programme of National Social Science Foundation of China (grant 13&ZD175) and Natural Science Foundation of China (grants 70971044 and 71171087).
4. Details of the impact
Our research in novel optimisation approaches using metaheuristics has underpinned several industrial collaborations, and approaches developed by us have been adopted within several companies. The relationship with each company has been fostered over many years of collaboration, with personnel from Stirling and each respective company exchanging visits to explore possible application areas, present results, and seek feedback. Stirling staff were seconded to each partner (funded by the DAASE project and the companies) for multiple weeks to fully understand the business needs and identify interesting research problems. BT was a named partner on the DAASE project; Janus Rehabilitation and KLM were introduced to the project team by personal connections.
The applications are very different, but the underlying research techniques and ultimate benefits are common. The key impact in each company has been to save employee time: through more efficient allocation of jobs to the workforce and through faster running software. This indirectly leads to saving money as paid staff make better use of their time. These benefits have been demonstrated at three companies, two of which are international in scale:
Impact 1: Engineer Scheduling at BT
British Telecommunications plc operates a large-scale field engineering workforce to service its customers, and build and maintain its core telecommunications network. This is a critical piece of UK infrastructure connecting the majority of UK households and businesses, and resold by most UK Internet Service Providers. In order to meet demand, over 23,000 engineers are employed. Our work with BT has drawn on our group’s expertise to apply metaheuristics to automate and optimise the allocation of employees to jobs. This is underpinned by our research in workforce scheduling [ P3], and required the development of improved algorithms building on our earlier work [ P1, P2]. The impact on the logistics staff has been significant: the “iRoster” suite that we have co-produced, launched on 1/1/2018, has been attributed to savings of over GBP1,293,000 for BT (up to 31st December 2020, extrapolated from the GBP470,000 figure to 2nd October 2019 provided by BT). This is currently in the process of development in other regions of the business, signalling the ongoing and increasing impact of our work. This impact has been noted in a testimonial letter from BT Research: “the generated schedules furthermore provide a higher level of quality than the baseline solution at BT” and “algorithms and problem formulation provided by this project are part of a software suite known as iRoster… found to enable cost savings of £470,000 to date” [ E1]. It is also discussed in general terms in a magazine article [ E2]. The impact has had wide reach, scheduling all 23,000 engineers across the UK. BT’s confidence in the system is demonstrated by its continued and expanding use: “the work produced in this project has been successfully re-implemented for use in roster optimisation for desk-based resources” [ E1].
Impact 2: Patient Management at Janus Rehabilitation
Janus Rehabilitation is an independent vocational rehabilitation centre located in Iceland. It provides a structured programme of therapy to help people recovering from physical and mental health issues, enabling them back into education or work. Janus treats around 150 patients at any one time (12% of the total for Iceland), and their work saved Icelandic society GBP8,000,000 over 2017-2019. It is one of the three largest such facilities after the Icelandic Government’s own hospital. Our research led to impact on Janus’ operations through applications developed by Haraldsson; with their testimonial noting that “collectively, [Dr Haraldsson’s] research and expert consultations have impacted individuals, JR, and Icelandic society as a whole”. Our research enabled an organisation (Janus) whose main business is not software development to have access to bespoke software suited to their needs with ongoing support and maintenance at a fraction of the usual cost. This was achieved through an automatic bug-fixing tool: our automated approaches to test-case generation [ P5] enabled this tool to replicate errors that were detected, and our code micro-mutation approaches [ P4] were deployed to fixing the errors: 22 bugs were repaired over a six-month period, noted by us in a reflective paper [ E3]. “Average post-delivery maintenance cost was decreased by approximately 50%” [ E4]. Limited developer time was thus freed to be spent on improving functionality. The bug-fixing tool is still live so this impact is ongoing. Janus estimate that application of our research has a significant financial savings impact of approximately GBP1,460,000: allowing Janus to have a business-critical management tool for around GBP40,000, where a competitor spent GBP1,500,000 on a similar system [ E4]. Furthermore, our software optimisation techniques were applied to enable rapid development of a predictive modelling tool for Janus; this has been used in the decision-making process for 395 patients since January 2017 [ E4]. In this time, Dr Haraldsson’s work “contributed towards…, significant increase of JR’s success rate” [ E4]: Janus’ success rate (people returning to education or work) has increased by 39%; it is estimated that this equates to an extra GBP1,400,000 million in savings to Icelandic society [ E4]; projected to GBP4,200,000 by the end of 2020, and Janus intend to continue to use the tool beyond 2020.
Impact 3: Scheduling & Best Practice at KLM
KLM Royal Dutch Airlines is an international airline carrying over 34 million passengers per year to 162 destinations using 209 aircraft. Our research in hyper-parameter tuning and optimisation of software was applied to the in-house software application ‘Opium’ at KLM by Brownlee during 2014-2015. Opium tested the flight schedules for all KLM flights worldwide; “totalling over 25,000 flights each quarter” [ E5] while it was in use. Opium was tuned using our approach to make more accurate predictions (meaning more reliable schedules for 60,000,000 passengers and less cost for the business) and running 20% faster for the same accuracy (meaning more schedules could be tested, with less human time taken, again reducing costs for the business). The improved software was in place for two years, equating to approximately 200,000 flights, before being replaced under a restructuring with Air France. During that time, system parameters were defined using University of Stirling research, replacing those developed “using around two years of developer time” [ E5] by KLM staff, thus saving future parameter-tuning time. The Senior Data Scientist/Innovation Project Manager considers the “most important long-term impact” of our collaboration to be the fundamental shift in best practice at Air France-KLM toward the setting of software parameters [ E6], saving them developer time and improving efficiencies.
5. Sources to corroborate the impact
E1. Testimonial Letter from Head of Service & Operational Transformation Research, BT.
E2. The workforce scheduling work is mentioned by Dr Gilbert Owusu (Head of Practice, Business & Operational Transformation at BT Research) in his article (entitled "Leveraging O.R. Techniques for Smarter Field Operations") published in the 2017 Spring Impact Magazine, which can be viewed/downloaded at https://issuu.com/orsimpact/docs/impact_3-1_web – pages 18-22.
E3. Paper reflecting on the use of automated program repair at Janus Rehabilitation: Haraldsson S, Woodward J, Brownlee A & Siggeirsdottir K (2017) Fixing bugs in your sleep: How genetic improvement became an overnight success In: 2017 Genetic and Evolutionary Computation Conference Companion, GECCO 2017, New York: Association for Computing Machinery, Inc. GECCO 2017: The Genetic and Evolutionary Computation Conference, 15.7.2017 - 19.7.2017, Berlin, Germany, pp. 1513-1520. Available at: https://doi.org/10.1145/3067695.3082517
E4. Testimonial Letter from Chief Executive Officer, Chief Medical Officer, and Chief Scientific Officer at Janus Rehabilitation, Iceland.
E5. Paper reflecting on the use of the predictive modelling at Janus Rehabilitation: Haraldsson S, Brynjolfsdottir RD, Woodward J, Siggeirsdottir K & Gudnason V (2017) The use of predictive models in dynamic treatment planning In: 2017 IEEE Symposium on Computers and Communications (ISCC), Piscataway, NJ, USA: IEEE. IEEE Symposium on Computers and Communications (ISCC 2017), 3.7.2017 - 6.7.2017, Heraklion, Greece, pp. 242-247. Available at: https://doi.org/10.1109/ISCC.2017.8024536
E6. Testimonial Letter from Senior Data Scientist/Innovation Project Manager, KLM.
Additional contextual information
Grant funding
| Grant number | Value of grant |
|---|---|
| EP/J017515/1 | £6,800,000 |