Vis enkel innførsel

dc.contributor.advisorFagerholt, Kjetil
dc.contributor.advisorSlette, Hans Tobias
dc.contributor.authorLianes, Ingeborg Margrete
dc.contributor.authorNoreng, Maren Theisen
dc.date.accessioned2021-09-14T17:06:35Z
dc.date.available2021-09-14T17:06:35Z
dc.date.issued2020
dc.identifierno.ntnu:inspera:55508684:57885796
dc.identifier.urihttps://hdl.handle.net/11250/2776932
dc.descriptionFull text not available
dc.description.abstractFiskeoppdrett representerer i dag en av Norges viktigste næringer, og frem mot 2050 er målet å nå en samlet produksjon på 5 millioner tonn på en bærekraftig måte. For å klare dette, kreves det store teknologiske fremskritt, i tillegg til å legge til rette for stordrift gjennom blant annet smartere håndtering av logistikk. Denne masteroppgaven tar for seg ruting av servicebåter til fiskeoppdrettslokasjoner, for gjennomføring av vedlikeholdsoppgaver. Problemet er referert til som et rutingproblem for servicefartøy i riskeoppdrettsnæringen (Aquaculture Service Vessel Routing Problem - ASVRP), og objektivet for problemstillingen er å konstruere ruter som maksimerer antall vedlikeholdsoppdrag gjennomført av en gitt flåte av servicefartøy, samtidig som seilingskostnadene minimeres. Rutene konstruert har som formål å kunne brukes som beslutningsstøtte for operasjonell planlegging. Servicefartøyene som opererer i fiskeoppdrettsnæringen i dag, utgjør en heterogen flåte. Dette betyr blant annet at båtene har ulike operasjonelle forutsetninger. Videre setter noen av service oppdragene ulike krav til gjennomførelse. Noen av service oppdragene krever blant annet at flere båter utfører dem samtidig. Noen oppgaver kan bli utført av ett stort fartøy, eller av to eller flere små, og noen oppgaver må gjøres før andre. Videre påvirker værforholdene hvor lang tid det tar å seile mellom to oppdrettslokasjoner, eller hvor lang tid det tar å gjennomføre et oppdrag. Disse tidene kan derfor ansees å være tidsavhengige. Viktigheten av å gjennomføre et oppdrag varierer mellom oppdragene. For å fange den operasjonelle planleggingssituasjonen til en fiskeoppdretter i dag, er problemet formulert som et tidsavhenging profittmaksimerende rutingproblem med tidsvinduer og synkronisering. Den matematiske modellen er presentert som en blandet heltallmodell (MIP modell), med diskret tid. Tilleggene til den standardiserte ruteoptimeringsmodellen, er lagt til for å håndtere den problemspesifikke oppførselen til fartøyene som opererer i fiskeoppdrettsnæringen, og for å klare og tilfredsstille alle kravene for gjennomføring av et serviceoppdrag. Testinstansene brukt i denne oppgaven omfatter oppdrettslokasjonene til MOWI langs norskekysten. Disse har en normalfordelt etterspørsel etter serviceoppdrag som dekker et bredt spekter av spesialiserte oppdrag for næringen. Fartøyene som det planlegges for ligner i stor grad på de som brukes i næringen i dag. I tillegg har historisk værdata blitt brukt for å generere tidsavhengige seilings- og operasjonstider. Å finne eksakte løsninger for MIP modellen er ikke mulig for alle store testinstanser. Derfor har en Adaptive Large Neighborhood Search (ALNS) heuristikk blitt implementert i denne masteroppgaven som alternativ løsningsmetode for rutingproblemet. Heuristikken har blitt tilpasset for å hensynta alle de spesielle forutsetningene som definerer rutingproblemet for servicefartøy i fiskeoppdrettsnæringen. For mindre testinstanser, der det er mulig å løse problemet til optimalitet ved å bruke en eksakt solver, leverer ALNS heuristikken løsninger med et optimalitetsgap på omtrent 1%. Videre klarer den, for testinstanser av varierende størrelse, referert til som liten, middels og stor, å levere løsningene med en gjennomsnittlig løsningstid på omtrent to minutter. Disse resultatene indikerer at den implementerte ALNS heuristikken klarer å løse det presenterte rutingproblemet av servicefartøy for fiskeoppdrettsnæringen.
dc.description.abstractAquaculture represents one of the most important industries in Norway, and by 2050 Norway could farm five million tonnes of fish per year, if key production and environmental challenges are addressed. In order to address these challenges, there is a need for technological advances and smart handling of logistics. This thesis examines the problem of routing a set of service vessels to a set of fish farming locations, to perform a set of service tasks, and is referred to as the Aquaculture Service Vessel Routing Problem (ASVRP). The main objective is to maximize the number of service tasks performed by a given fleet, while also minimizing sailing cost. The operation schedules are meant to serve as a decision support tool in operational planning. The vessels routed in the ASVRP compose a heterogeneous fleet and hold different operational capabilities. Certain service tasks require the simultaneous operation of more than one vessel. Some tasks can also either be performed by one large vessel, or by two or more small vessels, depending on their capabilities. Furthermore, some tasks hold precedence over others. Varying weather conditions make the sailing times and task durations time dependent. Lastly, the importance of performing a task in the current planning horizon differs between the tasks. To properly capture the real-life planning setting faced by the operational planners in the aquaculture industry today, the problem is formulated as a time dependent, prize collecting vehicle routing problem with synchronization constraints and time windows. The mathematical model is presented as a Mixed Integer Problem (MIP) model, with discrete time. The extensions to the standard vehicle routing problem are introduced to be able to handle the problem specific behavior of the service vessels and matching service task requirements and vessel capabilities. The test instances cover the MOWI fish farms found along the Norwegian coast. The demand for operations at each location has been drawn from a normal distribution, and tasks included cover a wide range of industry specific complexities. The vessel types used resemble real vessels operating in the industry today. Finally, historical weather data has been used to generate the time dependent sailing and operation times. Solving the MIP to optimality is either too time consuming, or not possible, for large instances of the problem. An Adaptive Large Neighborhood Search (ALNS) heuristic has thus been implemented in this thesis to serve as a solution method for the ASVRP. The heuristic is adapted to handle the problem specific constraints of the ASVRP. Further, the results provided by the ALNS heuristic are promising. For the small test instances where the commercial solver is able to provide an exact solution, the average optimality gap from the ALNS solution is about 1%. Furthermore, test instances capturing the range of planning scenarios seen in the aquaculture industry today, consisting of three different sizes defined as small, medium and large, were solved by the ALNS heuristic with an average run time of about two minutes. The results indicate that the implemented ALNS heuristic can be used as a solution method for the ASVRP.
dc.language
dc.publisherNTNU
dc.titleAn Adaptive Large Neighborhood Search Heuristic for the Aquaculture Service Vessel Routing Problem
dc.typeMaster thesis


Tilhørende fil(er)

FilerStørrelseFormatVis

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel