Matematikk og planlegging i helsevesenet

Et sykehus er en kompleks organisasjon der ressurser og aktiviteter må koordineres. For å oppnå god ytelse må optimerte planer utvikles. Disse planene bør revideres dynamisk slik at endringer til en hver tid blir hensyntatt. Kjente og svært komplekse eksempler på slike planleggingsproblemer er turnus- og operasjonsplanlegging. I løpet av de siste fem til ti årene har en voksende programvareindustri utviklet avanserte beslutningsstøttesystemer for helsesektoren. Slike systemer kan fange, organisere og presentere data. I noen tilfeller gir systemene også støtte for manuell eller semi-automatisk planlegging. Gitt den iboende kompleksiteten i planleggingsoppgavene og den økende etterspørselen etter kvalitet og effektivitet i helsevesenet, må slik planleggingsverktøy i fremtiden benytte moderne, avanserte optimeringsmetoder .

HOSPITAL er et femårig forskningsprosjekt som finansieres i hovedsak av Norges forskningsråd. SINTEF er den sentrale forskningsinstitusjonen i samarbeid med universitetet i Nottingham, begge verdenskjent for sin forskning på optimerings­metoder for automatisk planlegging. I prosjektet forsker vi på forbedrede og nye optimeringsmetoder til bruk i beslutningsstøttesystemer i helsevesenet.

Oppgaver
Forutsetninger: kunnskap om og interesse for programmering. Kjennskap til optimering. Det kan være aktuelt å samarbeid med en av bedrifteme i prosjektet; DIPS (operasjonsplanlegging) eller Gatsoft (turnusplanlegging).

Eksempel 1:

• Sette seg inn i problemet (turnus-/operasjonsplanlegging).
• Matematisk formulering av (deler av) problemet. Implementering i Xpress-MP eller CPLEX.
• Testing av ulike case.
• Sammenligning av ulike metoder for løsing av problemet.

Eksempel 2:

• Sette seg inn i problemet (turnus-/operasjonsplanlegging).
• Studie av eksisterende modell og løsningsmetoder
• Modellere og implementere forbedringer i den studerte metoden.
• Testing av ulike case.

Kontaktperson: Atle Riise
Beskyttet adresse, tlf. 22067697. 

Transportoptimering

Økonomisk og miljømessig effektiv transport krever god koordinering. I kjernen av de fleste transportanvendelser ligger det beregningsmessig harde (NP-harde), diskrete optimeringsproblemer. Det mest kjente er "Travelling Salesman Problem" (TSP, Handelsreisendeproblemet). I TSP skal en finne billigste (korteste, raskeste) rundtur for et gitt sett med byer og gitt tabell over reisekostnader mellom dem. "Vehicle Routing Problem" (VRP, Ruteplanleggingsproblemet) er en generalisering av TSP der en "flåte" av kjøretøy skal betjene et antall transportoppdrag. Kjøretøyene har kapasitet, og hvert oppdrag har en størrelse. I reelle anvendelser er det gjerne en rekke tilleggsføringer; tidsvinduer, kompatibiliteter, lagerføringer osv. I praksis er VRP langt hardere å løse enn TSP, og for industrielle anvendelser må en oftest benytte en eller annen form for approksimasjonsmetode.

Et polynomielt problem med mange anvendelser i transport er "Shortest Path Problem" (SPP, korteste (raskeste, billigste, beste) vei-problemet). Likevel er det utfordringer i å løse SPP effektivt for store transportnettverk, og i å løse realistiske modeller av beste vei-problemer. I virkelige transportnettverk varierer hastighetene i over tid (rushtid), og egenskapene i nettverket kan endre seg hurtig f.eks. ved trafikkuhell. Både i persontransport og godstransport er det aktuelt å se på integrerte nettverk som omfatter flere transportmodi.

Avdeling for anvendt matematikk ved SINTEF IKT har i mange år forsket på problemer innen transportoptimering, både innen gods- og persontransport. Vi har utviklet metoder for SPP, TSP og VRP som gir ytelse helt i verdenstoppen. Noen av metodene er implementert i programvare, og programvaren er kommersialisert, blant annet gjennom knoppskyting. Avdelingen har en rekke publikasjoner i anerkjente tidsskrift og på internasjonale konferanser innen feltet, og et stort internasjonalt forskernettverk. Videre har vi god kontakt med industri, både brukere og verktøyleverandører, i Norge og i utlandet.

