Applying Optimization to the Tactical Planning in the Home Health Care
Master thesis
Permanent lenke
https://hdl.handle.net/11250/2777027Utgivelsesdato
2020Metadata
Vis full innførselSamlinger
Sammendrag
Hjemmetjenesten har som mål å tilrettelegge for mennesker med psykiske eller fysiske behov, slik at de kan bo hjemme så lenge som mulig. Norge står overfor en eldrebølge, og den norske hjemmesyketjenesten opplever en økt etterspørsel etter helsetjenester. Denne utfordringen kan håndteres gjennom anvendelse av optimering, ved å identifisere og redusere ineektivitet i ek- sisterende prosesser. Hjemmetjenesten generer ruter basert på lister som definerer behovene og preferansene til sine brukere. I dag lager de fleste hjemmetjenesteavdelinger rutene manuelt, basert på de ansattes erfaring med pasientene. Til tross for mange år med erfaring, gjør de utallige mulighetene for kombinasjoner i ruter det krevende å oppnå optimale ruter, når dette gjøres manuelt. Denne oppgaven tar utgangspunkt i dagsoptimerte ruter for å løse det ukentlige ruteplanleggingsproblemet (Weekly Routing and Sceduling Problem, WRSP), på et taktisk nivå.
Et litteraturstudie relatert til det daglige og ukentlige ruteplanleggingsproblemet i hjemmetjen- esten er gjennomført. Denne oppgaven fokuserer på planlegging på et taktisk nivå og løsningsme- toder som er i stand til å løse problemer av realistisk størrelse. Et lineært blandet heltallsproblem (Mixed Integer Linear Program, MILP) er modellert for å løse WRSP. Heltallsproblemet er for- mulert som et fler-objektiv optimeringsproblem, som tar for seg seks objektiver. Problemet tar sikte på å minimere kjøretid, og samtidig minimere ulemper for ansatte og brukere. Min- imieringen av disse ulempene sikres ved å etterstrebe en rettferdig fordeling av arbeidsmengden, minimere overtid og minimere tiden brukt til å utføre overkvalifisert arbeid. I tillegg etterstreber modellen å minimere overstiging av tidsvinduet til oppgaver, og sikre besøkskontinuitet.
En iterativ forbedrings-heuristikk (Iterative Improvement Heuristic, IIH) foreslås for å løse WRSP. IIH er en matematisk heuristikk som identifiserer og legger til jobber som er subop- timalt allokert til et nytt optimeringsproblem, som iterativt løses av MILP. En initiell ukeplan (Weekly Route Plan, WRP) brukes som utgangspunkt for heuristikken og denne er sammensatt av et sett med daglige optimerte ruter. MILP løser optimeringsproblemet ved å simultant real- lokere jobber, noe som reduserer risikoen for å stagnere i et lokalt optimum.
IIH kalibreres og valideres ved hjelp av testinstanser som er generert på bakgrunn av data levert av Visma Optimization Technologies. Løsningen generert av heuristikken sammenlignes med den initielle WRP-en, og valideringen viser at IIH produserer mer eektive ruter for alle inter- essentene av WRSP. IIH er også validert ved sammenligning med den eksakte MILP-løsningen.
Resultater fra disse testene viser at IIH utkonkurrerer MILP når WRSP er av virkelighetsnær størrelse. I gjennomsnitt oppnår den matematiske heuristikken 67% reduksjon i gap sammen- lignet med MILP-en.
Videre gjennomføres en studie av hvordan implementeringen av IIH kan påvirke de ukentlige rutene. Studien undersøker avveiningen mellom forbedring og endring av ruter, hvor målet er å gjøre få endringer for å oppnå mye forbedring i de eksisterende rutene. Resultatene viser at små endringer i de eksisterende rutene kan gi betydelige forbedringer i ruter, da 44.14 % av den totale mulige forbedringen kun krever 23% av de tilhørende totale endringene i de eksisterende rutene, for en gitt instans.
IIH blir også implementert på WRSP for å generere eektive ruter med hensyn til forskjellige interessenter av problemet, for å avdekke avveininger mellom de ulike objektivene. Resultatene fra testene viser at ansatte- og bruker-relaterte objektiver kan inkluderes uten at dette i stor grad går på bekosting av kostnadsrelaterte objektiver, eksempelvis kjøretid. Den optimerte løsningen reduserer nemling andelen av arbeidsuken som blir brukt på kjøretid med 9.7 % sam- menlignet med den initielle WRP-en, uten å påvirke de andre objektivene. Dette impliserer at IIH kan brukes til å løse virkelighetsnære WRSP, som oppnår mer kostnadseektive ruter, og som samtidig tar hensyn til ansatte- og brukerrelaterte objektiver. Dette vil øke kapasiteten til hjemmetjenesten og belyser potensialet for kostnadsreduksjon i hjemmetjenesten. The Home Health Care (HHC) aims to assist the elderly and people in need so that they can stay at home for as long as possible. As Norway is facing an age wave, the Norwegian HHC providers are experiencing an increased demand for health care services. This challenge could be managed through the application of Operational Research (OR), by identifying and reducing ineciencies in existing HHC processes. The HHC providers generate routes and scheduling plans based on the needs and preferences of their associated users. Today, most HHC providers base the generation of these routes on the employees’ experience, and the routes are manually created on a day-to-day basis. Despite years of experience, the numerous possibilities of com- binations in routes make it complicated to manually obtain optimal routes, and ineciencies concerning driving time or employee and user-related aspects occur. The introduction of OR could, therefore, prove to be interesting for the HHC. This thesis examines the possibility of utilizing OR to solve the complex problem of planning on a tactical level. The aim is to solve the Weekly Routing and Scheduling Problem (WRSP) of the HHC by allocating jobs to days and employees and obtain ecient routes without violating government or patient-related con- straining factors. The WRSP in the HHC is an extension of the acknowledged periodic Home Health Care Routing and Scheduling Problem (HHCRSP).
A literature study related to the daily and weekly problem of routing and scheduling in the HHC is conducted. This thesis is concerned with planning on a tactical level and focuses on solution approaches capable of solving realistic size problems. A Mixed Integer Linear Program (MILP) model is developed to solve the WRSP. The MILP is formulated as a multi-objective optimization problem comprising six terms, aiming to minimize driving time while also min- imizing employee and user inconvenience. The hindmost is ensured by implementing a fair distribution of workload, minimize overtime, and minimize time spent performing overqualified work. Also, minimizing violation of the time window and facilitating visit continuity is included.
An Iterative Improvement Heuristic (IIH) is proposed to solve the WRSP. The IIH is a matheuris- tic that identifies and adds sub-optimal allocated jobs from an initial Weekly Route Plan, to an optimization problem which is iteratively solved by the MILP. The initial Weekly Route Plan (WRP) is compounded by a set of daily optimized routes. A function is introduced to identify suboptimal allocated jobs concerning dierent objectives of the WRSP. The MILP solves the optimization problem by reallocating jobs simultaneously, which reduces the risk of reaching a local optimum.
The IIH is configured and validated using real-life test instances provided by Visma Optimization Technologies. The performance of the matheuristic is validated against the initial WRP, being a composition of daily optimized routes, exposing that the IIH consistently produces more ecient routes concerning all objectives of the WRSP. The IIH is also validated against the exact solution of the MILP, revealing that the IIH outperforms the MILP when solving realistic instances. On average, the matheuristic obtains a 67% reduction in gap compared to the MILP.
Additionally, a study of how the implementation of the IIH may aect the Weekly Route Plan is conducted. The study investigates the trade-o between improvement of- and impact on routes. It is proven that slight alterations of existing routes may produce relative significant improve- ments in routes, as 44.6% of the total improvement only requires 23% of the total changes in routes, for a given instance.
Lastly, the IIH is applied to the WRSP to produce ecient routes with respect to dierent aspects of the problem, to reveal trade-os between the stakeholders’ interests. This thesis finds that employee- and user-related objectives can be included and considered without going at the extent of cost-related objectives like driving time. The acquired solution decreases the share of the workweek spent on driving time by 9.7% compared to the initial weekly routes, without worsening the remaining objectives. This implies that the IIH can be utilized to solve realistic size WRSPs and achieve more ecient routes, while still taking user and employee convenient aspects into account. This increases the capacity of the HHC providers and points out the potential for cost-reductions in the HHC.