MagistrskodeloMentor:prof.dr.GašperFijavžLjubljana,2021 URNIKPOMOČINADOMU UNIVERZAVLJUBLJANIFAKULTETAZAMATEMATIKOINFIZIKOFAKULTETAZARAČUNALNIŠTVOININFORMATIKORačunalništvoinmatematika–2.stopnjaAndrejRus

UNIVERZA V LJUBLJANI

FAKULTETA ZA MATEMATIKO IN FIZIKO

FAKULTETA ZA RAČUNALNIŠTVO IN INFORMATIKO Računalništvo in matematika – 2. stopnja

Andrej Rus

URNIK POMOČI NA DOMU

Magistrsko delo

Mentor: prof. dr. Gašper Fijavž

Ljubljana, 2021

Zahvala

V prvi vrsti gre zahvala mentorju za vestno opravljanje svoje vloge, ki je znatno pripomogla k zaključku magistrskega dela, ki je pred vami. Poleg tega bi se rad zahvalil bratrancu Mateju in stricu Alešu za ekspertno znanje na področju pomoči na domu, razvijalcem orodja OptaPlanner za vse nasvete ter družini in dekletu, ki so mi stali ob strani ter me spodbujali pri čim hitrejšem zaključevanju.

Kazalo

Program dela vii

1 Uvod 1

1.1 Terminologija . . . 1

1.2 Organizacija dela . . . 2

2 Optimizacijski problem 3 3 Izbira orodja 7 3.1 OptaPlanner . . . 8

3.1.1 Računanje vrednosti rezultata . . . 8

3.1.2 Omejitve . . . 9

3.1.3 Spremenljivke . . . 10

3.1.4 Primerjalna analiza . . . 12

4 Predstavitev podatkov 15 4.1 Vhodni podatki . . . 15

4.2 Struktura programa . . . 20

5 Rezultati 23 5.1 Omejitve . . . 23

5.2 Dodajanje malice . . . 26

5.3 Prevzem in dostava kosila . . . 29

5.4 Izbira pristopa za optimizacijo . . . 33

5.4.1 Rezultati orodja za primerjalno analizo . . . 37

5.5 Vpliv omejitev na dobljeni rezultat . . . 40

5.5.1 Neupoštevanje omejitev za menjavanje in priljubljene . . . 41

5.5.2 Neupoštevanje časovnih oken . . . 42

5.6 Vpliv vhodnih podatkov na dobljeni rezultat . . . 44

5.6.1 Vrstni red . . . 44

5.6.2 Dolžina časovnih oken . . . 44

5.6.3 Število zaželenih zaposlenih . . . 46

6 Sklep 49

Literatura 51

Program dela

V delu obravnavajte problem oskrbe na domu kot poseben primer splošnejšega pro- blema usmerjanja vozil v prometu. Problem usmerjanja voznega parka, vehilcle routing problem, je eden od znanih in pogosto pojavnih NP-težkih optimizacijskih problemov. Kako najučinkoviteje obiskati vozlišča v omrežju, včasih tudi v predpisa- nem vrstnem redu, z množico vozil, ki dnevno začenjajo in zaključujejo v predpisanih lokacijah.

Problem oskrbe na domu lahko kot problem razvijemo iz problema usmerjanja vo- znega parka z dodajanjem najrazličnejših omejitev, ki so lahko časovne, razvrstilne, kakovostne. V magistrskem delu pridobite potrebne podatke ene (ali po možnosti več) različice tedenskega problema oskrbe na domu. Cilj dela je izdelava proto- tipa sistema za reševanje problema urnika oskrbe na domu, ki deluje na realističnih podatkih.

V delu najprej izdelajte kombinatorični opis problema. Za samo reševanje pa uporabite katerega od odprtokodnih paketov za kombinatorično optimizacijo. Pre- skusite različne optimizacijske pristope. Hkrati poskusite eksperimentalno pridelati nekaj ekspertnih vodil, ki bi jih lahko uporabil koordinator razporejanja oskrbe na domu — do katere mere lahko poostrimo posamezne omejitve, da to ne vpliva preti- rano na kakovost končne rešitve; kakšne morajo biti relativna razmerja med jakostmi posameznih omejitev. Svoje rešitve ovrednotite.

Kot začetno literaturo za problem usmerjanja voznega parka predlagam [17], začetna literatura za problem oskrbe na domu sta vira [2] in [4].

Osnovna literatura

[4] E. Benzarti, E. Sahin in Y. Dallery, Operations management applied to home care services: Analysis of the districting problem, Decision Support Systems 55 (2013) 587–598, doi: 10.1016/j.dss.2012.10.015

[2] J. F. Bard, Y. Sha in X. Q. A. I. Jarrah, The traveling therapist scheduling problem, IIE Transactions 46(7) (2014) 683–706, doi: 10.1080/0740817X.2013.

851434

[17] J. K. Lenstra in A. H. G. R. Kanm,Complexity of vehicle and scheduling pro- blemss, NetworksVol.11 No.02(1981) 221–227, doi: 10.1002/net.3230110211

Podpis mentorja:

Urnik pomoči na domu Povzetek

Pomoč na domu izvajajo domovi za starejše občane. Eden izmed večjih povzro- čiteljev stresa za koordinatorje je načrtovanje in izdelava urnikov delovnega časa oskrbovalcev. Te se v večini primerov izdelujejo “ročno” ter se kopirajo iz tedna v teden z malenkostnimi popravki. Problem izdelave urnika pomoči na domu je podo- ben problemu razvoza s časovnimi okni (vehicle routing problem with time windows), ki mu dodamo nekaj dodatnih omejitev. V magistrskem delu predstavimo izdelavo urnika s pomočjo orodja za reševanje problemov z omejitvami — OptaPlanner. Opi- sane so posebnosti tega orodja, način, kako vhodne podatke pripravimo, da jih lahko program obdela, kaj so bili glavni izzivi pri implementaciji ter kako izbira različnih omejitev in njihovih uteži vpliva na končne rešitve.

Home care scheduling Abstract

Home care is provided by retirement homes. One of the major causes of stress for coordinators is the planning and scheduling of the caregivers’ working hours.

The schedules are in most cases made “by hand” and copied from week to week with minor corrections. The problem of creating a schedule for home care is like the vehicle routing problem with time windows, to which we add some additional restrictions. In the thesis, we present the creation of a schedule with the help of a constraint problem-solving tool — OptaPlanner. We describe the specifics of the tool, input data preparation, main challenges with the implementation, and how the choice of different constraints and their weights affect the final solutions.

Math. Subj. Class. (2010): oznake kot 74B05, 65N99, so na voljo na naslovu http://www.ams.org/msc/msc2010.html

Ključne besede: pomoč na domu, problem z omejitvami, razvrščanje, OptaPlan- ner

Keywords: home care, constraint satisfaction problem, scheduling, OptaPlanner

1 Uvod

Prve modele za optimizacijo urnika pomoči na domu so začeli razvijati Begur in soavtorji [3]. Oblikovali so sistem za pomoč pri odločanju za zdravstveno podjetje, da bi optimizirali poti in razvrščanje zaposlenih, ob tem pa niso upoštevali časovnih oken za izvedbo opravil pri oskrbovancih.

V splošnem na rast potrebe po pomoči na domu vpliva staranje prebivalstva, število invalidov, naraščajoči stroški zdravstvenega varstva ter prostorski problemi v bolnišnicah in domovih za starejše občane [2]. Oskrbovanci imajo raznorazne zahteve glede pomoči, ki jo mora oskrbovalec pri njih opraviti. Tu gre za stvari kot so oblačenje, umivanje, pomoč pri jemanju zdravil, dostava kosila, gospodinjska dela, spremljanje pri nujnih obveznostih in tako naprej. Pri pomoči na domu gre torej za enostavnejša opravila, ki jih oskrbovalec opravi pri pacientu doma v sproščenem okolju [2]. Zaradi naraščajočega števila oskrbovancev in oskrbovalcev je organizacija urnikov vedno težji kombinatorični problem, saj je kombinacij vedno več. Če se za zdaj koordinatorji v slovenskih domovih za starejše občane še lahko znajdejo z načrtovanjem urnika “na roke”, se bo to v prihodnosti najbrž spremenilo. Naša želja je, da izdelavo urnika koordinatorju zaposlenih v domu starejših občanov čim bolj poenostavimo ter optimiziramo, saj to prispeva k manjšim stroškom ter večjemu zadovoljstvu.

Pri izdelavi urnika za pomoč na domu oskrbovalcem dodeljujemo opravila, ki jih je treba opraviti pri različnih oskrbovancih z različnimi željami in potrebami na različnih lokacijah. Način, kako rešitev, pridobljeno z računalniškim programom, usmerjamo v želeno smer, je s pomočjo omejitev. Omejitve zapišemo na način, da rešitev usmerjajo k čim manjšim stroškom ter čim večjemu zadovoljstvu tako zaposlenih kot strank. Načrtovanje urnika pomoči na domu se sooča z zahtevnimi optimizacijskimi izzivi na različnih ravneh odločanja. Gre za razporejanje delovnega časa zaposlenih, dodeljevanje opravil in načrtovanje voženj, kako bodo zaposleni obiskovali stranke [14].

1.1 Terminologija

V magistrskem delu se nekateri izrazi pojavljajo večkrat. Spodaj so našteti in ob- razloženi:

• Dom starejših občanov oziroma krajše DSOje ustanova, ki izvaja pomoč na domu. Včasih ga poimenujemo tudi izhodišče, podjetje ali prevzemna točka.

• Pomoč na domu oziroma krajšePND je pomoč, ki jo zaposleni doma sta- rejših občanov opravi pri stranki.

• Zaposlenije oskrbovalec, ki v okviru doma starejših občanov opravlja pomoč na domu. V programu za reševanje optimizacijskega problema jih v angleščini imenujemousers. Označevali jih bomo z oznakami U1, . . . , UK.

• Stranka oziroma oskrbovanec je oseba, ki ima z domom starejših občanov dogovor za pomoč na domu. Stranka živi na določeni lokaciji in ima sklenjen

