Designing Delivery Districts and Tactical Routes for Parcel Home Delivery Service
Master thesis
Permanent lenke
https://hdl.handle.net/11250/3060793Utgivelsesdato
2022Metadata
Vis full innførselSamlinger
Sammendrag
Ruteinndelingsproblemet (the Route Partitioning Problem - RPP) i denne oppgaven er problemet med å lage taktiske kjøreruter for hjemlevering av pakker. Problemet innebærer å først dele opp et geografisk område i mindre områder og deretter bestemme rekkefølgen disse områdene skal besøkes i. En sentral utfordring med RPP er uforutsigbare pakkevolumer og kundelokasjoner. Målet med denne oppgaven er å finne ut om det å benytte et sett med taktiske ruter, som skal opereres uendret over en lengre tidsperiode, kan være er et attraktivt alternativ til det å sette sammen helt nye ruter hver dag.
I denne oppgaven utvikler vi en nyskapende to-stegs løsningsmetode for RPP. Det første steget løser et strategisk distriktsproblem ved hjelp av en lokasjon-allokering heuristisk algoritme. Algoritmen dekomponerer distriktsproblemet i to faser, en lokaliserings- og en allokeringsfase, hvor allokeringsfasen løses ved hjelp av Polygoninndelingsproblemet (the Polygon Partitioning Problem - PPP) implementert som en heltallsprogrammeringsmodell (IP). En løsning fra steg en er en inndeling av postnummer områder i ikke-overlappende polygoner som er kompakte, isolerte og unngår geografiske hindringer i veinettet. For hvert polygon beregnes en forventet leveringstid for tre ulike etterspørselsnivåer ved hjelp av Monte Carlo-simuleringer. I steg to implementeres en IP-modell for å løse det taktisk Polygonruteproblemet (the Polygon Routing Problem - PRP). En løsning fra steg to er en taktisk ruteplan, der hver rute er en sekvens av polygoner, som minimerer den totale forventede leveringstiden.
Løsningene til vår to-stegs løsningsmetode er konstruert for tre ulike etterspørselsnivåer for Trondheim kommune i Norge, og er evaluert basert på et antall realiseringer av kunders etterspørsel. Ved bruk av Google sitt optimeringsverktøy (OR-Tools), vil den totale leveringstiden av daglige ruter basert på våre taktiske ruter evalueres og sammenlignes med leveringstiden til et deterministisk Bilrutingsproblem (Vehicle Routing Problem - VRP). Et interessant aspekt er hvordan ulike inndelinger av det geografiske området påvirker leveringstid. Våre resultater indikerer at bruk av en mer granulær polygoninndeling i gjennomsnitt fører til de laveste leveringstidene. De taktiske rutene generert med den mest granulære inndelingen, fører til en gjennomsnittlig leveringstid som kun er 2.3% høyere enn de deterministiske VRP løsningene på tvers av etterspørselsnivåer. Disse resultatene er motiverende ettersom kostnadsbesparelsene i annen logistikk ved å bruke taktiske ruter antas å være betydelig større.
Oss kjent er denne oppgaven det første forsøket på å kombinere strategisk distriktsinndeling og taktisk ruting i en to-stegs løsningsmetode. Vår beregningsstudie indikerer at taktiske ruter kan være et attraktivt alternativ til det å lage helt nye ruter hver dag. Likevel bør denne oppgaven kun anses som en innledene studie, og videre analyser av kostnadsbesbarelsen ved å ta i bruk taktiske ruter er nødvendig før disse kan anvendes i praksis.
Denne oppgaven er utført i samarbeid med Posten Norge AS, et norsk post- og logistikkonsern. The Route Partitioning Problem (RPP) is the problem of generating tactical routes for home delivery of parcels by partitioning a geographical area into smaller areas and sequencing these. The main difficulty in designing good solutions to the RPP problem is the need to address stochastic parcel volumes and customer locations. This thesis aims to evaluate whether designing a set of tactical routes to be operated unchanged over a given period of time is a viable alternative to constructing a set of routes every day based on the particular instance of that day.
To solve the RPP, this thesis develops a novel two-stage solution approach. The first stage solves a strategic districting problem by using a location-allocation heuristic algorithm. The algorithm decomposes the districting problem into two phases, a location and an allocation phase, where the allocation phase is solved using the Polygon Partitioning Problem (PPP) implemented as an Integer Programming (IP) model. A solution from the first stage strategic districting problem is a partitioning of a set of postal code areas into non-overlapping polygons that are compact, isolated and avoids geographical barriers in the road network. For each polygon, an expected delivery time within the polygon is calculated for three different demand levels using Monte Carlo simulations. In the second stage, an IP model is implemented to solve the tactical Polygon Routing Problem (PRP). A solution is a tactical routing plan, where each route is a sequence of polygons, which minimizes the total expected delivery time.
Solutions of our two-stage approach are constructed for three different demand levels, identified within Trondheim municipality in Norway, and evaluated based on realizations of the customers’ demands. Using Google’s Operations Research Tools (OR-tools), the total delivery time of daily routes derived from tactical routes produced by our method is evaluated and compared to the delivery time of a deterministic Vehicle Routing Problem (VRP) solution. Interesting is the impact of different partitionings of the geographical area. Results indicate that using a more granular polygon partitioning when constructing tactical routes generates the lowest average delivery times. Moreover, the tactical routes generated with the most granular partitioning have merely a 2.3% higher average delivery time than the deterministic VRP solutions across all demand levels. The results are encouraging as the logistic cost saving of applying tactical routes is believed to be significantly larger.
To our knowledge, this thesis constitutes the first known attempt of combining strategic districting and tactical routing in a two-stage approach. The computational study has proven that tactical routing does provide a viable alternative to optimizing routes each day from scratch. Nevertheless, our efforts should be construed as an initial investigation, and further analysis of the cost-savings of applying tactical routes needs to be evaluated before being implemented in practice.
This thesis is carried out in collaboration with Posten Norge AS, a Norwegian postal and logistics group.