A Matheuristic for a Perishable Distribution Problem with Time Windows

Abstract

Denne oppgaven omhandler det nasjonale distribusjonsproblemet til Bama, en stor norsk grossist av frukt og grønt. Frukt og grønt er ferskvarer, noe som betyr at kvaliteten deres forringes over tid. Målet er derfor å levere produktene fra produsentene til distribusjonssentrene på en effektiv måte. Det vil si å minimere distribusjonskostnader, utslipp av drivhusgasser (GHG) og matsvinn. I problemet som studeres i denne oppgaven distribueres produktene enten direkte fra produsent til distribusjonssenter, eller gjennom et samlastningsanlegg. Distribusjonsplaner opprettes på ukentlig basis. Operasjonsanalyse er av stor interesse for forsyningskjeder for ferskvarer på grunn av dens evne til å håndtere flere målsettinger og identifisere effektive løsninger for industrielle problemer som omfatter mange produsenter, distribusjonssentre og produkter.

Det utføres en litteraturstudie om forsyningskjeder med og uten ferskvarer. Studien fokuserer hovedsakelig på litteratur om forsyningskjeder for ferskvarer med hensyn til produktets ferskhet og samlastningsanlegg. I tillegg utforskes litteraturen om forsyningskjeder som tar hensyn til GHG-utslipp og muliggjør levering av produkter innenfor et tidsvindu. Studien viser det er begrenset med litteratur om forsyningskjeder for ferskvarer med samlastningsanlegg som tar hensyn til både produktets ferskhet og GHG-utslipp. Som et resultat bidrar denne oppgaven med en matematisk modell som tar hensyn til alle disse forholdene.

Formålet med denne oppgaven er å oppnå innsikt i potensielle forbedringer av Bamas forsyningskjede for nasjonale produkter. Dette oppnås ved planlegging på operasjonelt nivå og analyse av resultatene fra dette. Vi definerer formelt Bama's Domestic, Inbound Distribution Problem (BDIDP), som er det operasjonelle problemet med å bestemme den ukentlige distribusjonen av Bamas nasjonale produkter fra produsenter til distribusjonssentre. En lineær blandet heltallsmodell (MILP) er utviklet for å løse BDIDP. MILP-modellen er formulert som et flerobjektivt optimeringsproblem som omfatter tre målsettinger; minimere distribusjonskostnader og transportutslipp, og maksimere produktenes ferskhet.

En iterativ heuristikk er foreslått for å løse BDIDP. Det er en matheuristikk som relakserer heltallsvariablene før den gradvis innfører heltallsrestriksjoner og fikserer heltallsverdiene iterativt. Heuristikken gir en realistisk løsning på en instans av BDIDP innen rimelig tid. For den komplette ukentlige instansen oppnår matheuristikken en drastisk reduksjon i relativt gap sammenlignet med den eksakte løsningsmetoden. Det er bevist at heuristikken finner en løsning som er rimelig nær den optimale løsningen. Heuristikken viser seg å oppnå realistiske løsninger for en instans med flere produkter, produsenter og distribusjonssentre. Dette arbeidet kan fungere som grunnlag for videre forskning på distribusjon av ferskvarer med flere målsettinger.

Den iterative heuristikken brukes på BDIDP for å oppnå innsikt til Bamas beslutningsprosesser. Disse beslutningene innebærer å introdusere et ekstra samlastningsanlegg i forsyningskjeden, legge til fleksibilitet i leveringstidene og hente produkter hos færre produsenter. Det vises at å øke tidsvinduet for levering og å klynge produsenter både reduserer distribusjonskostnader og transportutslipp, mens å innføre et ekstra samlastningsanlegg ikke gir betydelige besparelser. Ingen av justeringene i forsyningskjeden viser seg å ha en betydelig innvirkning på den generelle ferskheten til produktene. Imidlertid vises det at distribusjon gjennom hovedterminalen fører til en lavere ferskhetsverdi.

This thesis concerns the domestic distribution problem of Bama, a large Norwegian wholesaler of fruits and vegetables. Fruits and vegetables are perishable products, meaning their quality deteriorates over time. The aim is therefore to deliver the products from producers to distribution centers efficiently. That is, minimizing distribution costs, greenhouse gas (GHG) emissions, and food waste. In the problem studied in this thesis, products are either distributed directly from the producer to the distribution center, or through an intermediate facility. Distribution plans are created on a weekly basis. Operations Research is of great interest to perishable supply chains due to its ability to address multiple objectives and identify efficient solutions to industrial-scale problems involving numerous producers, distribution centers, and products.

A literature study concerning supply chains both with and without perishable products is conducted. The study mainly focuses on literature regarding perishable supply chains with freshness considerations and intermediate facilities. In addition, literature on supply chains that consider GHG emissions and allow for the delivery of products within a time window is explored. The study shows that the literature on perishable supply chains with intermediate facilities that consider both product freshness and GHG emissions is limited. Consequently, our contribution is a mathematical model that considers all these concerns.

The purpose of this thesis is to obtain strategic insights into potential improvements to Bama's supply chain for domestic products. This is accomplished by planning on an operational level and analyzing the results. We formally define Bama's Domestic, Inbound Distribution Problem (BDIDP) which is the operational problem of deciding the weekly distribution of Bama's domestic products from producers to distribution centers. A Mixed Integer Linear Program (MILP) model is developed to solve the BDIDP. The MILP is formulated as a multi-objective optimization problem comprising three objectives; minimize distribution costs and transportation emissions and maximize product freshness.

An iterative heuristic is proposed to solve the BDIDP. It is a matheuristic that relaxes the integer variables before gradually imposing integer restrictions and fixing the integer values iteratively. The heuristic provides a realistic solution to a real-life instance of the BDIDP in a reasonable time. For the complete weekly instance, the matheuristic obtains a drastic reduction in relative gap compared to the exact solver. It is proven that the heuristic finds a solution that is reasonably close to the optimal solution. The heuristic is shown to obtain realistic solutions to an instance with multiple products, producers, and distribution centers. The work may serve as a basis for further research on the distribution of perishable products with multiple considerations.

The iterative heuristic is applied to the BDIDP in order to gain managerial insights relevant to Bama’s decision-making. These decisions involve introducing an additional intermediate facility into the supply chain, adding flexibility in delivery times, and collecting products at fewer producers. It is shown that increasing the time window on delivery and clustering producers both reduce the distribution costs and transportation emissions while introducing an additional intermediate facility does not provide substantial savings. None of the supply chain adjustments are shown to significantly impact overall product freshness. However, it is shown that distribution through the main terminal leads to a lower freshness value.