dogovor, kdaj bo pomoč na domu potekala. V programu za reševanje optimi- zacijskega problema jih v angleščini imenujemo clients. Označevali jih bomo z oznakami C₁, . . . , C_M.

• Opravilaso vnaprej dogovorjeni obiski zaposlenega na domu stranke v okviru pomoči na domu ali pa opravila, ki so vezana neposredno na zaposlenega, na primer njegova malica. Imajo določen čas trajanja in jih je treba začeti izvajati znotraj vnaprej začrtanega časovnega okna. V programu za reševanje optimizacijskega problema jih v angleščini imenujemo tasks. Označevali jih bomo z oznakami T₁, . . . , T_N.

• Lokacije so različne za posamezne stranke (kje potekajo opravila), zaposlene (kje se začne in konča njihov delovnik) in DSO. V programu za reševanje optimizacijskega problema jih v angleščini imenujemo locations. Označevali jih bomo z oznakami L₁, . . . , L_α (vsaka stranka in vsak zaposleni ima svojo lokacijo, imamo pa še druge).

• Časovno oknoje časovni interval za izvedbo opravila, ki je določen z začetnim (from) in končnim (to) časom.

• Omejitev je pogoj, ki ga postavimo pri iskanju rešitve problema. Lahko gre za omejitev, kdaj mora zaposleni priti k stranki, omejitve glede na tip opravila, dolžino delovnika, omejitev prepogostega menjavanja zaposlenih in druge. V programu za reševanje jih v angleščini imenujemo constraints. Označevali jih bomo z oznakami X₁, . . . , X_β.

• Problem razvoza oziromavehicle routing problem (VRP) je tip optimizacij- skega problema, ki ga bomo večkrat omenjali.

1.2 Organizacija dela

V pričujočem delu je predstavljena izdelava urnika pomoči na domu. V poglavju 2 je zapisano matematično ozadje problema, ki ga bomo reševali. Poglavje 3 opisuje izbiro orodja, ki ga za izdelavo urnika uporabljamo in njegove lastnosti. Vhodni podatki, njihova organizacija in struktura programa so predstavljeni v poglavju 4.

Težave pri implementaciji, vmesni rezultati, analiza različnih pridobljenih rešitev in načini uporabe programa se nahajajo v poglavju 5. V poglavju 6 povzamemo zaključke in iztočnice za nadaljnje delo.

Kar nekaj slik, ki se v delu pojavljajo, so del OptaPlannerjeve dokumentacije.

Veseli nas, da smo dobili izvorne datoteke, primerne za obdelavo in prevod angleških napisov, ter dovoljenje za njihovo uporabo.

2 Optimizacijski problem

Problem razvoza s časovnimi okni (vehicle routing problem with time windows — VRPTW) je problem, kjer moramo znotraj vnaprej določenih časovnih oken zado- stiti naboru strank, s tem, da imamo na voljo določeno število vozil [4]. Izdelava urnika za pomoč na domu je nadgradnja tega problema, ki vsebuje par dodatnih omejitev in zahtev, kar ga naredi še nekoliko kompleksnejšega od VRPTW [4]. Če te dodatne omejitve zanemarimo in rečemo, da ne upoštevamo časa za malico zapo- slenega, da vsi zaposleni začnejo delo na lokaciji doma starejših občanov (DSO) in da razporejamo le opravila, pri katerih ni potrebno najprej v DSO in nato k stranki, potem lahko problem predstavimo v obliki grafa. Naj G = (V, E) predstavlja ne- usmerjen graf, kjer V= {v₀, . . . , v_n, v_n+1} množica vozlišč in E množica povezav.

Množica vozlišč V_t ={v₁, . . . , v_n} sovpada z množico vseh opravil, ki jih je treba opraviti pri različnih strankah, medtem ko vozlišči v₀ in v_n+1 predstavljata dom starejših občanov. Cilj optimizacije je, da obiščemo vsa vozlišča v grafu (opravimo vsa opravila) znotraj vnaprej določenih časovnih oken, s čim nižjimi stroški (kar v našem primeru predstavlja število minut na cesti), ne da bi ob tem kršili dodatne omejitve glede delovnih časov zaposlenih. Ta problem je NP-težak, kar pomeni, da število možnih rešitev z naraščanjem problema postaja ogromno in neobvladljivo.

Preiskovanje vseh bi bilo nesmiselno, zato se reševanja navadno lotimo s pomočjo različnih hevristik [17].

Recimo, da imamo torej N opravil in K zaposlenih. Povezava v grafu naj pred- stavlja povezavo in smer vožnje med dvema lokacijama na zemljevidu (pri neusmer- jenem grafu si lahko predstavljamo, da imamo usmerjeno povezavo med paroma vozlišč v obeh smereh). Čas trajanja vožnje med vozliščema v_i inv_j bomo označili s c_ij (če je i = j, potem je c_ij = 0). Vsaka pot v grafu se začne v vozlišču z oznako v0, konča v vozlišču vn+1 (DSO) in vsak zaposleni opravi natanko eno pot, zato je število poti enako številu zaposlenih.

Vsako vozlišče v grafu, razen v₀ in v_n+1, je lahko obiskano največ enkrat z enim od zaposlenih in ima za obisk opredeljeno časovno okno, ki ga predstavljata para- metra, kdaj se obisk najprej lahko začne in pred katerim časom mora biti zaposleni zagotovo pri stranki. Če zaposleni pride pred časom za začetek na strankino lokacijo, potem mora čakati na mestu. Vsak obisk ima določeno dolžino trajanja in vsak za- posleni ima predviden čas na poti (dolžina delovnika). Cilj je ustvariti tako družino poti, ki zadosti vsem omejitvam in obenem minimizira stroške — kar je v našem primeru čas na poti. Če si vozlišča predstavljamo kot lokacije na zemljevidu, po- tem pot predstavlja zaporedno obiskovanje posameznih vozlišč. Matematično lahko formuliramo problem na naslednji način [16].

Parametri problema so:

• K . . . število vseh zaposlenih,

• N . . . število vseh opravil (vozlišč v grafu, če izvzamemo izhodišče),

• c_ij . . . čas potovanja od stranke i do stranke j,

• e_i . . . najbolj zgoden dopusten čas prihoda k stranki i,

• ℓ_i . . . najbolj pozen dopusten čas prihoda k stranki i,

• d_i . . . čas trajanja opravila pri stranki i,

• r_k . . . dolžina delovnika zaposlenegak. Osnovne spremenljivke:

• x_ijk (i, j ∈ {0, 1, 2, . . . , N}; k ∈ {1, 2, . . . , K}; i ̸= j) je indikatorska spremenljivka z vrednostjo 1, če zaposleni k potuje od stranke i do stranke j, in 0 v ostalih primerih;

• spremenljivkaP_i predstavlja čas prihoda zaposlenega k stranki i;

• spremenljivkawi predstavlja čas čakanja pri strankii, če zaposleni pride pred e_i .

Minimizirati želimo

N

∑︂

i=0 N

∑︂

j=0 K

∑︂

i̸=j,k=1

c_ijx_ijk. (2.0)

Če formulo (2.0) gledamo po delnih vsotah, vidimo, da nam predstavlja čas potova- nja vseh zaposlenih. Zunanji dve vsoti potujeta čez vse možne pare vozlišč v grafu, notranja pa po vseh zaposlenih. V primeru, da zaposleni z oznako k zaporedno obišče vozlišči v_i in v_j, je spremenljivka x_ijk enaka 1, če pa ne, potem je x_ijk = 0. Ta indikatorska vrednost se pomnoži s časom vožnje med vozliščemav_i inv_j. Vsota

N

∑︂

i=0 N

∑︂

j=0

c_ijx_ijk

nam pri izbranem zaposlenem tako predstavlja čas, ki ga porabi na poti (če izvza- memo postanke). Celoten izraz (2.0) z vsemi tremi vsotami je seštevek časov poti vseh zaposlenih. Pot posameznega zaposlenega predstavlja pot v grafu, ki se začne in konča v domu starejših občanov (vozlišče v0 je začetek, vn+1 pa konec). Na poti imamo le povezave, kjer ima indikatorska spremenljivka vrednost 1 — zaradi spo- daj zapisanih omejitev, se v nobenem vmesnem vozlišču posamezne poti ne more zgoditi, da bi iz njega izhajali dve povezavi, ki bi imeli indikatorsko spremenljivko z vrednostjo 1.

Pri tem upoštevamo naslednje omejitve:

• Največje število poti je manjše ali enako številu vseh zaposlenih. To pomeni, da je število povezav iz izhodišča, ki imajo vrednost indikatorske spremenljivke 1, največ K:

K

∑︂

k=1 N

∑︂

j=1

xijk ≤K, zai= 0. (2.1)

• Za vsakega zaposlenega je natančno ena povezava, ki gre iz izhodišča in v izhodišče, kar predstavlja zagotovilo, da se pot zaposlenega začne in zaključi v DSO:

N

∑︂x_ijk= 1, zai= 0 in k∈ {1, . . . , K}. (2.2)

N

∑︂

j=1

x_jik = 1, zai=n+ 1 ink ∈ {1, . . . , K}. (2.3)

• Vsako vozlišče (razen izhodišča) ima natanko eno povezavo z vrednostjo indi- katorske spremenljivke 1, ki izhaja iz tega vozlišča, in eno, ki gre vanj:

K

∑︂

k=1 N

∑︂

j=0,j̸=i

x_ijk = 1, zai∈ {1, . . . , N}. (2.4)

K

∑︂

k=1 N

∑︂

i=0,i̸=j

x_ijk = 1, zai∈ {1, . . . , N}. (2.5)

• Celoten čas potovanja zaposlenega je krajši ali enako dolg kot njegov delovnik:

N

∑︂

i=0 N

∑︂

j=0,j̸=i

xijk(cij +di+wi)≤ru, za k∈ {1, . . . , K}. (2.6)

• Zaposlenim v izhodišču ni potrebno čakati, preden se odpravijo na pot:

w₀ =d₀ = 0. (2.7)

