Towards More Effective Multi-objective Meta-Heuristics to Solve Complex Combinatorial Problems

Lead Research Organisation: University of Nottingham
Department Name: School of Computer Science

Abstract

This research project proposes the investigation of a number of challenging ideas in the field of multi-objective combinatorial search. Most of the research in this area has been based on recycling knowledge acquired from research on the single-objective case and this has inspired the extension of many single-objective techniques to their multi-objective variants. Many of these are extensions from evolutionary techniques such as genetic algorithms, evolutionary strategies, particle swarm optimisation and others. There are some extensions of other meta-heuristics such as tabu search and simulated annealing to multi-objective variants. Evolutionary approaches have received most of the attention in multi-objective heuristic search but I believe that a wider range of meta-heuristic techniques should be investigated. The research themes proposed here represent a considerable shift in emphasis. Specifically, the aim is to conceive more effective multi-objective meta-heuristics to tackle complex combinatorial problems in a more effective and efficient manner than the current state of the art is capable of. This proposal aims to re-think the design of multi-objective meta-heuristics by developing them within the multi-objective paradigm instead of modifying known single-objective approaches.
 
Description The project was successful in our goal of developing more effective optimisation algorithms to tackle complex multi-objective optimisation problems. Many real-world scheduling, planning and design problems are multi-objective in the sense that several conflicting criteria should be considered when assessing the quality of solutions. For example, tour cost vs. route flexibility when developing transportation plans, or rota cost vs. personal preferences satisfaction when developing workforce schedules. Prior to this project, many specialised multi-objective algorithms had been developed and reported in the literature, but such algorithms had been successful mostly on continuous optimisation problems with less reported success on combinatorial problems. The maim outcome of this project has been the development of a very effective and efficient algorithm, called Evolutionary Multi-objective Simulated Annealing Algorithm (EMOSA), that outperforms other state-of-the-art algorithms when solving two multi-objective benchmark problems, the multiple knapsack problem and the travelling salesman problem. These two problems are the basis for many real-world problems such as timetabling and scheduling, transportation planning, office space planning and management, etc. We identified several important principles and strategies that are beneficial in developing algorithms for complex multi-objective optimisation problems. Self-adaptation allows the algorithm to react to the multi-objective aspects of the problem, competition and cooperation between solutions allows to better explore the space of possible solutions to the problem, simultaneous multiple solution representations allows the algorithms to visit more possible solutions in the same computation time, combining evolutionary and local search is key when tackling multi-objective combinatorial problems. Overall, the outcomes of this project have been: 1) the identification of a set of good principles and strategies to tackle multi-objective combinatorial optimisation problems, 2) the development of EMOSA, an approach that outperforms other state-of-the-art algorithms, and 3) the application of the above to several multi-objective problems including travelling salesman, multiple knapsack and quadratic assignment problem, which are base problems for many real-world applications.
Exploitation Route The findings have already been put to use as described below. Taking the findings forward can be achieved by further application to the various projects in collaboration with industrial partners that we have in the ASAP research group.
The findings of this research have been put to use in three specific projects: two KTP (Knowledge Transfer Partnership) projects and one Knowledge Transfer Secondment (KTS). One KTP project, from January 2010 to December 2012, consisted on developing a routing optimisation engine for 3T Logistics, a UK company that delivers logistic planning for the HGV transportation industry. The other KTP project, from February 2014 to February 2016, consists on the development of a personnel scheduling engine for Webroster, a UK company that delivers personnel scheduling software for the home care sector. The KTS project consisted in developing the formal computational optimisation model and benchmark the real world workforce management problems for Webroster in preparation for the KTP grant.

The better understanding and generated knowledge on search strategies to tackle multi-objective combinatorial optimisation problems was also taken forward by the PhD research student (Juan Castro-Gutierrez) associated to this award project. This PhD student was funded by the University of Nottingham to complement the funding of this project by EPSRC. The PhD project developed a number of techniques to tackle multi-objective vehicle routing problems. This PhD was completed in March 2012. A current PhD student is working on extending this work in the context of home care workforce scheduling. This PhD project is due to be completed in January 2017.
Sectors Communities and Social Services/Policy,Digital/Communication/Information Technologies (including Software),Healthcare,Leisure Activities, including Sports, Recreation and Tourism,Transport
 
Description The findings of this research have been put to use in three specific projects: two KTP (Knowledge Transfer Partnership) projects and one Knowledge Transfer Secondment (KTS). One KTP (7449) project, from January 2010 to December 2012, consisted on developing a routing optimisation engine for 3T Logistics, a UK company that delivers logistic planning for the HGV transportation industry. The other KTP (9240) project, from February 2014 to February 2016, consists on the development of a personnel scheduling engine for Webroster, a UK company that delivers personnel scheduling software for the home care sector. The KTS project internally funded by the University of Nottingham, consisted in developing the formal computational optimisation model and benchmarking the real world workforce management problems for Webroster in preparation for the corresponding KTP (9240) grant. More specifically, some of the algorithmic techniques developed in this award project were transferred to the optimisation engine software developed for 3T Logistics in the KTP project. This optimisation engine is now part of the software suite that 3T Logistics commercialise and is a crucial part of their business. This impact on 3T Logistics, was the subject of an impact case study in the REF2014 return for the School of Computer Science at the University of Nottingham.
First Year Of Impact 2011
Sector Transport
Impact Types Economic
 
Description Impact Acceleration Account - University of Nottingham 2012
Amount £9,000 (GBP)
Funding ID EP/K503800/1 
Organisation Engineering and Physical Sciences Research Council (EPSRC) 
Sector Public
Country United Kingdom
Start 04/2015 
End 08/2015
 
Description Knowledge Transfer Partnership
Amount £55,996 (GBP)
Funding ID KTP 7074 
Organisation Innovate UK 
Sector Public
Country United Kingdom
Start 02/2009 
End 02/2011
 
Description Knowledge Transfer Partnership
Amount £83,530 (GBP)
Funding ID KTP 7449 
Organisation Innovate UK 
Sector Public
Country United Kingdom
Start 01/2010 
End 01/2012
 
Description Knowledge Transfer Secondments May 2012
Amount £9,871 (GBP)
Funding ID KTS 32 
Organisation University of Nottingham 
Sector Academic/University
Country United Kingdom
Start 07/2012 
End 09/2012