Masteroppgaver

Gruppen for optimering kan tilby oppgaver tilknyttet vår forskningsaktivitet innen anvendt optimering for både prosjekt- og masterstudenter.

Oppgavene kan gjøres mer eller mindre utfordrende, alt ut fra kandidatens ønsker, og vil generelt kunne lede frem til arbeid som er verdt å publisere. Gjennom årene har vi hatt både prosjekt- og diplomstudenter fra NTNU og hovedfags- og mastergradsstudenter fra UiO tilknyttet våre prosjekter. Etter oppgaven har flere fortsatt å jobbe hos oss som forskere eller som doktorgradsstudenter på oppgaver tilknyttet vår virksomhet.

SINTEF ønsker primært at oppgavene utføres i våre lokaler i Forskningsveien 1 i Oslo. Vi tilbyr fast arbeidsplass, og tilgang til egnet datautstyr.

For mer informasjon ta kontakt med Truls Flatberg (, tlf. 22 06 76 54).

Under følger noen eksempler på oppgaver:

• Planlegging i helsevesenet
• Serie- og cup-planlegging 
• Transportoptimering

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 eksempel på slike planleggingsproblmer er turnus- og operasjonsplanlegging. I løpet av de siste fem til ti årene har en voksende programvareindustri utviklet avanserte beslutniningsstø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 forskningsinstitutsjonen i samarbeid med universitetet i Nottingham som er 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).

Under gir vi eksempler på oppgaver:

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: Martin Stølevik 
, forsker, 22067672.

Oppsett av både serier og cup i norsk fotball har tidligere vært gjort som en manuell prosess. Dette er nå i ferd med å endres, og programvare basert på metoder fra operasjonsanalyse og AI (kunstig intelligens) tas i bruk som hjelpemidler.

Spilleplaner for fotball-ligaer er underlagt føringer og ønsker fra både lag, tilskuere, forbund og tv-selskaper – ønsker som ofte er i konflikt. Dette gjør at problemet med å lage løsningsmetoder som håndterer alle føringer/ønsker, er et interessant problem fra et operasjonsanalytisk perspektiv. Effektive og gode metoder er attraktive da inntekter fra både tv og tilskuere kan avhenge av en god spilleplan. Cupoppsett er et enklere problem, men med andre type føringer knyttet til reiseavstander og seeding.

Oppgaven vil bestå i sette seg inn i litteraturen på området og relatere denne til de norske problemene. Basert på dette skal det lages matematiske formulering av problemene og løsningsmetoder.

Oppgaven passer for en eller to studenter med interesse for optimering, programmering og fotball.

Kontaktperson: Truls Flatberg

, tlf. 22 06 76 54

Ø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 benytte en eller annen form for approksimasjonsmetode. Et polynomielt problem med mange anvendelser i transport er ”Shortest Path Problem” (SPP, Korteste (raskeste, billigste) vei-problemet). Likevel er det utfordringer i å løse SPP effektivt for store transportnettverk, og i å løse rike modeller av raskeste vei-problemer, for eksempel der hastighetene i transportnettet varierer over tid. I industrielle anvendelser av VRP og TSP må en som regel løse et meget stort antall SPP som delproblemer.

Avdeling for anvendt matematikk ved SINTEF IKT har i mange år forsket på problemer innen transportoptimering, med fokus på anvendelser særlig innen land og sjøbasert godstransport. Vi har utviklet metoder for SPP 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 metoder for 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, eller ved utvidelse av SINTEFs generiske programvare.

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

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.

Kantruting

Kantrutingsproblemer (Arc Routing Problem, ARP) er varianter av VRP. Her er transportoppdragene er definert på kanter i transportnettverket i stedet for noder. Eksempler på anvendelser er strøing og snømåking. Det skal utvikles metoder som er effektive for rene ARP og kombinasjoner av ARP og VRP.

I en stor del av VRP-litteraturen forutsettes det at alle kjøretøy er like. Denne forutsetningen gjelder sjelden i reelle anvendelser. I oppgaven skal VRP med heterogen flåte undersøkes. Metoder for optimalisert flåtesammensetning skal utvikles.

Mange av de beste metodene for VRP lar seg forholdsvis enkelt parallellisere. I oppgaven skal det utvikles en parallell VRP-løser som også vil utnytte flerkjerne-prosessorer.

Det skal utvikles teknikker som sikrer effektive SPP-beregninger i store transportnettverk, eksempelvis i elektroniske veinett for Europa. Teknikkene skal også være tilpasset bruk der SPP inngår i løsing av VRP. Viktige spørsmål er caching-strukturer, kompakte representasjoner. Oppgaven knyttes til SINTEFs SPP-beregner SPIDER Guider II.