• Če jex_ij = 1, potem je čas prihoda v vozliščev_j kasnejši, kot če bi času prihoda v vozlišče v_i prišteli seštevek časov čakanja na začetek opravila v vozlišču v_i, dolžino trajanja opravila v vozliščuv_i in časa trajanja poti med vozliščema:

K

∑︂

k=1 N

∑︂

i=0,i̸=j

xijk(Pi+wi+di+cij)≤Pj, za j ∈ {1, . . . , N}. (2.8)

• Čas, ko zaposleni začne izvajanje opravila (čas prihoda plus čakanje), mora biti znotraj časovnega okna:

e_i ≤(P_i+w_i)≤ℓ_i za i∈ {1, . . . , N}. (2.9) Omejitve lahko razdelimo na različne nivoje, ki jih je lahko poljubno veliko. Naj- višji nivo predstavljajo take, ki jih nikakor ne smemo kršiti in jim pravimo krepke omejitve. Rešitve, ki jih dobimo pri reševanju optimizacijskega problema, so lahko sledeče [9]:

• Možna rešitev (possible solution) je vsaka rešitev ne glede na to, ali krši katerokoli omejitev ali ne. VRPTW ima ogromno število možnih rešitev, med katerimi so mnoge povsem brez smisla. Primer take bi bil, da če imamo 10 zaposlenih in 100 opravil, da bi vse dodelili enemu zaposlenemu.

• Dopustna rešitev (feasible solution) je rešitev, ki ne krši nobenih krepkih omejitev. V primeru zgoraj bi to pomenilo, da smo našli rešitev, kjer so upoštevane vse omejitve od (2.1) do (2.9). Lahko se zgodi, da dopustna rešitev ne obstaja. Vsaka dopustna rešitev je element množice možnih rešitev.

• Optimalna rešitev (optimal solution) je rešitev, kjer je vrednost kriterijske funkcije najbolj ugodna (v našem primeru rešitev z najkrajšimi potovalnimi časi). Problem je kombinatoričen in ima končno mnogo rešitev, med katerimi vedno obstaja vsaj ena optimalna, tudi če ta ni znotraj množice dopustnih rešitev.

• Najboljša rešitev (best solution) je rešitev, kjer je vrednost kriterijske funk- cije med vsemi najdenimi rešitvami najbolj ugodna. Ker je preiskovalni pro- blem zelo velik ne moremo vedeti, ali je najboljša rešitev tudi optimalna (če bi znali najti optimalno rešitev, potem bi bila le ta tudi najboljša).

V našem primeru izdelave urnika za pomoč na domu le tega izdelujemo za posamezni dan, nato pa iz posameznih dnevnih urnikov sestavimo tedensko celoto. Na tak način lahko posamezni dan obdelamo dokaj neodvisno od drugih, kar omogoča, da morebitni nepredvidljivi dnevni popravki ne vplivajo na urnik celega tedna, ampak le na posamezni dan. Kakšne dodatne omejitve bi potrebovali, da bi se tedenski urnik sestavil v čim lepšo celoto, za zdaj ni bil glavni poudarek tega dela. Ukvarjali smo se predvsem s sestavljanjem dnevnega urnika, povezovanje v tedensko ali celo mesečno celoto na pameten način pa vidimo kot priložnost za nadaljnje delo na tem področju.

Pri sestavljanju urnika za daljše časovno obdobje bo zelo pomembno to, da že pri oblikovanju vhodnih podatkov pazimo na določene omejitve, pravilnike in zakone, ki jih moramo upoštevati. Če bi bili na primer vhodni podatki pripravljeni tako, da določen zaposleni dela vse vikende v mesecu, potem bi moral koordinator dobiti obvestilo, da nekaj ni v redu in da bo, če nadaljuje tako načrtovanje, kršen zakon o delovnih razmerjih. Prav tako bi določenega zaposlenega, ki ima predviden dopust, izpustili pri načrtovanju urnika za določene dni. Poleg skrbno pripravljenih vhodnih podatkov bi bilo treba zagotoviti sinhronizacijo med posameznimi dnevi in da bi se podobna opravila zgodila v podobnem času. Če je recimo stranka dogovorjena za opravilo vsak dan enkrat med 7.00 in 10.00, potem bi bilo smiselno, da je ta ura vsak dan v tednu podobna, kar bi lahko spodbujali z omejitvijo, ki bi kaznovala morebitne časovne razlike v uri začetka med posameznimi dnevi.

3 Izbira orodja

Odločili smo se, da se reševanja problema z omejitvami ne bomo lotili s točke nič, ampak bomo za pomoč uporabili enega izmed odprtokodnih programov oziroma pro- gramskih orodij, ki obstajajo na trgu. V nasprotnem primeru bi bil časovni vložek v razvoj reševalnika prevelik, kakovost dobljenega rezultata v primerjavi z orodjem, ki je v razvoju več let, pa verjetno slabša. Naša naloga je bila izbrati orodje, ga spoznati, ugotoviti na kakšen način je treba predstaviti podatke, da jih program sprejme, določiti omejitve in njihove uteži ter vizualno predstaviti dobljen rezultat.

Da smo lahko izbrali program, ki nam najbolj odgovarja, smo pregledali več pro- gramskih rešitev.

Merila za izbiro orodja so bila naslednja:

1. Zna reševati veliko problemov.

2. Je sodoben in se posodablja.

3. Ima aktivno skupnost.

4. Je dobro dokumentiran.

Ocene meril so predstavljene v tabeli 3.1, kjer je zbranih deset odprtokodnih orodij za pomoč pri reševanju problemov kombinatorične optimizacije¹. Vsi izmed zbranih orodij naj bi zadostili merilu številka 1. Da je orodje sodobno in se posodablja, smo ponazorili s stolpcem “zadnja posodobitev”, aktivno skupnost pa s pomočjo stolpcev “Github”, ki prikazuje, koliko ljudi je všečkalo projekt na platformi Github [12], in “Stack overflow”, ki prikazuje koliko vprašanj se na določeno temo pojavlja na platformi Stack overflow [19].

ime Github ⋆ Stack overflow jezik zadnja posodobitev

OptaPlanner 2151 2428 Java 2021

Choco Solver 521 154 Java 2021

Cassowary 460 40 Swift 2017

Holmes 274 10 ² Haskell 2020

Cassowary Rs 251 0 Rust 2020

Jfs 215 4 C++ 2019

Kiwi.js 207 5 Javascript 2020

Geocode 178 10 ² C++ 2021

Optaweb ER 116 12 Java 2021

Kvconstraintkit 91 0 Swift 2019

Tabela 3.1: Primerjave odprtokodnih orodij za reševanje problemov z omejitvami.

OptaPlanner, se je zdel na podlagi pregledanih sorodnih orodij najbolj primeren.

Poleg številk v tabeli 3.1 ponuja več kot 350 strani dolgo dokumentacijo [9], grafične

1Podatki so bili zabeleženi 7. 4. 2021 in tako ne prikazujejo natančnih številk med odločanjem, kljub temu pa je vrstni red zelo podoben kot takrat.

2Zaradi imena je bilo težje razpoznati, katera vprašanja so bila v povezavi z dotičnim orodjem.

prikaze in dostopno kodo za različne primere uporabe, izobraževalne posnetke na platformi YouTube [18] ter kar nekaj člankov, ki pomagajo ali začeti delo ali pa se naučiti katerih bolj naprednih tehnik [10]. OptaPlanner se je zdel v primerjavi z ostalimi pregledanimi programi nekaj korakov spredaj, zato se v še bolj podrobno analiziranje ostalih programskih rešitev nismo spuščali. Je tudi najbolj prijazen uporabniku, zato smo se odločili, da pot programiranja urnikov pomoči na domu nadaljujemo z uporabo OptaPlannerja.

3.1 OptaPlanner

OptaPlanner je orodje, ki s pomočjo vgrajenih naprednih algoritmov rešuje probleme z omejitvami [9]. V dokumentaciji predstavi paleto primerov uporabe pri problemih, kot so problem razvoza, organizacija vzdrževalnih del, dodeljevanje nalog, izdelava šolskega urnika, pakiranje zabojnikov, razporejanje sestankov in še veliko več. Poleg programskega jezika Java omogoča programiranje tudi z drugimi jeziki JVM, kot sta na primer Kotlin in Scala. Njegova prednost je, da omejitev ni treba vnašati kot matematične enačbe, ampak jih lahko zapišemo v človeku bolj domačemu jeziku, ki jih potem program sam pretvori v notranje predstavljivo obliko. Znotraj orodja imamo implementirane različne optimizacijske pristope, kot so tabu iskanje(tabu search),simulirano ohlajanje (simulated annealing),iskanje z vzpenjanjem (hill climbing) in druge metahevristike, ki skušajo učinkovito priti do dobrega rezul- tata. V spodnjih razdelkih bomo predstavili nekatere posebnosti, ki jih OptaPlanner omogoča in ki bodo osnova za razumevanje poglavja z rezultati.

3.1.1 Računanje vrednosti rezultata

Vsaka rešitev, ki jo s pomočjo programa dobimo, ima določeno vrednost kriterijske funkcije oziroma oceno (score). Ta nam služi, da lahko posamezne rešitve med seboj primerjamo — višja kot je ocena, boljša je rešitev. Na vrednost kriterijske funkcije vplivajo omejitve, ki morajo biti dobro opredeljene, saj je le v tem primeru rešitev z najboljšo oceno, najboljša tudi v praksi. Poleg tega moramo paziti na hitrost izračunavanja ocene, saj se ovrednotenje sprotnih rezultatov dogaja ves čas

— tudi po več tisočkrat na sekundo (odvisno od implementacije računanja ocene in od narave problema). OptaPlanner nam omogoča, da lahko oceno posamezne rešitve računamo na različne načine:

• Enostavno Java računanje ocene (easy Java score calculation) je način računanja ocene, ki je enostaven za implementacijo, vendar ima to pomanj- kljivost, da mora vsakič znova čez vse parametre programa in jih oceniti, kar pomeni, da ne glede na velikost spremembe vmesnega rezultata, vsakič znova preračuna oceno od začetka. V primeru, da je naš optimizacijski problem maj- hen in nam za hitrost računanja rešitve ni mar, potem je ta način računanja ocene primeren, drugače pa ne.