Det er fremdeles mange betydelige utfordringer innen transportoptimering. Oppgavene som er beskrevet under er eksempler, og tenkt som utgangspunkt for videre diskusjon med interesserte studenter. Det er en fordel med bakgrunn og interesse innen diskret optimering og/eller algoritmer og datastrukturer. Oppgavene vil omfatte litteraturstudier, modellering, analyse, algoritmeutvikling og eksperimentelle undersøkelser. Oppgavene kan fokuseres mer eller mindre mot anvendelser eller teori. Implementering kan foregå ved utvikling av prototyp fra grunnen av, ved bruk av kommersielle løsere, eller ved utvidelse av SINTEFs generiske programvare.

Se også våre sider innen transportplanlegging.

Kontaktperson: Geir Hasle Beskyttet adresse tlf. 22 06 78 87 mob. 930 58 703

Effektiv logistikk i mediebransjen
Logistikk-kostnadene er en stor andel av de totale kostnadene for papirbaserte medieprodukter som aviser. Blader og aviser er ferskvare som skal trykkes og distribueres til abonnenter og utsalg innen strenge tidsfrister og med lav kostnad. Det er mange uløste logistikkoppgaver innen mediebransjen. Eksempelvis er distribusjon av abonnements- og løssalgsaviser ikke koordinert. Heller ikke er det foretatt optimalisering av hvilket produkt som skal trykkes hvor med mål om effektiv totallogistikk. Store kostnadsbesparelser synes mulig for en bransje som er presset økonomisk.

I oppgaven vil vi fokusere på et optimeringsproblem innen logistikk for papirbaserte medieprodukter, fortrinnsvis ett av de to skissert over, men andre er aktuelle. Oppgaven vil bestå av litteraturstudium, matematisk modellering, analyse og eksperimentelle undersøkelser. Det er mest aktuelt å bruke et kommersielt verktøy som Xpress-MP til modellering og eksperimentelle undersøkelser, men det kan og være aktuelt å utvikle en tilpasset optimeringsalgoritme for problemet. Kvantifisering av besparingspotensial er et viktig mål.

Det er naturlig å knytte oppgaven til det pågående innovasjonsprosjektet Respons, der SINTEF er forskningspartner. Industripartnere er Distribution Innovation, VG, Aftenposten, Coop og NR1 Trykk så det vil være god tilgang på case-informasjon. Videre vil oppgaven knyttes til forskningsprosjektet DOMinant II, der NTNU/IØT, Høgskolen i Molde og SINTEF IKT er partnere.

Kombinert kantruting og noderuting
I operasjonsanalyselitteraturen for Vehicle Routing Problem (VRP) er det et gjennomgående skille mellom noderuting der "oppdragene" er lokalisert i punkter, og kantruting, der visse kanter i et transportnettverk skal betjenes. Eksempel på noderuting-anvendelser er henting av pakker i lokaldistribusjon, mens snømåking og strøing er eksempler på kantruting. Det er foretatt lite forskning på generaliserte VRP som kombinerer av node- og kantruting. Anvendelser fins for eksempel innen renovasjon. Dessuten vil aggregering av kunder for å redusere antall oppdrag generelt føre til et blandet problem.

SINTEF har i flere år arbeidet med kombinert kant- og noderuting, både på idealiserte modeller, og på rike modeller i forbindelse med utvikling av verktøy for optimalisering av budruter. I oppgaven skal vi primært studere kombinert kant- og noderuting på en idealisert modell. Det skal utvikles en ny metode som kombinerer eksakte metoder fra matematisk programmering med heuristiske løsningsmetoder. Metoden skal undersøkes på standard testproblemer.

Det er naturlig å knytte oppgaven til det pågående innovasjonsprosjektet Respons, der SINTEF er forskningspartner. Industripartnere er Distribution Innovation, VG, Aftenposten, Coop og NR1 Trykk så det vil være god tilgang på case-informasjon. Videre vil oppgaven knyttes til forskningsprosjektet DOMinant II, der NTNU/IØT, Høgskolen i Molde og SINTEF IKT er partnere.

TSP med sideføringer
Eksakte metoder for TSP er interessante i forbindelse med løsing av VRP, for eksempel for å gjøre gode VRP-løsninger enda bedre. Her må TSP i mange tilfeller utvides med sideføringer, for eksempel kapasitet på kjøretøy og tidsvinduer for oppdragene. Slike metoder skal utvikles og undersøkes ved beregningseksperimenter. Videre skal effektive approksimasjonsmetoder utvikles for probleminstanser som er for store til å løses eksakt innen rimelig tid.