A Combined Optimization-Simulation Framework for a Maritime Inventory Routing Problem Under Uncertainty

Abstract

Denne masteroppgaven presenterer et rammeverk som kombinerer optimering og simulering for å løse et maritimt ruteplanleggings- og lagerstyringsproblem (MIRP) under usikkerhet for en global aluminiumsprodusent. Hensikten er å konstruere en leveringsplan over en taktisk planleggingshorisont som presterer godt under usikkerhet i reisetid og ankomsttid i lastehavner. For å oppnå dette utvikler vi et iterativt rammeverk som kombinerer simulering med to optimeringsmodeller.

Produsentens beslutninger deles i beslutninger som må tas flere uker før avreise; valg av skip og lastehavn, og beslutninger som er mer fleksible; ruting av skip og lossing. Steg 1 av rammeverket genererer en planlagt leveringsplan der valg av skip og lastehavn besluttes endelig. Steg 2 bruker simulering med en rerutingsmodell til å evaluere de planlagte leveringsplanene der rerutingsmodellen tillater fleksibilitet i ruting- og lossebeslutningene. En estimert usikkerhetskostnad assosieres med den planlagte leveringsplanen, noe som fører til at steg 1 av modellen genererer en ny leveringsplan i neste iterasjon av rammeverket. Denne prosessen gjentas til rammeverket har funnet en planlagt leveringsplan som er optimal under usikkerhet.

Rammeverket har initielt en tostegs-tilnærming der alle de usikre parametrene avsløres samtidig mellom steg 1 og steg 2. Vi utvikler videre en rerutingsmodell med flerstegs-tilnærming for å nærmere etterligne den virkelige beslutningsprossen. Målet med denne utvidelsen er å fange opp utfordringene ved å planlegge rerutingen med mangelfull informasjon. Deretter implementerer vi flere tiltak for å redusere kjøretiden inkludert parallel prosessering av løsninger og en to-fasetilnærming for evalueringen av løsnigner.

Resultatene viser at leveringsplanene som genereres av vårt rammeverk presterer betydelig bedre under usikkerhet enn de deterministik optimale leveringsplanene. Videre produserer rammeverket med flerstegs-tilnærming løsninger som håndterer usikkerheten i lastetid og reisetid bedre enn løsningene fra det originale rammeverket. Rammeverket løser realistiske probleminstanser innen en rimelig tid med både tostegs- og flerstegs-tilnærming.

This Master’s thesis presents an optimization-simulation framework for a tactical Maritime Inventory Routing Problem under uncertainty faced by a global aluminium producer. The aim is to find shipping schedules performing well under uncertain travel and port admission times. To accomplish this, we develop an iterative feedback framework combining simulation with two optimization models.

The producer’s decisions are divided into loading- and ship selection decisions, taken weeks prior to departure, and routing- and unloading decisions that are more flexible and can be altered after the uncertainty is revealed. Stage 1 of the solution framework generates planned schedules where the loading- and ship selection decisions are made. Stage 2 evaluates the solutions using simulation with a re-routing model to allow for some flexibility in the routing- and unloading decisions. The estimated cost of uncertainty for the planned schedule is then associated with the stage 1 solution in the next iteration of the framework, prompting the stage 1 model to create a different schedule. This process is repeated until it terminates with an estimated optimal solution under uncertainty.

The framework has a two-stage approach; revealing all the uncertain parameters between stage 1 and 2. However, to better imitate the real-world information structure, we further develop a multistage extension to the re-routing model. This model aims to capture the challenges of re-routing under incomplete information. Further, we implement several improvements to reduce the framework’s runtime. Most notably, we extend the framework to a two-phase evaluation approach as well as extract multiple solutions in each iteration and evaluate them in parallel.

The results of our computational study show that the solutions found using the framework perform significantly better under uncertainty than the optimal deterministic solutions. Also, the framework with multistage information structure produces more robust solutions with respect to uncertainty in travel and port admission times than the original two-stage approach. Further, the multistage framework can be solved within a reasonable runtime for realistic problem instances.