Heuristic Methods for a Periodic Multi-Trip Vehicle Routing Problem with Time Windows in the Food Distribution Industry

Abstract

Det periodiske multi-trip vehicle routing problemet med tidsvinduer (PMTVRPTW), inkompatible varer, og en heterogen kjøretøysflåte oppstår når ASKO, det ledende selskapet for dagligvaredistribusjon i Norge, planlegger ukentlige kjøreruter. I forkant av hver planleggingsperiode bestiller kunder en mengde forskjellige varer. Hver varemengde må enten leveres i sin helhet på en leveranse, eller deles i flere leverenser på flere dager. En løsning på problemet tildeler kunder en rekkefølge i en rundtur som gjennomføres av et kjøretøy, for hver dag i planleggingshorisonten. I tillegg allokeres varer til hver rundtur. I dag optimerer ASKO ruteplanlegging og vareallokering sekvensielt. I denne oppgaven forsøkes det å optimere rutene og vareallokeringen simultant. Objektivet er å minimere kostnader ved bruk av kjøretøy, bestående av kjørekostnader og en fast kostnad for bruk, samtidig som man minimerer antall overtidstimer på varelageret. Denne kombinasjonen av problemutvidelser er sjelden i litteraturen, og ingen løsningsmetoder er foreslått.

En matematisk modell for PMTVRPTW er presentert. Fordi eksakte metoder ikke er i stand til å løse problemet for reelle kundestørrelser, er fire forskjellige heurisitiske metoder foreslått. Først presenterer vi en hybrid genetisk algoritme (HGA), inspirert av tidligere arbeid fra blant annet Vidal et al. (2012) og Cattaruzza et al. (2016a). Ved å dekomponerer problemet på periodenivå, kan hver enkelt periode løses separat med en multiperiodisk HGA (MPHGA). Videre presenterer vi en sverm-inspirert multiperiodisk artificial bee colony (MPABC) algoritme, som også benytter seg av en periodisk dekomponering. Til slutt blir en kombinatorisk kolonnegenereringsmodell (CJGM) presentert, som kombinerer deler av løsninger funnet av flere MPHGAer og MPABCer i en eksakt løsningsmetode.

Et beregningsstudie er gjennomført for å evaluere de foreslåtte heurestikkene. Det har blitt generert testinstanser basert på reel data fra ASKO. Alle heurestikkene viser lite avvik fra objektverdiene funnet av en eksakt modell på instanser med få kunder. CJGMen rapporterer beste resultater for alle instanser, også de av reelle størrelse (med opptil 115 kunder). I tillegg er CJGMen den mest stabile løsningsmetoden, med en lav variasjonskoeffisient. Effekten av å løse en eksakt metode ved å kombinere løsninger funnet av heurestikker er analysert, og det viser seg at den klarer å forbedre løsninger for alle instansstørrelser, hovedsakelig basert på løsninger funnet fra MPHGAen. For kundestørrelser opp til 50 kunder klarer MPABCen å finne løsninger av høy kvalitet, men lider av en ineffektiv lokalsøksoperator for større instanser. HGAen avviker mye fra løsningene funnet av CJGMen for alle kundestørrelser. Generelt viser det seg at en heuristisk fremgangsmåte som anvender en periodisk dekomponering i kombinasjon med en eksakt løsningsmetode gir kvalitetsløsninger innen rimelig kjøretid, og skalerer bedre til større instanser.

The periodic multi-trip vehicle routing problem with time windows (PMTVRPTW), in- compatible commodities, and a heterogeneous fleet arise when ASKO, a leading food- service distributor in Norway, schedule their weekly operations. In advance of a planning period, customers request a set of different commodities. Commodities are either dividable across planning periods, or restricted to be delivered in one single period. The objective is to minimize costs related to vehicle usage, i.e. driving time and fixed usage costs, while reducing the amount of overtime incurred at the warehouse. This particular combination of problem extensions is poorly covered in literature, and no solution methods are pro- posed to solve this VRP class. A problem-solution both assigns sequences of customers to vehicles in each planning period, and allocates commodities to each vehicle. Today, ASKO schedules routes and allocates commodities sequentially. This thesis shows that a simultaneous optimization approach can provide decision support for real-size instances within a practical amount of time.

A mathematical model of the PMTVRPTW is presented. As exact methods are unable to solve the problem for real-size instances, four different heuristic methods are devel- oped. Inspired by the work in recent literature (e.g Vidal et al., 2012, Cattaruzza et al., 2016a), we first propose a hybrid genetic algorithm (HGA) for the PMTVRTW. The multi- periodic HGA (MPHGA) arises when the HGA is decomposed to solve the problem for each planning period separately. Third, we propose a swarm-inspired multi-periodic arti- ficial bee colony (MPABC) algorithm which adopts the decomposition structure. Finally, the combinatorial journey-generating model (CJGM) is presented, which is a matheuristic combining partial solutions generated by the MPABC and MPHGA, with an exact method.

A computational study is conducted to evaluate and compare the proposed heuristics. Test instances are generated from real-life data provided by ASKO. All heuristics show mi- nor deviations from the objectives obtained by an exact method on small-sized instances. Results on real-size instances (i.e. up to 115 customers) show that the CJGM is the best performing method in terms of ability to find quality solutions for all instance sizes, with a low coefficient of variation. The MPHGA also scales well to real-size instances, but has on average a larger coefficient of variation than the CJGM. The MPABC suffers from an inefficient local search operator for larger instances. The HGA reports a large average de- viation from solutions obtained by the CJGM across all instance sizes. The contribution of incorporating an exact method which combines partial solutions obtained by the heuristic methods in the CJGM is analyzed, and shown to improve solution quality on all customer sizes, particularly for large instances. Thus, the CJGM is expected to serve as decision support in dynamic planning procedures, when solutions for real-size instances must be obtained rapidly without the need for complex calibration procedures.