Optimisation and Illumination of a Real-world Workforce Scheduling and Routing Application via Map-Elites

Urquhart, Neil; Hart, Emma

Abstract

Workforce Scheduling and Routing Problems (WSRP) are very common in many practical domains, and usually have a number of objectives. Illumination algorithms such as Map-Elites (ME) have recently gained traction in application to design problems, in providing multiple diverse solutions as well as illuminating the solution space in terms of user-defined characteristics, but typically require significant computational effort to produce the solution archive. We investigate whether ME can provide an effective approach to solving WSRP, a repetitive problem in which solutions have to be produced quickly and often. The goals of the paper are two-fold. The first is to evaluate whether ME can provide solutions of competitive quality to an Evolutionary Algorithm (EA) in terms of a single objective function, and the second to examine its ability to provide a repertoire of solutions that maximise user choice. We find that very small computational budgets favour the EA in terms of quality, but ME outperforms the EA at larger budgets, provides a more diverse array of solutions, and lends insight to the end-user.

Citation

Urquhart, N., & Hart, E. (2018, September). Optimisation and Illumination of a Real-world Workforce Scheduling and Routing Application via Map-Elites. Presented at Parallel Problem Solving from Nature (PPSN) 2018, Coimbra, Portugal

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Parallel Problem Solving from Nature (PPSN) 2018
• Start Date: Sep 8, 2018
• End Date: Sep 12, 2018
• Acceptance Date: May 14, 2018
• Online Publication Date: Aug 22, 2018
• Publication Date: 2018
• Deposit Date: May 23, 2018
• Publicly Available Date: May 29, 2018
• Publisher: Springer
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743
• Book Title: Parallel Problem Solving from Nature – PPSN XV 15th International Conference, Coimbra, Portugal, September 8–12, 2018, Proceedings, Part I
• Chapter Number: TBA
• ISBN: 978-3-319-99252-5
• DOI: https://doi.org/10.1007/978-3-319-99253-2_39
• Keywords: Workforce scheduling and Routing problems, WSRP, Evolutionary Algorithm (EA), Map-Elites (ME)
• Public URL: http://researchrepository.napier.ac.uk/Output/1186833
• Contract Date: May 23, 2018