Research Output

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

  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.

  • Date:

    14 May 2018

  • Publication Status:

    Accepted

  • Publisher

    Springer

  • Library of Congress:

    QA75 Electronic computers. Computer science

  • Dewey Decimal Classification:

    006.3 Artificial intelligence

  • Funders:

    Edinburgh Napier Funded

Citation

Urquhart, N., & Hart, E. (in press). Optimisation and Illumination of a Real-world Workforce Scheduling and Routing Application via Map-Elites. In Proceedings of PPSN 2018

Authors

Keywords

Workforce scheduling and Routing problems, WSRP, Evolutionary Algorithm (EA), Map-Elites (ME),

Monthly Views: