A Memetic Algorithm With Optimal Quantity Assignments for the Fish Feed Maritime Inventory Routing Problem

Abstract

Oppdrettslaks er en av Norges mest verdifulle eksportvarer. Mindre kjent er fiskefôrindustrien som daglig produserer og distribuerer omtrent 5.000 tonn fôr til anlegg langs hele norskekysten. Lave profittmarginer gjør effektiv logistikk en nødvendighet for å tjene penger i industrien. I denne masteroppgaven presenterer vi de nåværende produksjons- og distribusjonsprosessene av laksefôr basert på informasjon fra SINTEF Ocean og vår industripartner, Mowi. Fokuset ligger på skaleringen av operasjonelle aspekter, restriksjoner på logistikken, variasjon i fôretterspørselen og utfordringer og begrensninger ved dagens system. I dag er distribusjonsprosessen basert på ordre utstedt av anleggene, som håndteres av forhåndsdefinerte ruter. Våre industripartner tror at det kan gjøres besparelser ved å gå over til en form for vendor-managed inventory (VMI).

Dette danner utgangspunktet for vårt problem, maritim ruting og lagerstyring av fiskefôr (fish feed maritime inventory routing problem – FFMIRP). FFMIRP består av en heterogen flåte og flere produkter, og tar for seg en distribusjonsprosess der distributøren er ansvarlig for å opprettholde tilstrekkelig lagerbeholdning på alle anlegg. Vi foreslår en matematisk modell for problemet, formulert som en kantflyt-basert blandet heltallsmodell med en diskret representasjon av tiden. Grunnet problemets kompleksitet er det vanskelig, om ikke umulig, å løse reelle probleminstanser til optimalitet med en kommersiell løser.

Som en konsekvens av problemets kompleksitet, utvikler vi en matheuristikk som er tiltenkt å løse større probleminstanser. Vi har kalt algoritmen "Scalable Memetic Optimization algorithm with LP-based search Techniques" (SMOLT). SMOLT benytter en memetisk algoritme for å bestemme hvordan hvert skip skal rutes, og kombinerer dette med et lineært program (LP) for å tilordne optimale leveringsmengder. Vi benytter en ny representasjon av rutingen, som består av (port, tid)-par for hvert skip. Løsningsmetoden vår inkluderer en rekke mutasjonsoperatorer som endrer ruteløsningene – blant annet ulike destruer & gjenoppbygg-metoder. SMOLT er designet for å kunne parallelliseres lett; dette tilrettelegger for høy grad av parallell utførelse. Denne parallelliseringen bidrar til å gjøre det mulig for SMOLT å løse større problemer enn de som er adressert i litteraturen frem til nå.

Testinstansene er generert basert på ekte data om skip og anlegg som vi har fått fra industripartneren vår, Mowi. Mindre instanser er generert ved å variere lengden på planleggingshorisonten og ved å trekke ut et tilfeldig utvalg av tilgjengelige anlegg, båter og produkter. Vi ser at den kommersielle løseren finner bedre løsninger enn SMOLT på noen av de små instansene, men SMOLT finner vanligvis omtrent like gode løsninger også i disse tilfellene. På de større, mer reelle instansene, utkonkurrerer SMOLT den kommersielle løseren og finner fornuftige løsninger. Som en del av analysen, presenterer vi SMOLT sine resultater på "MIRPLib Group 1"-instansene for å muliggjøre sammenligning med andre løsningsmetoder. Til tross for at SMOLT ikke er utviklet for å løse disse problemene, viser resultatene at algoritmen finner gode løsninger for de fleste instansene. Til slutt gir vi eksempler på mulige områder SMOLT kan bidra som et beslutningsstøttende verktøy i strategiske beslutninger, og diskuterer mulige fremtidige utbedringer av den foreslåtte løsningsmetoden.

Farmed Atlantic salmon is one of Norway's most valuable export goods. Supporting this industry, we find the fish feed industry responsible for producing and distributing around 5,000 tonnes of feed to fish farms along the Norwegian coast every day. Low margins make efficient logistics a necessity for operating profitably. We present the current process of producing and distributing fish feed to Atlantic salmon fish farms based on information from SINTEF Ocean and our industry collaborator, Mowi. The focus is on the scale of operations, logistic constraints, demand variations, and challenges and limitations in the current planning process. The current order-based system is a limitation, and industry partners believe that cost savings can be realized by changing to vendor-managed inventory (VMI).

This serves as the basis for our problem, the fish feed maritime inventory routing problem (FFMIRP). It is a heterogeneous vessel fleet, multi-product maritime inventory routing problem (MIRP) formulation for the distribution process, where the feed supplier is responsible for maintaining sufficient inventory at farms. We propose a mathematical model for the FFMIRP, formulated as an arc-flow mixed-integer linear program with a discrete time representation. Due to the scale and complexity of the problem, it is difficult, if not impossible, to solve real-world instances to optimality using a commercial solver.

Consequently, we develop a matheuristic intended to be applied to larger instances. The algorithm is termed the Scalable Memetic Optimization algorithm with LP-based search Techniques (SMOLT). SMOLT employs a memetic algorithm to decide how to route each vessel and combines this with a linear program (LP) for optimal quantity assignment. We use a novel representation for routing consisting of a list of (port, time)-pairs for each vessel. Our solution method implements a series of mutations operating on routing solutions – including a set of ruin & recreate methods, among these an adaption of SISR by Christiaens and Vanden Berghe (2020) to the MIRP. SMOLT has been designed to be easily parallelized, allowing it to be scaled out to nearly arbitrary levels of parallel execution. This allows us to solve larger problems than those addressed in the literature so far.

Test instances are created using real vessel and farm data provided by our industry partner, Mowi. Smaller instances are made by varying the duration of the planning horizon and by sampling a random subset of available farms, vessels, and products. When compared, we find that a commercial solver performs better than SMOLT on some small instances. However, our algorithm usually obtains solutions close to that of the solver in terms of objective value. For larger instances, SMOLT outperforms the commercial solver, and is able to identify reasonable solutions for real-world-sized instances. As part of our analysis, we present SMOLT's performance on the MIRPLib Group 1 instances to give a comparison to existing solution methods. Despite not being specifically designed to solve the MIRPLib instances, the results indicate that SMOLT can obtain high-quality solutions for most instances. Finally, we give examples of how SMOLT can be used to support more strategic decisions and discuss possible future improvements for the solution approach.