• Računanje ocene s pomočjo omejitvenih tokov(constraint streams score calculation) je način računanja ocene, ki ga OptaPlanner najbolj priporoča.

Gre za način, kjer vsako omejitev zapišemo kot ločen omejitveni tok (constra- int stream). Ta način je enostaven za implementacijo, hiter pri računanju in

skalabilen. Omogoča inkrementalno računanje ocene, kar pomeni, da pri spre- membi vmesnega rezultata obravnava le del, ki se je spremenil, in ustrezno popravi oceno. Ta način je naša izbira za računanje.

• Inkrementalno Java računanje ocene (Incremental Java score calcula- tion) tako kot prejšnji način tudi omogoča inkrementalno računanje vmesnih rezultatov, vendar s to razliko, da je ta način težje implementirati in vzdrževati pri različnih spremembah, zato ga OptaPlanner za uporabo ne priporoča.

• Računanje ocene s pomočjo orodja Drools (Drools score calculation) je način, kjer vsako omejitev napišemo kot pravilo v jeziku DRL (Drools rule language). Način je skalabilen, a se je treba naučiti pisanja pravil v jeziku, ki ga predvideva.

3.1.2 Omejitve

Pri reševanju optimizacijskega problema želimo z našo rešitvijo zadostiti različnim omejitvam. Znotraj OptaPlannerja so omejitve lahko precej prilagodljive in jim lahko določamo naslednje lastnosti:

Nivo omejitve

Kdaj se zgodi, da je kršenje ene omejitve neprimerljivo slabše kot kršenje druge.

V tem primeru razdelimo omejitve na več nivojev. OptaPlanner nam omogoča poljubno število nivojev, vendar se v praksi izkaže, da se veliko število nivojev ne obnese najboljše [9]. Pri več nivojih se je treba zavedati, da če imamo recimo dva nivoja — krepke in šibke omejitve, potem bo rešitev, ki nima kršene nobene krepke omejitve boljša od rešitve, ki ima kršeno vsaj eno krepko omejitev, pa četudi ima prva rešitev kršenih 10000 šibkih omejitev. Na sliki 3.1 vidimo rešitve z dvema omejitvama na različnih nivojih in v kakšnem razmerju so med seboj.

Velikokrat nam krepke omejitve predstavljajo primere, ki fizično niso mogoči — da je na primer en oskrbovalec istočasno na dveh različnih lokacijah in izvaja oskrbo.

Marsikdaj se da s pametnim načrtovanjem opredelitve problema take situacije pre- prečiti z izbiro spremenljivk in parametrov programa — takim omejitvam rečemo modelske omejitve. Če na primer želimo, da opravilo opravi največ en zaposleni, potem je tip spremenljivke, ki označuje za podatek, zapisan kot ”zaposleni“ in ne kot ”seznam zaposlenih“.

Predznak omejitve

Omejitve so lahko negativne ali pozitivne. V primeru pozitivne omejitve govorimo o nagradi (reward), v primeru negativne pa o kazni (penalty). Pozitivne omejitve želimo maksimizirati, negativne pa minimizirati. Na sliki 3.2 vidimo, kako v pra- ksi delujejo kazni in nagrade. Za vsako jabolko rečemo, da k vrednosti kriterijske funkcije prispeva eno točko, vsaka porabljena enota bencina pa eno točko odšteje.

V tem primeru je nivo obeh omejitev enak, zato lahko kazni in nagrade seštejemo skupaj ter dobimo končno oceno.

V praksi se večinoma uporabljajo negativne omejitve, kar pomeni, da je najboljša rešitev taka, ki ima oceno 0, se pravi, da nobena omejitev ni bila prekršena.

Slika 3.1: Najprej minimiziramo prekomerno naložene tovornjake, potem minimizi- ramo porabo bencina [9].

Uteži omejitev

Niso vse omejitve enako pomembne. Če je kršitev ene omejitve x-krat slabša kot kršitev druge, morata imeti ti dve omejitvi različni uteži (čeprav sta na enakem nivoju). Na sliki 3.3 lahko vidimo, da nam en nezadovoljen delavec predstavlja −2 točki, ena porabljena enota bencina pa −1 točko. Vidimo lahko, kakšne so ocene rešitve in v kakšnem medsebojnem razmerju so med seboj.

Kako določiti uteži omejitev tako, da je rezultat čim bolj podoben takemu, kot ga uporabnik želi, zahteva nekaj ekspertnega znanja. Ni pa to zagotovilo za uspeh.

Včasih je bolje, da se kot programerji ne ukvarjamo preveč s točnimi utežmi vsake omejitve, temveč implementiramo program na način, da lahko uporabnik sam na- stavlja uteži in primerja dobljene rezultate. V primeru domov za starejše občane se vsak dom nekoliko razlikuje pri svojih željah, zato je to še toliko bolj pomembno.

3.1.3 Spremenljivke

Način, kako OptaPlannerju povemo, katere stvari bomo načrtovali in katere bodo ostale nespremenjene med načrtovanjem, je s pomočjo zastavic (annotations). Na sliki 3.4 imamo prikazano shemo za načrtovanje šolskega urnika. Objekti tipa Ti- meSlot inRoom se tekom načrtovanja ne spreminjajo. TimeSlot (časovna reža) ima atribute dayOfWeek (dan v tednu), startTime (začetek časovne reže) in endTime

Slika 3.2: Iskana rešitev maksimizira število jabolk in minimizira porabo bencina [9].

(konec časovne reže) ves čas enake. Prav tako velja za atributname (ime) objekta Room. V programu sta ta dva objekta označena z zastavico@PlanningFact. Objekti tipa Lesson (učna ura) imajo nekatere atribute, ki se tekom načrtovanja ne spre- minjajo: subject (predmet), teacher (učitelj) in studentGroup (skupina učencev).

Obenem pa tudi dve spremenljivki, ki ju želimo med načrtovanjem določiti. Vsaki učni uri želimo prirediti kdaj bo potekala (timeslot) in kje bo potekala (room). Ti dve spremenljivki tekom programiranja OptaPlanner vseskozi spreminja in išče re- šitev z najboljšo oceno. Označimo ju z zastavico @PlanningVariable. Vsak objekt, ki ima znotraj kakšno spremenljivko označeno s @PlanningVariable, je označen z zastavico @PlanningEntity.

Poleg spremenljivk, ki so označene s @PlanningVariable, ima OptaPlanner še posebno vrsto spremenljivk, ki jim pravimo senčne spremenljivke (shadow variables).

Način, kdaj in zakaj jih uporabiti lahko ponazorimo s primerom iz našega programa za izdelavo urnika pomoči na domu.

V našem primeru imamo zaposlene (oskrbovalci), ki jim dodeljujemo opravila pri strankah (oskrbovanci). Obiskovanje strank je v programu zabeleženo v obliki verige, kjer so stranke razporejene v časovnem vrstnem redu. Če bi želeli točno izračunati prihod k vsaki stranki, bi lahko začeli na začetku (začetna lokacija zaposlenega) in preračunavali čase trajanja posameznih opravil in časov voženj. Na ta način bi bilo računanje na vsakem koraku zelo zamudno, zato uvedemo senčno spremenljivko za čas prihoda k posamezni stranki (arrivalTime). V primeru, da se veriga strank spremeni, se časi prihodov ustrezno popravijo, kot je vidno na sliki 3.5.

Slika 3.3: Minimiziramo nezadovoljstvo zaposlenih in porabo bencina. Teža omejitev je različna [9].

3.1.4 Primerjalna analiza

OptaPlanner podpira več algoritmov za optimizacijo, zato se je logično vprašati, kateri od njih se bo najbolje obnesel za naš tip problema. Tip problema je pri opti- mizaciji ključnega pomena, saj izrek o brezplačnem kosilu (no free lunch theorem) pravi, da če bi povprečili rezultate dobljene na vseh možnih problemih, potem bi se katerikoli optimizacijski algoritem (tudi povsem naključno iskanje) izkazal enako dobro [20].

OptaPlanner nam omogoča, da v svoj program implementiramo orodje za pri- merjanje in analiziranje različnih algoritmov in njihovih nastavitev. Orodje nam ponuja vizualne prikaze in nam pomaga pri tem, da lahko najdemo najboljšo kon- figuracijo za naš problem reševanja. Oris, kako primerjalnik (benchmarker) deluje, si lahko ogledamo na sliki 3.6. Po tem, ko gre program skozi vse možne kombina- cije vhodnih podatkov in optimizacijskih algoritmov, nam izdela poročilo v obliki HTML dokumenta, ki ga lahko odpremo v spletnem brskalniku. Znotraj poročila je razvidno, kateri izmed algoritmov je dal pri opredeljenih vhodnih podatkih najboljše rezultate in ga OptaPlanner predlaga za nadaljnjo uporabo.

Slika 3.4: Diagram za problem izdelave šolskega urnika [9].

Slika 3.5: Ko v verigi strank pride do spremembe, se časi senčne spremenljivke ustrezno popravijo [9].

Slika 3.6: Oris delovanja orodja za analizo in primerjanje.

4 Predstavitev podatkov

Podatki, s katerimi delamo, predstavljajo dogovorjen urnik za en teden³ v februarju za enega izmed slovenskih domov za starejše občane. Gre za srednje velik dom, ki ima 29 zaposlenih, ki se ukvarjajo z oskrbo na domu, ter 168 strank. V tabeli 4.1 je prikazano, koliko oskrbovalcev dela na posamezni dan v tednu. Ta teden ne vsebuje nobenega praznika, je pa število zaposlenih, ki delajo na praznik, podobno številu zaposlenih, ki delajo ob nedeljah.

ponedeljek torek sreda četrtek petek sobota nedelja

22 23 22 22 23 10 8

Tabela 4.1: Število izvajalcev pomoči na domu na posamezni dan v tednu.

