The last decade or so has seen sustained research effort directed at hyper-heuristic methods, much of which is a result of pioneering work done by researchers within the OR Group at QMUL. Unlike traditional search methodologies, hyper-heuristics operate over a search space of heuristics or heuristic components to generate methods which are much more general than those which operate over a search space of solutions directly. Hyper-heuristics typically fall under two categores, those which select and combine multiple existing heuristics to exploit the strengths and weaknesses of each, and those whick generate new heuristics from existing heuristics and/or heuristic components. Core goals of automating the heuristic design process include reducing the time required to develop such methods and reducing the burden on the human involved in the development cycle.
The OR Group continues to set the international research agenda in automated heuristic design, in part through the DAASE EPSRC programme grant and ongoing collaboration with world-leading researchers in the area.
According to the most-likely growth forecast scenario for the whole Europe by 2035, the number of flights will increase to 14.4 millions, which is 50% more than in 2012 with an average annual growth of 1.8%. This growth will be limited by the available capacity at the airports, based on capacity expansion plans reported by airports in a new survey. As a result, in the most-likely scenario, around 1.9 million flights (constituting 12% of the demand) will not be accommodated in 2035. Furthermore, congestion at airports will increase quite rapidly once the capacity limits are reached, leading to extra pressure on the network, and more delays.
OR-MASTER (Mathematical models and algorithms for allocating scarce airport resources) is a two site project between Lancaster University and Queen Mary University, funded by the Engineering and Physical Sciences Research Council (EPSRC). It represents a strong partnership between academia, the air transport industry and policy makers. The project grant aims to meet the major scientific challenge of developing novel mathematical models and solution approaches for effective capacity deployment at congested airports in the UK and across the world. Airport capacity is expressed in slots, where a slot identifies a time interval on a specific date during which a carrier is permitted to use the airport infrastructure for landing or take-off. Current slot allocation procedures suffer from the following limitations: (i) oversimplified models of the objectives and operational/regulatory constraints; (ii) insufficient capture of the interactions encountered in airport networks; and (iii) the use of empirical and ad hoc strategies for determining declared capacity, without taking into account the complexity of the real-world problem and the uncertainties encountered in airport capacity assessment. Consequently, this creates allocation inefficiencies which, in turn result in poor airport capacity utilization with negative impacts on airport revenues, airline operating costs, the level of service offered to passengers and the environment. The proposed mathematical models and optimization strategies will take into account a wide range of operational/regulatory constraints and objectives of all stakeholders, for a single airport and for a network of airports. Furthermore, algorithms that will be developed and tested during this project will provide essential support for the complex large scale capacity allocation problems that arise in other types of transportation networks, including rail networks.
The project partners include Advanced Systems for Air Traffic Control (SICTA), Airports, Council International (ACI) Europe, Eurocontrol, HALA SESAR Research Network, NEXTOR-II Consortium, Zurich Airport, Air France KLM, Athens International Airport, German Aerospace Centre DLR, Massachusetts Institute of Technology, Northrop Grumman Park Air Systems, Airport Services Association, CRIDA A.I.E, Goldair Handling, NATS Ltd, and SESAR.
Search methodologies have been applied to solve a wide variety of real-world scheduling problems. One of these areas is healthcare, where surgery admission planning and nurse rostering represent two examples of problems that can be solved using computational search techniques. Surgery admission planning seeks to optimise the use of resources involved in performing surgery within a hospital or healthcare center, by assigning slots for patients to undergo surgery whilst respecting the constraints placed on surgery teams, equipment and operating theatre availability. Nurse rostering is a specific instance of the personnel scheduling problem, where a roster defining shift patterns for a set of nurses must be generated for a ward considering a number of practical constraints. Examples of constraints on this problem include: restrictions on shift patterns (e.g. nurses can not work more than a certain number of consecutive days), requirements that staff with a particular skill set must be present at certain times, fair balance of weekend shifts between nurses etc.
The OR Group has a number of ongoing research projects, using exact and metaheuristic approaches to tackle real instances of both of these problems in partnership with healthcare institutions in the UK, Norway and Iceland.
We carry out investigations into metaheuristic methodologies, for both theory and practice, including:
Repairing defects is an important part of the development of any software. Defects occur as a result of human errors in coding or logic and they might impact software functionalities, decrease its quality and cause security issues. Developers spend more than 50% of their time finding and repairing defects. This time could be significantly reduced by using automatic tools that locate, predict and repair defects.
Together with the Fixie project partners, the OR group conducts research in exploiting defect localisation and prediction for automated program repair. Knowing the location of a defect (faulty lines), our tool applies a search-based algorithm to modify these faulty lines and find a repair. The repair is verified by Unit tests. When the location of a defect is predicted, our tool modifies the faulty code to decrease the predicted defectiveness.
Out tool will mark code in an IDE and suggest repairs to developers in an early stage of the software development (even before testing) to avoid having more complex and costly defects in the future.