Using MAP-Elites to support policy making around Workforce Scheduling and Routing

Urquhart, Neil; Hart, Emma; Hutcheson, William

Abstract

English abstract: Algorithms such as MAP-Elites provide a means of allowing users to explore a solution space by returning an archive of high-performing solutions. Such an archive, can allow the user an overview of the solution space which may be useful when formulating policy around the problem itself. The number of solutions that can potentially be returned by MAP-Elites is controlled by a parameter d that discretises the user-defined features into `bins'. For a fixed evaluation budget, increasing the number of bins increases user-choice, but at the same time, may lead to a reduction in overall quality of solutions. We undertake a study of the application of Map-Elites to a Workforce Scheduling and Routing problem, using a set of realistic instances based in London.

German abstract: Algorithmen wie MAP-Elites bieten Nutzern ein Mittel, um einen Lösungsbereich unter Rückgriff auf ein Archiv leistungsstarker Lösungen zu erkunden. Ein solches Archiv kann dem Nutzer einen Überblick über den Lösungsraum geben, der es ihm erlaubt, selbst eine Verfahrensweise für das Problem zu formulieren. Die Anzahl der möglichen Lösungen, die von MAP-Elites zurückgespielt werden, wird durch einen Parameter d gesteuert, der die benutzerdefinierten Funktionen in „Bins“ diskretisiert. Gegen ein festgelegtes Bewertungsbudget wird die Anzahl der Bins erhöht, was wiederum die Benutzerauswahl erhöht. Dies kann aber gleichzeitig zu einer Verringerung der Gesamtqualität der Lösungen führen. Wir führen eine Studie über die Anwendung von MAP-Elites für die Personaleinsatzplanung und ‑weiterleitung mit einem Set realistischer Instanzen mit Sitz in London durch.

Citation

Urquhart, N., Hart, E., & Hutcheson, W. (2020). Using MAP-Elites to support policy making around Workforce Scheduling and Routing. Automatisierungstechnik, 68(2), https://doi.org/10.1515/auto-2019-0107

• Journal Article Type: Article
• Acceptance Date: Nov 1, 2019
• Online Publication Date: Jan 22, 2020
• Publication Date: 2020-02
• Deposit Date: Nov 7, 2019
• Publicly Available Date: Jan 23, 2021
• Journal: Automatisierungstechnik
• Print ISSN: 0178-2312
• Publisher: Oldenbourg Verlag
• Peer Reviewed: Peer Reviewed
• Volume: 68
• Issue: 2
• DOI: https://doi.org/10.1515/auto-2019-0107
• Keywords: MAP-Elites; optimisation; routing
• Public URL: http://researchrepository.napier.ac.uk/Output/2296970