An Extended Model and a New Matheuristic for the Offshore Helicopter Routing Problem with Split Deliveries

Abstract

Olje- og gassindustrien er den største industrien i Norge, og det er forventet at den forblir viktig i flere tiår fremover. Utvinningen av petroleum foregår på den norske kontinentalsokkelen, og offshore-installasjoner er sentrale for produksjonen. I denne masteroppgaven blir transport av personell til og fra disse installasjonene ved hjelp av helikopter studert.

Forespørsler om transport av personell er samlet i ordrer, som er definert som personell som skal til eller fra samme installasjon på samme tidspunkt. En heterogen flåte med helikoptre stasjonert ved flere heliporter brukes til transporten. Sekvensen av heliporter og installasjoner som besøkes av et helikopter i løpet av en dag kalles for en flyvesekvens. Hvert helikopter kan benytte flere heliporter, men må starte og slutte sin flyvesekvens på den samme heliporten. Hvilke heliporter som brukes til å hente/levere ordre er valgfritt. Når installasjonene i en flyvesekvens byttes ut med ordrene som håndteres på hver installasjon, får vi det som kalles en rute. En ordre kan splittes mellom flere helikoptre. Målet er å minimere de totale kostnadene av å leie og bruke helikoptrene, samtidig som alle ordre fullføres og alle reguleringer og restriksjoner overholdes.

En litteraturstudie for det generelle pickup and delivery-problemet og offshore helikoptertransport blir presentert, med fokus på relevante utvidelser og heuristiske løsningsmetoder. Det å tillate at helikoptre benytter flere heliporter og gjøre det valgfritt hvilke heliporter som skal brukes til å hente/levere hver ordre, er nye utvidelser som ikke er funnet i litteraturen. En komplett matematisk beskrivelse av problemet er gitt av en arc-flow-modell. I tillegg er en ny matheuristikk foreslått som en løsningsmetode for problemet. En dekomponeringsmetode er brukt for matheuristikken, og problemet er dekomponert i tre deler. I den første endres flyvesekvensene fra den nåværende løsningen, og i den andre blir en labeling-algoritme brukt til å generere ruter fra de endrede flyvesekvensene. Til slutt løses et blandet heltallsproblem for å finne den beste kombinasjonen av ruter og passasjerer. Disse tre delene utgjør en iterasjon, og matheuristikken utfører så mange iterasjoner som mulig før termineringskriteriet er nådd.

Arc-flow-modellen er kun i stand til å finne optimal løsning for instanser med opptil åtte ordre inkludert, og matheuristikken løser nesten alle de samme instansene til optimalitet. Tester viser at matheuristikken konsekvent finner tilnærmet de samme løsningene for hver kjøring av instanser med opptil 40 ordre. Inkludering av de nye utvidelsene reduserer gjennomsnittlig objektivverdi med omtrent 9 % og det totale antallet helikoptre som trengs med 0,70. Splitting av ordre viser seg derimot å ha liten innvirkning på objektivverdien. Basert på resultatene virker det som de nye utvidelsene kan være nyttige tilskudd ved planlegging av offshore helikoptertransport.

The oil and gas industry is the biggest industry in Norway and is expected to remain important for several decades. The extraction of petroleum takes place on the Norwegian continental shelf, and offshore installations are vital for the production. In this thesis, the problem of transporting working personnel to and from these installations with the use of helicopters is studied.

The requests for transportation are aggregated into orders, which consist of personnel going to or from the same installation at the same time. A heterogeneous fleet of helicopters stationed at multiple heliports is used for the transportation. The sequence of heliports and installations visited by a helicopter during a day is called a flight sequence. Each helicopter is allowed to use multiple heliports, but must start and end its flight sequence at the same heliport. Which heliports to use for pickup/delivery of each order is optional. When replacing the installations in a flight sequence with the orders handled at each installation, we get what is defined as a route. An order can be split between multiple helicopters. The objective is to minimise the total cost of chartering and using the helicopters, while completing all orders and satisfying all regulations and operational restrictions.

A literature review on the general pickup and delivery problem and the offshore helicopter routing problem is presented, with focus on relevant extensions and heuristic solution methods. Allowing helicopters to use multiple heliports and making it optional which heliports to pickup/deliver each order at, are new extensions that are not found in the literature. A complete mathematical formulation of the problem is provided by an arc-flow model. In addition, a new matheuristic is proposed as a solution method for the problem. A decomposition approach is used for the matheuristic, and the problem is decomposed into three parts. In the first, changes are made to flight sequences from the current solution, and in the second a labeling algorithm is used to generate routes from the changed flight sequences. Finally, a mixed integer programming model is solved to find the best combination of routes and passengers. These three parts make up one iteration, and the matheuristic performs as many iterations as possible until the termination criterion is met.

The arc-flow model is only able to find the optimal solution for instances with up to eight orders included, and the matheuristic solves almost all of the same instances to optimality. Tests show that the matheurisitic consistently finds approximately the same solutions for each run of instances with up to 40 orders. Including the new extensions reduces, on average, the objective value by approximately 9 % and the number of helicopters by 0.70. Splitting of orders, on the other hand, is found to have little impact on the total cost. Based on the results, the new extensions could be beneficial additions to the offshore helicopter routing problem.