Neural Network Assisted Large Neighborhood Search for Personnel Rostering

Abstract

Allokering av arbeidskraft er en essensiell oppgave hos mange organisasjoner som kan være både kompleks og tidkrevende. Til tross for dette er den dominerende praksisen å sette opp timeplaner manuelt. Vår industripartner, Visma Resolve, leverer programvareløsninger for å automatisere skiftplanleggingsprosessen. Deres programvareløsning må balansere generalitet og spesifisitet for å appellere til mange ulike kunder. Vi kaller det generelle skiftplanleggingsproblemet til Visma Resolve for Resolves skiftsplanleggingsproblem (Resolve Rostering Problem - RRP), og Visma Resolves programvareløsning bruker heuristiske løsningsmetoder for å løse det. På grunn av den voksende populariteten og utviklingen til maskinlæring har Visma Resolve uttrykt at de ønsker å integrere maskinlæring i deres eksisterende løsning. Også innen operasjonsanalysemiljøer har maskinlæringsmetoder blitt populære for å løse kombinatoriske optimeringsproblemer, hvilket gjør det til et spennende akademisk forskningsfelt.

Denne masteroppgaven har som formål å forene teknikker fra operasjonsanalyse og maskinlæring. Vi presenterer et nevralt nettverk-assistert nabolagssøk (Neural Network Assisted Large Neighborhood Search - NNALNS) som integrerer et nevralt nettverk i et adaptivt stort nabolagssøk (Adaptive Large Neighborhood Search - ALNS). Vi trener det nevrale nettverket til å lære seleksjonsstrategier for operatorer ved å bruke teknikker fra forsterket læring, hvilket erstatter den adaptive læringsmekanismen til ALNS. NNALNS bruker problemspesifikke og søksbaserte attributter som input til det nevrale nettverket for å beskrive tilstanden i løpet av søket.

Resultatene i masteroppgaven viser at NNALNS klarer å utkonkurrere ALNS på alle instanser utenom én når det nevrale nettverket er trent og testet på den samme instansen. NNALNS viser også evne til å kunne lære gode, generelle operatorseleksjonsstrategier som kan benyttes på ulike probleminstanser. I praksis kan disse resultatene peke mot at det er fordelaktig å bruke forhåndstrente operatorseleksjonsstrategier. RRP-instansene for en spesifikk kunde av Visma Resolve er ofte like i struktur mellom planleggingsperioder og kan derfor løses av NNALNS uten å måtte trene nye nevrale nettverk.

Ved å berike tilstandsrepresentasjonen med problemspesifikke attributter så klarer NNALNS å sanke flere belønninger (rewards). Likevel kan en mulig dissosiasjon mellom belønninger og objektivverdi hemme en økning i objektivverdi.

Vårt hovedbidrag er å inkludere en problemspesifikk tilstandsrepresentasjon og implementasjonen av operatorer som er skreddersydd for RRPet. I tillegg utgjør NNALNS en nyskapende løsningstilnærming til skiftplanleggingsproblemer og bidrar til å lukke gapet mellom maskinlæring og operasjonsanalyse.

Personnel rostering is an essential task for many organizations that can be complex and time-consuming, yet it is often done manually. Our industry partner, Visma Resolve, provides software solutions to automate the shift scheduling process, which must balance generality and specificity to appeal to their diverse customers. We denote this general shift scheduling problem as the Resolve Rostering Problem (RRP). Visma Resolve's software solution uses a heuristic approach to solve their rostering problem. Due to the recent popularity and advances in machine learning technology, Visma Resolve have expressed interest in integrating such technology into their solutions. Machine learning methods are also becoming increasingly popular in operation research communities to solve combinatorial optimization problems, making it an interesting academic research field.

This thesis aims to combine techniques from operations research and machine learning to solve a general shift scheduling problem. We present a Neural Network Assisted Large Neighborhood Search (NNALNS), which integrates an Artificial Neural Network (ANN) in an Adaptive Large Neighborhood Search (ALNS). Using reinforcement learning techniques, we train the ANN to learn operator selection policies, replacing the online learning mechanism of ALNS. NNALNS uses problem-specific and search-based features as input to the ANN to provide information on the state during the search.

The results in this thesis show that NNALNS manages to outperform ALNS on all but one of the problem instances when the ANN is trained and tested on the same instance. NNALNS also exhibits an ability to learn good, generalized operator selection policies applicable to different problem instances. In a real-world use case, these results points in favor of using pre-trained policies. The RRP instances for a particular customer of Visma Resolve are often similar in structure between scheduling periods and can be solved by NNALNS without training new selection policies.

By enriching the state representation with problem-specific features, NNALNS obtains more rewards from the reinforcement learning environment. However, a possible disassociation between rewards and obtained objective values inhibits an increase in objective value.

Our main contribution is the inclusion of an enriched state representation of the RRP and the design of tailored operators for the problem. In addition, NNALNS constitutes a novel solution approach to personnel rostering problems, bridging the gap between machine learning and operations research.