V dotičnem tednu je bilo dogovorjenih 920 opravil. V tabeli 4.2 je prikazano število opravil na posamezni dan v tednu. Pri primerjavi teh številk se je treba zavedati, da niso vsa opravila enako dolga.

ponedeljek torek sreda četrtek petek sobota nedelja

157 154 160 156 160 70 63

Tabela 4.2: Število dogovorjenih pomoči na domu na posamezni dan v tednu.

4.1 Vhodni podatki

Podatke o dogovorjenem urniku dobimo v obliki datoteke JSON. JSON je standardi- zirana oblika zapisa, ki uporablja človeku berljivo besedilo za shranjevanje in prenos podatkovnih objektov, sestavljenih iz parov atribut-vrednost [5]. Za zdaj vhod v program predstavljajo podatki za posamezni dan v tednu, zato je treba prvotne po- datke nekoliko prilagoditi. Vhodni podatki so naslednji:

Zaposleni:

• ID— unikatna identifikacijska številka. Uporablja se za identifikacijo zaposle- nega pri strankinih parametrih za preteklega zaposlenega, ki je izvršil določeno opravilo (last_user), ter za zaželene in nezaželene zaposlene (default_users, rejected_users).

• Začetnice (initials) — niz znakov, ki predstavlja začetnice imena in priimka zaposlenega. Podatek služi za lažjo berljivost vmesnih rezultatov in preverja- nje dobljenega rezultata z realnim stanjem.

• Koordinate (coordinates) — parameter je sestavljen iz dveh podatkov, ki predstavljata zemljepisno širino (lat) in zemljepisno dolžino (lng). Služi za računanje razdalj med posameznimi lokacijami, med katerimi zaposleni potu- jejo.

3Gre za teden od 15. do 21. februarja 2021.

• Dolžina delovnika (daily_working_minutes) — v minutah podana dolžina delovnega časa posameznega zaposlenega.

• Delovni dnevi (weekly_workdays) — seznam dnevov v tednu, ko določeni zaposleni dela.

• Začetek dela (start_time) — kdaj posameznik začne delo oziroma od kdaj naprej mu lahko dodeljujemo opravila.

Vhodni podatki za enega zaposlenega v obliki JSON so prikazani v izseku 4.1.

{

" ID ": 1 8,

" i n i t i a l s ": " BoBr ",

" c o o r d i n a t e s ": {

" lat ": 4 6.1 1 1 1 1 1,

" lng ": 1 6.2 2 2 2 2 2 },

" d a i l y _ w o r k i n g _ m i n u t e s ": 4 0 0,

" w e e k l y _ w o r k d a y s ": [1,2,4,7],

" s t a r t _ t i m e ": "6:3 0"

}

Izsek programa 4.1: Primer objekta JSON, ki predstavlja podatke zaposlenega in je del vhodnih podatkov v program za izdelavo urnika pomoči na domu.

Stranka:

• EŠD — enolična evidenčna številka stranke.

• Koordinate (coordinates) — parameter je sestavljen iz dveh podatkov, ki predstavljata geografsko širino (lat) in geografsko dolžino (lng). Služi za raču- nanje razdalj med posameznimi lokacijami, med katerimi zaposleni potujejo.

• Zaželeni zaposleni (default_users) — seznam ID-jev zaposlenih, za katere stranka želi, da pri njej izvedejo opravilo.

• Nezaželeni zaposleni (rejected_users) — seznam ID-jev zaposlenih, za ka- tere stranka ne želi, da pri njej izvedejo opravilo.

• Dogovorjen urnik (schedule) — seznam opravil, za katere je stranka dogo- vorjena z DSO. Vsako opravilo vsebuje naslednje podatke:

– Od(from) indo(to) — označujeta meje časovnega okna, v katerem mora zaposleni priti do stranke.

– Dan v tednu(weekday) — dogovorjen dan opravila.

– Čas trajanja (duration) — čas trajanja opravila.

– Prejšnji zaposleni(last_user) — ID zaposlenega, ki je nazadnje opra- vljal to opravilo. Služi temu, da lahko omejitve postavimo tako, da usmer- jamo končen rezultat k čim manj menjavam zaposlenih pri opravilih.

– Tip opravila (visit_type) — opravila so lahko različnih tipov:

∗ Oskrba — pomoč pri temeljnih opravilih, gospodinjska pomoč, po- moč pri vzdrževanju stikov, . . .

∗ Kosilo — dostava kosila stranki.

∗ Kosilo in oskrba — opravilo, ki združuje dostavo kosila in oskrbo.

∗ Malica — poseben tip opravila, ki ni vezan na stranko, temveč na zaposlenega, in sicer označuje njegov čas za malico. Kje bo opravek opravljen, ni vezano na nobeno lokacijo.

{

" esd ": 4 2,

" c o o r d i n a t e s ": {

" lat ": 4 6.4 2 4 2 4 2,

" lng ": 1 6.6 9 6 9 6 9 },

" s c h e d u l e ": [ {

" from ": "7:0 0",

" to ": "9:0 0",

" w e e k d a y ": 7,

" d u r a t i o n ": 3 0,

" l a s t _ u s e r ": 3 1,

" v i s i t _ t y p e ": " O S K R B A "

} ],

" d e f a u l t _ u s e r s ": [2 4,4 1,5 2,3 1],

" r e j e c t e d _ u s e r s ": [ ] }

Izsek programa 4.2: Primer objekta JSON, ki predstavlja podatke stranke in je del vhodnih podatkov v program za izdelavo urnika pomoči na domu.

Medsebojne razdalje

Med izvajanjem programa za izdelavo urnika za pomoč na domu je stalna potreba po podatkih o medsebojnih razdaljah posameznih lokacij. Če bi te podatke izraču- navali med izdelavo urnika, bi se čas izvajanja programa zelo podaljšal, zato si jih pripravimo vnaprej. Načinov, kako pridobiti te podatke je več. Mi smo se odločili, da bomo uporabili podatke o razdaljah, ki nam jih ponuja Google. Njihov vmesnik (API) nam omogoča, da pridobimo medsebojno razdaljo med lokacijama, ki ju po- šljemo v zahtevku (request). V našem primeru je bilo treba dobiti informacijo za kar nekaj parov lokacij. Želeli smo razdalje med lokacijami zaposlenih in strank, med domom starejših občanov in vsemi ostalimi lokacijami ter med vsemi pari strank med seboj. Pri tem smo upoštevali podatek, da je DSO natanko en, zaposlenih 29 in strank 168. V vmesnik smo poslali

29·168 + 1·(168 + 29) + (︃168

2 )︃

= 19097

zahtevkov. Vsak zahtevek za pridobitev razdalje med dvema lokacijama stane 0,005

$, toda Google nam podari200$ zastonj mesečnega proračuna, ki ga lahko porabimo za uporabo njihovih vmesnikov. Kljub temu je bilo potrebno nekaj previdnosti, da ne bi podatkov vsakič znova pridobivali, pač pa shranili enkrat in jih potem uporabljali ter po potrebi dopolnjevali. Podatke smo shranili v obliki slovarja, na način, da ima vsaka lokacija svoj podslovar, kjer so zapisane razdalje do ostalih lokacij, kot je prikazano v izseku 4.3.

{

"4 6.6 5 6 7 6 4,1 6.1 5 3 7 7": {

"4 6.7 5 4 4 6 5,1 6.0 0 6 5 4 9": [1 3 8 6, 2 0 3 3 9],

"4 6.6 2 8 0 2 6,1 6.2 1 9 3 0 7": [6 8 8, 8 1 9 1],

"4 6.5 7 1 8 0 3,1 6.2 3 1 3 8 5": [1 0 9 8, 1 4 0 0 6],

"4 6.6 6 0 1 0 9,1 6.1 6 5 3 0 9": [2 0 2, 1 4 3 6], ...

}

"4 6.6 6 6 8 8 4,1 6.1 3 6 7 3": {

"4 6.7 5 4 4 6 5,1 6.0 0 6 5 4 9": [1 2 2 6, 1 8 6 6 5],

"4 6.6 2 8 0 2 6,1 6.2 1 9 3 0 7": [8 5 0, 9 9 3 1],

"4 6.5 7 1 8 0 3,1 6.2 3 1 3 8 5": [1 2 6 0, 1 5 7 4 6],

"4 6.6 6 0 1 0 9,1 6.1 6 5 3 0 9": [2 8 9, 2 6 5 3], ...

} ...

}

Izsek programa 4.3: Izsek slovarja medsebojnih razdalj med dvema lokacijama.

Kot je vidno v izseku 4.3, za medsebojno razdaljo hranimo dve vrednosti. Prva predstavlja časovno razdaljo oziroma čas trajanja vožnje v sekundah med dvema lokacijama na podlagi Googlovih izračunov. Pri pošiljanju zahtevka lahko oprede- limo kdaj točno se bo vožnja zgodila oziroma tega ne opredelimo in dobimo neko povprečno vrednost. Če bi v praksi na določenih relacijah prihajalo do prevelikih razhajanj med predvidenim in dejanskim časom vožnje, bi podatke za posamezne lo- kacije ponovno pridobili, saj bi bilo možno, da zaradi del na cesti ali kakšnih drugih dejavnikov pride do odstopanj. Druga vrednost predstavlja razdaljo med lokacijama v metrih vožnje.

Pri reševanju problema se moramo odločiti, katero izmed teh dveh vrednosti bomo želeli minimizirati. Če bomo minimizirali čas vožnje, potem moramo tudi podatke pridobiti na način, da bomo med dvema lokacijama iskali pot, za katero porabimo najmanj časa, in ne poti, ki je najkrajša glede na prevoženo razdaljo.

Slika 4.1 prikazuje manjši zemljevid, kjer imamo na levi strani povezane lokacije na podlagi najkrajše poti, na desni strani pa na podlagi najhitrejše poti. V tem primeru se edino pot med A in C razlikuje pri obeh različicah — v resničnosti se lahko to velikokrat zgodi (npr. pot po avtocesti je hitrejša, a moramo narediti nekaj več kilometrov).

