Planning and Optimisation
Research activites
The Planning and Optimisation Group is involved in the design and application of mathematical optimisation techniques to real life problems, particularly in the areas of scheduling and packing. These techniques can be used to introduce efficiency and reduce waste in the logistical operations of companies and government agencies.
One vibrant area of research in this group concerns the problem of timetabling. Universities, for example, periodically face the burden of scheduling exams and lectures so that a variety of complex, and often conflicting constraints are met. Members of the group have previously designed methods for such problems and were also involved in the organisation of the Second International Timetabling Competition in 2006-7 which allowed researchers from across the globe to design and test their algorithms on real-life problems in a competitive environment. The resources generated from this competition continue to stimulate new work by providing a useful access point into the field.
Members of the group are also active in the area of sports timetabling, where the aim is to produce schedules that are fair to all teams and that also satisfy constraints regarding pitch availability, television requirements etc. The group has previously worked with the International Rugby Board and the Welsh Rugby Union and has used metaheuristic search techniques to produce schedules for the 1999 Rugby World Cup, Welsh domestic rugby leagues, and all international rugby fixtures over a 12-year period.
The Planning and Optimisation Group have also published widely in the field of partitioning problems. Such problems arise regularly in industry, transportation and logistics, and include multi-dimensional packing and balancing problems, stock cutting problems, rostering problems and graph-theory. Stock cutting problems, for example, arise in areas such as the clothing and building industries, where the aim is to cut a set of predefined and possibly multi-dimensioned items from a set of equi-dimensioned “stocks” such that the wastage is minimised (thus encouraging economic savings). Previous research by the group has resulted in methods achieving state of the art results on popular benchmark problems (some of which have originated from real-world industrial processes), as well as the analysis and solving of new cutting problems provided to us by industrial partners.
Finally, the group is also investigating dynamic routing problems – that is routing problems where requirements change over time. An example is where a company receives new orders during the day and has to re-route delivery vans to the new customers while still minimising the distance travelled. High-quality solutions have been achieved using ant colony optimisation and our methods have also been applied to large scale static problems in order to divide problems into more manageable parts.