A Decomposition-Based Matheuristic for the Two-Echelon Multi-Product Maritime Inventory Routing Problem

Abstract

Sjøfart som transportmetode har lenge vært ryggraden i verdensøkonomien, og transporterer i dag omtrent 80% av den globale handelen per volum. Ettersom dette er en langsom transportsmetode, er det nødvendig med omfattende ruteplanlegging. Med bruk av matematisk optimering som besluttningsstøtte er det mulig å redusere operasjonskostnadene betydelig. Selv om maritime ruteplanleggingsproblemer har vært forsket mye på de siste tiårene, er det svært få studier som omfatter problemer med transport av flere produkter og flere ledd mellom produsent og forbruker.

Problemet i denne masteroppgaven omhandler transport av flere produkter i en verdikjede med mellomlagre mellom produsent og forbruker. I første ledd blir produkter transportert over lengre distanser fra en produsenthavn til de regionale mellomlagrene. Fra de regionale mellomlagrene blir produktene transportert videre over kortere distanser til forbrukere, og dette utgjør andre ledd. Det er én region som kun består av produsenten. De resterende regionene har ett regionalt mellomlager, og flere forbrukere. Hver region har en heterogen flåte med skip. Målet er å minimere kostnadene ved å avgjøre når, hvor, og hvor mye av hvert produkt som skal transporteres. I tillegg avgjøres det når og hvor mye som skal kjøpes og selges på spotmarkedet som er tilgjengelig for de reginalene mellomlagrene.

To matematiske modeller er presentert, inkludert en fixed-charge network flow (FCNF) med tilhørende gyldige ulikheter og innstramninger av variabelgrenser. En dekomponeringsheuristikk er implementert med mål om å finne løsninger av høy kvalitet på større instanser. Heuristikken utnytter problemstrukturen ved å aggregere etterspørselen i hver region, og deler problemet opp i subproblemer som løses iterativt. Den benytter FCNF-modellen som viste seg best egnet for å raskt finne løsninger for subproblemene. Preprosessering er benyttet, samt en kombinasjon av clustering og et relax-and-fix og fix-and-optimize rammeverk som benyttes når subproblemene blir for komplekse for den eksakte FCNF-modellen. I beregningsstuidet klarer heuristikken å finne løsninger for alle 75 instanser og den eksakte modellen finner løsinger for 37. Blant disse 37 instansene finner heuristikken beste objektivverdi i 10 av dem, og den gjennomsnittlige objektivverdien er 0,9% høyere enn for den eksakte modellen. Analyser viser at heuristikken i gjennomsnitt fjerner ca. 70% av heltallsvariablene sammenlignet med den eksakte løsningsmetoden.

Maritime transport is the backbone of the global trade economy with more than 80% of the volume of international trade transported by sea. Being a slow mode of transportation, comprehensive scheduling is essential, and using mathematical optimization as a support tool can help reduce the costs of operating. Even though maritime inventory routing problems have been subject to a significant amount of research for the last decades, problems with two echelons and multiple products are not yet found in the literature.

In the problem at hand, multiple products are transported in a two-echelon supply chain. In the first echelon, the products are transported over long distances from a production port to regional hubs. Products are further distributed over shorter distances from the hubs to consumption ports in the second echelon. There is one region containing only the production port, with the remaining regions containing one hub and multiple consumption ports. Each region has a heterogeneous fleet of vessels. The objective is minimizing costs by deciding when, where, and how much of each product to transport, as well as how much and when to buy or sell in an external spot market available to all hubs.

Two arc-flow models for the problem are formulated, including a fixed-charge network flow formulation (FCNF), to which valid inequalities and variable bound tightenings are implemented. A decomposition matheuristic is developed with the aim of obtaining high quality solutions for larger instances. The matheuristic takes advantage of the problem structure by aggregating the demand in each region and splitting the problem into smaller subproblems, which are then solved iteratively. It applies the FCNF model, as this proved to be the best exact model for quickly finding high-quality solutions for the subproblems. Preprocessing techniques are applied, as well as a clustering technique combined with a relax-and-fix and fix-and-optimize framework when subproblems are too computationally heavy for the exact FCNF. In the computational study, the matheuristic finds feasible solutions to all 75 test instances, whereas the exact solution method finds feasible solutions to 37. Out of these 37 instances, the matheuristic finds the best objective value in 10, and the average objective value of the matheuristic is 0.9% higher than for the exact method. Analysis shows that the matheuristic on average removes around 70% of integer variables compared to the exact solution method.