Na sliki 4.2 želimo v obeh primerih poiskati najkrajšo pot med posameznimi lokacijami. Izkaže se, da je pomembno, na kakšen način smo pridobili podatke o

Slika 4.1: Povezave med lokacijami glede na najkrajšo (levo) in najhitrejšo (desno) pot [9].

medsebojnih razdaljah lokacij. Če želimo dobiti najkrajšo pot, potem moramo že pri pridobivanju podatkov med pari lokacij iskati najkrajše poti. V nasprotnem primeru se nam lahko zgodi, da bomo dobili suboptimalno rešitev.

Slika 4.2: Iskanje najkrajše poti glede na vhodne podatke [9].

Podoben primer lahko vidimo na sliki 4.3, kjer želimo v obeh primerih minimi- zirati čas vožnje, a nimamo v obeh primerih ustreznih vhodnih podatkov.

V splošnem ljudje raje izberejo hitrejšo pot kot krajšo pot. Raje imajo avto- ceste kot lokalne ceste in raje asfaltne ceste kot makadame [9]. Pri izdelavi urnika pomoči na domu bomo minimizirali čas potovanja in temu primerno smo pridobili podatke. To je tudi Googlov privzeti način, ko pošljemo poizvedbo za pot med dvema lokacijama.

Slika 4.3: Iskanje najhitrejše poti glede na vhodne podatke [9].

4.2 Struktura programa

Naš program, ki rešuje problem izdelave urnikov pomoči na domu je v Javi sprogra- mirana aplikacija REST, ki je zgrajena s pomočjo orodja Quarkus, v ozadju pa za optimizacijo uporablja orodje OptaPlanner. REST (Representational State Trans- fer) je arhitekturni slog za vmesnik aplikacijskega programa (API), ki za dostop in uporabo podatkov uporablja zahteve HTTP [11]. V našem primeru za zdaj do pro- grama dostopamo le preko klicahttp://localhost:8080/urnik_oskrbe/solve, ki je tipa POST, v telesu zahtevka pa pošljemo vse vhodne podatke v obliki JSON.

Znotraj programa imamo več objektov, celotno domeno pa prikazuje slika 4.4.

Objekti, ki se tekom načrtovanja spreminjajo so tipa Task. Spremenljivka, ki jo načrtujemo in je označena s @PlanningVariable, je previousStandstill. Standstill je v resničnosti čas, ko zaposleni (User) ne potuje. Razred je implementiran kot vme- snik (interface), ki lahko predstavlja ali to, da je zaposleni pri stranki na izvajanju opravila ali pa doma (pred začetkom delovnega časa in po opravljenih vseh opra- vilih). Poleg spremenljivke previousStandstill se bodo tekom izvajanja programa spreminjale še nekatere druge spremenljivke. Te so na sliki 4.4 napisane z vijolično barvo. Gre za tako imenovane senčne spremenljivke (shadow variables). Kako se bo tekom načrtovanja spreminjal čas prihoda in odhoda (arrivalTime in departu- reTime) smo na kratko opisali v razdelku 3.1.3, zakaj imamo pri vsakem opravilu začetno in končno lokacijo (arrivalLocation indepartureLocation) in zakaj se bo dol- žina opravila (duration) tekom načrtovanja spreminjala pa je opisano v poglavju Rezultati. V splošnem je domena povzeta po domeni za reševanje problema razvoza s časovnimi okni, ki ga znotraj svojih primerov ponuja OptaPlanner.

Slika 4.4: Domena programa za izdelavo urnika pomoči na domu.

5 Rezultati

Program je sestavljen na način, da ga zaženemo z določenimi parametri (iskalni algoritem, čas reševanja, vzporedno izvajanje na več jedrih), nato pa čaka na vho- dne podatke, ki jih pošljemo prekoPOST zahtevka. Za lažje preverjanje obnašanja programa, iskanja hroščev v kodi in primerjanja dobljenih rešitev med seboj, smo uporabili nastavitev z oznako “REPRODUCIBLE”. Ta omogoča, da v primeru ena- kih vhodnih podatkov, enakega časa reševanja in enake porabe računalnikovih virov, poišče vedno enako rešitev. To pomeni, da tudi če se med iskanjem rešitve uporablja naključnost, bo ta v vsakem primeru izvedena na enak način. Čas iskanja rešitve lahko določimo poljubno dolg. Za manjši primer, kjer razporejamo 63 opravil, se je izkazalo, da pri iskanju rešitve s pomočjo metahevristik ni razlike v rezultatu pri 15-minutnem in 100-minutnem iskanju. OpraPlanner nam omogoča tudi, da reševanje ustavimo, ko določen čas ni spremembe vrednosti kriterijske funkcije, a takega načina nismo kaj dosti uporabljali. V naslednjih razdelkih je opisano, kako smo se lotili reševanja, na kakšne težave smo naleteli, kateri so bili večji izzivi pri implementaciji in kakšen je končni rezultat.

5.1 Omejitve

Da rešitev programa usmerjamo v želeno smer (kaj je želena smer, smo izvedeli s pomočjo ekspertnega znanja), opredelimo omejitve. Kaj posamezni omejitvi v OptaPlannerju lahko določamo, smo opisali v razdelku 3.1.2. Odločili smo se, da bodo poleg modelskih omejitev (tiste, ki jih opredelimo s samim načinom zapisa podatkov) še tri različne stopnje. Krepke (hard), srednje (medium) in šibke (soft) omejitve. Kakšna točno bo končna utež posamezne omejitve, bomo morali s pomo- čjo ekspertnega znanja in potreb posameznega doma starejših občanov še določiti.

Spodaj so opisane posamezne omejitve, ki smo jih dodali v program in kako vplivajo na končno rešitev:

Menjava zaposlenega pri določenem opravilu(user change conflict)

Stranke, ki so z domom starejših občanov domenjene za pomoč na domu, ne želijo, da bi se zaposleni pri obiskih pogosto menjavali. Če je na primer stranka dogovorjena za oskrbo vsak dan zjutraj, potem je najboljše, da jo vsak dan opravi isti zaposleni, saj ga je stranka navajena, mu zaupa, poleg tega pa tudi zaposleni pozna stanje, zdravstvene težave in posebnosti stranke, zato lahko delo bolj kakovostno in hitreje opravi.

Čim manj menjavanja dosežemo s tem, da ima vsako opravilo podatek za za- dnjega zaposlenega, ki je ta opravek opravljal (last_user). Na ta način lahko pri- merjamo zadnjega, ki je opravek opravljal, in trenutno dodeljenega. Poleg opravil, ki jih zaposleni opravlja pri strankah doma, to omejitev uporabljamo tudi za usmerjanje programa k rešitvi, kjer ima vsak zaposleni na urniku malico, ki mu je dodeljena. Za ta dva primera se razlikuje utež omejitve, ki je v obeh primerih na srednjem nivoju.

V primeru malice, kjer nočemo, da bi prišlo do položaja, ko bi imel en zaposleni dve malici, drugi pa nobene, je utež −2000, v vseh ostalih primerih pa−2. Razliko pri utežeh dosežemo z dodatnim parametrom, ki ga hranimo za vsako opravilo.

Ta omejitev je odvisna od parametra za zadnjega zaposlenega, ki opravilo opra- vljal. V primerih, ko bi bil določeni zaposleni en dan na dopustu ali imel bolniško, bi bilo treba paziti pri vhodnih podatkih, in sicer da določeno izjemo, ki se je zgodila in je bila izredna, ignoriramo.

Zaželeni in nezaželeni zaposleni (default and rejected users)

Vsaka stranka ima nabor zaposlenih, ki ji bolj ugajajo, in nabor zaposlenih, ki ji ne ugajajo. Gre za podatek, ki ga beležijo domovi za starejše občane in je namenjen predvsem temu, da zvišuje zadovoljstvo strank. Podatek za zaželene in nezaželene zaposlene za posamezno stranko pošljemo kot vhodni podatek v obliki množice ID- jev. Za vsako opravilo pogledamo, če je trenutno dodeljeni zaposleni znotraj množice zaželenih. V primeru da ni, potem to predstavlja znižanje vrednosti kriterijske funkcije za 3 na srednjem nivoju. Prav tako pogledamo, če je trenutno dodeljeni zaposleni znotraj množice nezaželenih. V primeru, da je, potem to predstavlja še dodatno znižanje vrednosti kriterijske funkcije za 4 na srednjem nivoju (poleg znižanja, ker zaposleni ni na seznamu zaželenih).

Podatki za zaželene in nezaželene člane se od doma do doma zelo razlikujejo.

Nekateri se s tem podatkom ne ukvarjajo, nekateri pa ga redno beležijo. V domu za starejše občane, od koder smo dobili podatke za izdelavo te naloge, pri zapisovanju niso preveč vestni. Vhodne podatke smo zato prilagodili na način, da smo pogledali, kateri zaposleni so bili v zadnjem času pri določeni stranki in smo tiste dodali na seznam zaželenih. To v praksi pomeni tudi to, da če je kršena omejitev pri zaželenih uporabnikih, potem je zagotovo prišlo tudi do kršitve prejšnje omejitve — menjava zaposlenega pri določenem opravilu.

Prihod izven časovnega okna (arrival after client due time)

Stranka je z domom starejših občanov dogovorjena, kdaj bo zaposleni prišel in izvedel obisk. Vnaprej je znano časovno okno, kdaj se mora obisk začeti. Program smo pripravili na način, da zaposleni ne more začeti obiska že pred dogovorjenim časom.

Če pride k stranki pred začetkom časovnega okna, potem mora počakati, kot je to prikazano na sliki 5.1.

Slika 5.1: Čakanje na opravilo, če zaposleni pride prezgodaj.

V primeru, da zaposleni pride po koncu časovnega okna, to kaznujemo z omeji- tvijo, ki je nastavljena tako, da vsaka minuta zamude predstavlja znižanje vrednosti kriterijske funkcije za 2 na srednjem nivoju.

Prekoračitev delovnega časa zaposlenega(arrival after user due time)

