Heuristically Solving Large-Scale Location Routing Problems with Stochastic Customer Presence for Online Grocery Delivery
Master thesis
Permanent lenke
https://hdl.handle.net/11250/3111989Utgivelsesdato
2023Metadata
Vis full innførselSamlinger
Sammendrag
Denne oppgaven presenterer en studie av heuristiske optimeringsmetoder for å løse et stort og komplekst "location-routing"-problem (LRP) med stokastisk kundetilstedeværelse, i samarbeid med det norske nettbaserte dagligvareselskapet Oda. For å levere matvarer og andre produkter til tusenvis av kunder, løser de daglig store "vehicle-routing"-problemer (VRP) med flere depoter, kapasitets- og varighetsbegrensninger, tidsvinduer og heterogene kjøretøy. Ved utvidelse til nye markeder må de først beslutte hvor depotene som kjøretøyene starter rutene sine fra skal lokaliseres, som er utfordrende med usikkerhet knyttet til hvilke kunder som vil bestille, også kalt kundetilstedeværelse. Vi modellerer et stokastisk, to-stegs LRP for å finne gode depotlokasjoner i slike situasjoner. I første steg besluttes depotlokasjonene, mens andre steg finner kostnaden til kjøretøysrutene for ulike realiseringer av kundetilstedeværelse. LRP av denne størrelsen og kompleksiteten med stokastisk kundetilstedeværelse er ikke forsket på tidligere. De foreslåtte løsningsmetodene består av en algoritme for å søke gjennom ulike depotlokasjoner, en scenariogenereringsmetode og en rutingalgoritme. Disse testes på realistiske probleminstanser med 20 mulige depotlokasjoner og tusenvis av kunder i Berlin.
Søket gjennom førstestegsløsningene gjøres med en "Greedy Randomized Adaptive Search Procedure" (GRASP), samt "Constructive Adaptive Tabu Search'' (CATS), som først finner et lovende antall åpne depoter og deretter utfører lokalsøk med et adaptivt nabolag. CATS presterer mest konsistent, men begge metodene finner løsninger i løpet av 12 timer med under 0.2% kostnadsavvik til den beste kjente løsningen. CATS finner løsninger med under 1% avvik etter bare 2 timer. Siden løsningsevalueringen er tidkrevende, er utvidelsene i CATS viktige for å finne gode løsninger fort nok. Stokastisiteten håndteres ved å generere scenarioer med ulikt antall kunder, som vektes etter sannsynligheten for lignende scenarioer basert på historiske etterspørselsfordelinger. "Out-of-sample"-tester viser at bruk av 16 scenarioer er nok for å oppnå stabilitet, spesielt når det kommer til å rangere løsningene riktig. Utregningen av rutekostnader er tredelt. Først tildeles kundene et depot, så grupperes lignende kunder sammen, før en "Hybrid Genetic Search"-løsningsmetode konstruerer rutene. Sammenlignet med løsninger fra Odas operasjonelle ruteplanlegger, viser denne metoden tilfredsstillende resultater ved å oppnå stabil rangering av løsninger selv om problemene løses 20 ganger raskere enn Odas ruteplanlegger.
Vi anvender CATS i en case-studie for å gi innsikt til Oda. Her finner vi at åpning av depoter først er lønnsomt når man har et gjennomsnitt på 3000 kunder per skift. Vi ser også at størrelsen på kjøretøysflåten og hvordan den er sammensatt er viktige faktorer når man skal vurdere lønnsomheten ved å åpne ulike depoter. This master's thesis studies heuristic optimization methods for solving a large and complex Location Routing Problem (LRP) with stochastic customer presence in collaboration with Oda, a Norwegian online grocery company. To deliver groceries to thousands of customers daily, Oda needs to solve a very large multi-depot capacitated Vehicle Routing Problem (VRP) with time windows, a heterogeneous fleet and tour duration constraints. When entering a new market with uncertainty related to which customers place an order, or customer presence, they must determine where the depots that vehicles drive from should be located. To find good depot locations in such situations, we model a two-stage stochastic LRP. The first stage considers locating depots, and the second stage handles routing from depots to customers for a realization of the customer presence. LRPs with stochastic customer presence of this size and complexity have not been researched before. We propose solution methods consisting of three parts: a depot location search algorithm, a scenario generation method, and a routing algorithm. These are tested on realistic problem instances with 20 possible depot locations and thousands of customers in Berlin.
For searching through first-stage solutions, a Greedy Randomized Adaptive Search Procedure (GRASP) and Constructive Adaptive Tabu Search (CATS), which first finds a promising number of open depots and then performs a local search with an adaptive neighborhood, are used. CATS performs more consistently, but both methods find solutions within 12 hours with cost gaps of less than 0.2% of the best known solutions. CATS achieves solutions within a 1% cost gap after only 2 hours. Since evaluating solutions is time-consuming, the extensions in CATS are necessary to find good solutions quickly. Stochasticity is handled by generating scenarios with different numbers of customers that are weighted from the likelihood of similar scenarios based on historical distributions of demand. Out-of-sample stability tests show that using 16 scenarios is sufficient to ensure stability, especially when it comes to ranking solutions correctly. The calculation of routing costs follows a three-phase approach. First, customers are assigned to depots, then similar customers are clustered, before a Hybrid Genetic Search solver creates routes. Compared to benchmarks from Oda's operational solver, this method demonstrates satisfactory results as it achieves a stable ranking of solutions solving the problems 20 times faster than Oda's solver.
In a case study, we use the CATS algorithm to gain insights for Oda. We find that opening depots is first profitable when exceeding an average of 3000 customers per shift, and that the fleet size and composition are important attributes in determining a depot's attractiveness.