Delovni čas zaposlenega se začne ob prihodu k prvi stranki in zaključi z odhodom pri zadnji stranki. Večina zaposlenih ima 400-minutni delovnik s šestimi delovnimi dnevi v tednu. Za zdaj program ne odobrava nadur in jih kaznuje tako, da vsaka prekoračena minuta delovnika zaposlenega prispeva k znižanju kriterijske funkcije za 1 na srednjem nivoju. V primeru, da bi bila želja, da določenim zaposlenim nadur ne kaznujemo, bi lahko pri parametrih zaposlenega dodali utež, s katero bi pomnožili kazen te omejitve. Če bi posameznik torej želel delati nadure, bi bila utež nič, kar bi pomenilo, da se prekoračitev delovnika ne bi kaznovala.

Čas na poti (traveling time)

Pridobivanje časov med posameznimi lokacijami in na kaj moramo pri tem paziti, smo opisali v razdelku 4.1. Čas na poti želimo minimizirati ob upoštevanju zgornjih omejitev. Vsi časi, s katerimi operiramo znotraj programa, so podani v minutah, da ni preveč vmesnih preračunavanj. Vsaka minuta, ki jo zaposleni opravi pri vožnji, zmanjša vrednost kriterijske funkcije na šibkem nivoju za1.

Krepke omejitve (hard constraints)

Nobena od zgoraj naštetih omejitev ni krepka, kar pomeni, da bo vsaka rešitev, ki jo dobimo, dopustna. Vseeno smo se pri implementaciji odločili, da bomo imeli omejitve na treh nivojih, saj se zna zgoditi, da bo, na podlagi potreb posameznega doma starejših občanov, treba v program kaj dodati. Primer, da bi morali dodati še krepko omejitev, bi bil, da omejimo razvoznike kosil in da s krepko omejitvijo kaznujemo, če bi kosilo dostavil zaposleni, ki se s tem ne ukvarja in ki morebiti v avtu nima ustrezne opreme, da bi kosilo ostalo toplo.

Modelske omejitve

Najboljši način za to, da program usmerjamo v želeno rešitev, so zagotovo modelske omejitve. To so omejitve, ki jih opredelimo s samim načinom predstavitve podat- kov in ne morejo biti kršene. V primeru našega programa so modelske omejitve naslednje:

• Zaposleni ne more biti na dveh lokacijah hkrati— pri izdelavi urnikov bi se nam lahko zgodilo, da dvema opraviloma, ki potekata istočasno, dodelimo isto osebo, ki ju opravlja. Pri implementaciji našega programa smo to pre- prečili tako, da za vsakega zaposlenega tekom načrtovanja izdelujemo verigo njegovih opravil, kjer si le-ta sledijo v časovnem zaporedju in se ne prekrivajo.

• Vsako opravilo ima največ enega zaposlenega— lahko bi se zgodilo, da bi isto opravilo dodelili več zaposlenim, kar smo v našem programu preprečili s tem, da omejimo, da se lahko eno opravilo pojavi le v eni verigi opravil, ki jo ima posamezni zaposleni.

• Zaposleni ne more prehitevati časovnega okna — opisano pri omejitvi

“Prihod izven časovnega okna” in prikazano na sliki 5.1. To je implementirano na način, da za čas začetka opravljanja opravila vzamemo maksimum od časa prihoda in začetka časovnega okna.

• Prevzem kosila je vedno pred dostavo — pri opravilih, ki vključujejo dostavo kosila, je zagotovljeno, da se prevzem le-tega zgodi pred dostavo.

Podrobneje smo to opisali v razdelku 5.3.

5.2 Dodajanje malice

Zaposlenim, ki delajo poln delovnik, znotraj delovnega časa pripada 30-minutni odmor za malico. Odločali smo se med dvema možnostima, kako tak odmor imple- mentirati:

Samodejna zakasnitev

Ko določeno opravilo preseže neko vnaprej postavljeno časovno mejo, pride do sa- modejne zakasnitve, kar pomeni, da se trenutnemu opravilu podaljša čas trajanja za 30 minut. V konkretnem primeru to pomeni, da če je oskrbovalec začel delo ob 7.00 in želimo, da ima okoli 11.00 malico, potem se bo prvemu opravilu, ki preseže uro 11.00, podaljšal čas trajanja za 30 minut, kot to vidimo na sliki 5.2. V praksi bi to pomenilo, da bi zaposleni dokončal opravilo, nato pa bi imel 30 minut prostega časa. Ta način lahko implementiramo z uporabo senčnih spremenljivk.

Slika 5.2: Opravilu, ki preseže uro 11.00, se doda 30 minut, kar predstavlja malico zaposlenega.

Prednosti takega načina so:

• Ni nam potrebno dodajati novih opravil, ki bi bili za razliko od drugih, ki so vezani na stranke, vezani na zaposlene.

• Pri računanju razdalj med lokacijami opravil nam ta način ne predstavlja težav, saj opravilo, ki ga zaposleni opravlja, le podaljšamo za ustrezen čas, razdalje pa se bodo potem računale od lokacije trenutnega opravila do naslednjega kot v ostalih primerih.

• Zaposleni bo vsak dan vedel, kdaj lahko na svojem urniku pričakuje malico.

Slabosti:

• Manj prilagodljivosti pri tem, kdaj bo malica potekala. Mogoče bi bilo idealno, da bi zaposleni opravil še eno opravilo in imel potem malico v času, ko ima v svojem urniku, zaradi različnih časovnih oken strank, luknjo.

Malica kot opravilo

Pri tej možnosti dodamo malice med opravila, kar pomeni da imajo časovno okno, kdaj jih je treba opraviti in jih tako kot druge razporejamo v končni urnik.

Prednosti takega načina so:

• Imamo večjo svobodo, kdaj bo čas za malico potekal, kar pomeni, da bo pro- gram lahko z njimi zapolnil morebitne luknje v urnikih zaposlenih.

• Če želimo bolj omejiti čas malice posameznega zaposlenega, lahko ustrezno prilagodimo časovno okno, v katerem se mora izvesti.

Slabosti:

• Zahtevnejša implementacija.

• Problem povečamo z dodatnimi opravili, kar pomeni, da povečamo problem preiskovanja in s tem podaljšamo čas reševanja.

Odločili smo se, da bomo pri našem programu za izdelavo urnika pomoči na domu uporabili drugi način, saj je glavna prednost prvega to, da je lažji za implementacijo, pri drugem pa se zdi, da bodo lahko končni urniki boljši. Če imamo na primer dve opravili, ki imata enako časovno okno, in enega zaposlenega, ki ju mora opraviti, potem lahko pride do položaja, ki je prikazana na sliki 5.3. V zgornjem primeru malica sledi opraviluT₃, ki prvo preseže 11.00, kar pomeni, da opravilaT₄ne moremo začeti znotraj njegovega časovnega okna. Spodnji primer kaže drugi način, kjer opraviloT₄začnemo znotraj časovnega okna, malica pa se bo začela po tem opravilu.

Drugi način v tem primeru deluje boljše. Opazimo lahko, da je vsaka rešitev v prvem načinu lahko tudi rešitev v drugem načinu, obratno pa ne.

Glavni izzivi pri implementaciji malice kot opravila so bili:

Dodajanje novih opravil

Pred začetkom izdelave urnika, smo morali med obstoječa opravila dodati toliko opravil tipa malica, kolikor zaposlenih dela na dan, ki ga obravnavamo. Ker pri vsakem opravilu gledamo tudi stranko, na katero se nanaša, je bilo treba ustvariti za vsakega zaposlenega stranko, ki ima na listi zaželenih zaposlenih samega sebe.

Računanje razdalj med lokacijami

Opravilo je vezano na lokacijo in ko računamo pot zaposlenega med dvema opravi- loma, pogledamo v slovar razdalj, ki ga hranimo za vsako izmed lokacij (razloženo v razdelku 4.1). Če je tip opravila malica, potem to ni vezano na posamezno loka- cijo, ampak je čas vožnje od prejšnjega opravila enak 0, za razdaljo do naslednjega opravila pa moramo pogledati, koliko je od prejšnjega opravila do naslednjega, kot je to prikazano na sliki 5.4.

Da smo lahko dosegli tak način delovanja, smo vsem malicam določili, da se zgo- dijo na koordinatah 0,0 in za čas potovanja do malice določili 0 minut. Slovar razdalj opravila tipa malica pa smo tekom načrtovanja ves čas posodabljali, da je bil enak kot pri opravilu pred njim, kar smo lahko dosegli s pomočjo senčnih spremenljivk.

Slika 5.3: Primerjava obeh načinov pri primeru, kjer se drugi izkaže kot boljši.

Slika 5.4: Kako vstavljanje malice v urnik vpliva na čas vožnje.

Vsak zaposleni ima natanko eno opravilo z malico

Opravila in njihovo dodeljevanje so glavni del sestave urnika pomoči na domu. Po- sameznega opravila ne moremo določiti določenemu zaposlenemu, lahko pa omejitve prilagodimo na ta način, da bomo želen rezultat spodbujali. V objekt opravilo smo dodali parameter, ki označuje utež (weight), s katero se pri računanju prekršenih omejitev pomnoži utež omejitve. Za malico smo nastavili utež 1000 za vse ostale pa 1. Do tega množenja pride pri omejitvi, kjer primerjamo zadnjega zaposlenega, ki je določeno opravilo opravljal in trenutno dodeljenega, kot smo to opisali v razdelku 5.1 (Menjava zaposlenega pri določenem opravilu). Za vsako malico je zadnji, ki jo je opravljal, posamezni zaposleni. Tako program uspešno najde rešitev, ki vsako malico dodeli točno določenemu zaposlenemu.

5.3 Prevzem in dostava kosila

Tip opravila je lahko tudi dostava kosila ali pa dostava kosila z oskrbo. V tem primeru mora zaposleni kosilo najprej prevzeti v domu starejših občanov, nato pa ga dostaviti pri stranki doma. Sprva smo to želeli implementirati tako, da je vsak prevzem kosila v DSO predstavljal ločeno opravilo, ki je bil par z ustrezno dostavo.

Dodali smo omejitev, da mora zaposleni najprej prevzeti kosilo, nato pa ga dostaviti.

Četudi smo kršenje te omejitve visoko kaznovali, so bili rezultati zelo slabi.

Slika 5.5: Izsek rešitve za urnik pri ločenem prevzemu in dostavi.

Na sliki 5.5 vidimo izsek iz dobljene rešitve, ki ponazarja vse možne težave, do katerih je prišlo. Omeni tri zaposlene, s kraticami imena in priimka (PaVe, BoBr, KrMar), in njihov urnik. Celica obarvana z bež barvo predstavlja opravila, ki so tipa oskrba, zelena je malica zaposlenega, vijolična je prevzem kosila, modra dostava kosila, turkizna pa dostavo kosila z oskrbo. Težave, ki so na sliki 5.5 označene s črkami, predstavljajo:

• A — Uporabnik PaVe je pri stranki s številko 164 dostavil kosilo in opravil oskrbo, ne da bi kosilo za to stranko prej prevzel.

• B— Zaposleni je opravil opravilo, ki vključuje dostavo kosila, ki ga je prevzel kasneje.

• C— Prevzemi kosila so sicer skupaj, kar je dobro, saj zaposleni prihrani čas pri vožnji, a obenem prevzame tudi kosilo, ki naj bi ga dostavil pred tem in kosilo, katerega dostave nima na svojem urniku.

• D — Prevzem kosil za dostavi, ki ju zaposleni nima na urniku.

Zakaj je do take rešitve prišlo, četudi so bile kršitve visoko kaznovane, nam ni povsem jasno. Predvidevamo, da ker program ne loči posameznih opravil med seboj, je preizkušal različne možnosti, a tudi če je prevzem dodelil ustreznemu zaposlenemu, ni bilo zagotovljeno, da bi bilo opravljeno ob pravem času glede na dostavo. Tako je moral program opraviti ogromno število menjav parov opravil ali generiranj rešitev, da je za posamezni par prevzem in dostava dobil ugodno rešitev.

V komunikaciji z razvijalci OptaPlannerja smo dobili predlog, da prevzem in dostavo združimo. Rešitev se zdi na prvi pogled enostavna, vendar je bilo za imple- mentacijo treba zagotoviti dve ključni stvari:

Vhodna in izhodna lokacija

V primeru, da združimo prevzem in dostavo kosila, je lokacija do katere moramo priti na začetku opravila različna od lokacije, kjer opravilo končamo in od koder računamo čas vožnje naprej. S tem v mislih se je parameter za lokacijo opravila razdelil na vhodno (arrival) in izhodno (departure) lokacijo. Pri opravilih, ki so tipa oskrba, je ta vrednost za oba parametra enaka, pri tistih, kjer smo morali opraviti prevzem in dostavo pa različna. Ustrezno je bilo treba prilagoditi tudi računanje razdalj, da vedno računamo od izhodne lokacije opravljenega opravila do vhodne naslednjega.

Čas trajanja opravila

Čas trajanja opravila predstavlja prevzem kosila v DSO, vožnjo od vhodne do izho- dne lokacije in čas dostave kosila oziroma dostave z oskrbo, kar lahko vidimo na sliki 5.6. Čase za opravila smo morali izračunati na začetku pred izvajanjem programa.

Slika 5.6: Trajanje opravila pri združenem prevzemu in dostavi kosila.

Na tak način smo se izognili rešitvam, ki bi bile nesmiselne. Vsak prevzem se zgodi pred dostavo in oboje opravlja isti zaposleni. Izsek rešitve si lahko ogledamo na sliki 5.7.

Rešitev se na prvi pogled zdi v redu, a vendar lahko hitro opazimo prostor za izboljšavo. V primeru, ki je na sliki 5.7 označen s črko A se zgodi, da gre zaposleni po vsako kosilo posebej v DSO. Radi bi dosegli to, da če je več dostav kosil na urniku zaporedno, potem bi naredili en prevzem in opravili vse razvoze, kar bi prineslo določen prihranek časa. Tak prihranek časa je prikazan na sliki 5.8.

Slika 5.7: Izsek rešitve za urnik pri združenem prevzemu in dostavi.

Slika 5.8: Prihranek časa pri prevzemu več kosil hkrati.

Pri enakih časih izvajanja programa smo primerjali seštevek dolžin vseh delov- nikov zaposlenih pri urniku brez združevanja prevzemov kosil in pri urniku z zdru- ževanjem. To smo naredili za dan, ko je pomoč na domu opravljalo 8 zaposlenih (nedelja). Urnik brez združevanja predvideva, da bi zaposleni delali 3300 minut, medtem ko urnik z združevanjem 3168 minut, kar je več kot dve uri dodatnega časa.

Časovni prihranek je lahko velik, a je za implementacijo potrebno nekaj dodatnega prilagajanja programske kode. Na sliki 5.8 opazimo, da dostava kosila številka dva (K₂) sedaj ni več sestavljena iz prevzema na vhodni lokaciji, vožnje med DSO in izhodno lokacijo ter dostave kosila stranki, ampak le še iz dostave kosila stranki.

Tekom programiranja moramo tako v primeru zaporednih dostav kosila prilagajati vhodne lokacije in čase trajanja opravila. To nam omogočajo senčne spremenljivke, kjer opredelimo, kaj se zgodi s posameznim opravilom, preden in po tem, ko ga dodelimo določenemu zaposlenemu. Preden ga dodelimo mu ponastavimo vrednosti za vhodno lokacijo in čas trajanja na podatke, kot če bi bila samostojna dostava, po dodelitvi pa preverimo, kakšnega tipa je opravilo pred in za njim in ustrezno posodobimo parametre.

Pri taki implementaciji se lahko zgodi, da pridemo do položaja, ko prevzamemo kosila, nato pa imamo najprej dostavo kosila z oskrbo, za njim pa sledijo nadaljnje dostave (brez oskrbe). V tem primeru je čas od prevzema kosila do dostave zadnjega kosila lahko precej dolg in se kosilo tekom vožnje ohladi. Da bi preprečili tovrstne

težave, smo v program dodali omejitev, ki jo imenujemo omejitev hladnega kosila (cold lunch constraint), ki rešitev programa usmerja k temu, da se v primeru več zaporednih dostav najprej zgodijo tiste, kjer mora zaposleni le oddati kosilo, nato pa tiste, kjer mora zaposleni oddati kosilo in opraviti oskrbo. Na sliki 5.9 lahko zgoraj vidimo rešitev brez te omejitve in spodaj s to omejitvijo. Opravila, kjer gre le za dostavo kosila so obarvana modro, kjer mora zaposleni poleg dostave kosila opraviti tudi oskrbo pa s turkizno barvo. Vidimo lahko, da so v spodnjem primeru turkizna opravila za modrimi.

Slika 5.9: Izsek dveh rešitev, kjer je zgornja brez, spodnja pa z omejitvijo za hladno kosilo.

Vseeno se lahko zgodi, da program najde tako rešitev, ki bo kršila omejitev za hladno kosilo. Če želimo to povsem preprečiti, lahko program prilagodimo tako, da določene prevzeme združimo, določenih pa ne, kot je to prikazano na sliki 5.10.

Slika 5.10: Shematski prikaz, v katerih primerih pride do združevanja prevzema kosila.

Na sliki 5.10 vidimo, da v primeru, da imamo kosilo z oskrbo (turkizna barva), potem naslednjemu opravilu, ki tudi vsebuje kosilo, ne odrežemo stran prevzema. Če pa imamo najprej le kosilo (modra barva), potem pa naslednjemu opravilu, ki je tudi

povezano z dostavo kosila, prevzem eliminiramo. Na ta način program, podobno kot prej z omejitvijo hladnega kosila, silimo, da bo zaposleni najprej opravil “navadne”

dostave kosil in na koncu dostavo z oskrbo, saj v tem primeru verjetno skrajšamo čas vožnje zaposlenega, ki jo želimo minimizirati.

5.4 Izbira pristopa za optimizacijo

OptaPlanner nam omogoča, da za reševanje problema izberemo enega od že imple- mentiranih pristopov za optimizacijo. Kot smo opisali v razdelku 3.1.4, nam lahko pri izbiri najbolj primernega pomaga vgrajeno orodje za primerjalno analizo (bench- marker). Groba posplošitev obnašanja skupin različnih optimizacijskih pristopov, ki temelji na več letih izkušenj in velikemu številu testiranj na realnih problemih s strani razvijalcev OptaPlannerja, je prikazana na slikah 5.11, 5.12 in 5.13 [9]. Na sliki 5.11 je prikazana ocena, koliko časa porabi posamezna skupina za to, da najde rešitev. Graf nas lahko malenkost zmede, saj moramo upoštevati, da se za začetno rešitev iskalnih metahevrističnih pristopov v našem primeru uporablja rešitev pri- dobljena s požrešnim pristopom. Na vseh treh grafih (5.11, 5.12, 5.13) imamo na osi x spremenljivke s širokim naborom možnih vrednosti. V primeru, da bi šlo za binarne možnosti, potem se grafi nekoliko sploščijo. Čas na osi y je linearen.

Slika 5.11: Graf ocene porabljenega časa za izvedbo pri posameznem pristopu [9].

Na sliki 5.11 vidimo, da čas pri izčrpnem iskanju z naraščanjem števila spremen- ljivk eksponentno narašča in kmalu preseže mejo, ki označuje razpoložljiv čas.

Z naraščanjem števila spremenljivk narašča tudi potreben prostor, ki ga pri do- ločenem pristopu potrebujemo za izvedbo. Pri določenih metahevristikah lahko s pomočjo parametrov povemo, koliko pomnjenja dopuščamo. Na sliki 5.12 vidimo oceno za naraščanje potreb po hitrem pomnilniku (RAM) v odvisnosti od naraščanja števila spremenljivk.

Če preiščemo vse možnosti, potem zagotovo dobimo optimalno rešitev, vendar traja predolgo. Na sliki 5.13 vidimo pričakovano oceno dobljenega rezultata pri po- sameznem algoritmu. Vidimo, da s pomočjo metahevrističnih pristopov pričakujemo