Solving Multi-Constraint Large-Scale Vehicle Routing Problems

Abstract

Ruteproblemet, kjent som "Vehicle routing problem (VRP)" , har vært forsket på i over seksti år på grunn av dets teoretiske kompleksitet og betydning i mange bruksområder. Mange applikasjoner i det virkelige liv har et økt behov for å levere til tusenvis av kunder, mens de samtidig tar flere begrensninger i betraktning. I tillegg er applikasjoner i det virkelige liv ofte avhengig av å motta løsningene fra problemet raskt, noe som betyr at problemet må løses på kort tid, definert som 30 minutter i denne oppgaven. Likevel har få studier hittil fokusert på å løse instanser av stor skala med flere begrensninger, innenfor denne tidsgrensen. Denne oppgaven undersøker hvordan en "state-of-the-art" hybrid genetisk algoritme dermed kan tilpasses for å mer effektivt løse insanser av stor skala med flere begrensninger og hvordan dette vil påvirke ytelsen.

En ny teknikk for å unngå overflødige beregninger i det lokale søket blir introdusert, som fokuserer på å gjenbruke informasjon fra forgjenger-løsninger med like egenskaper. Resultatene viser at denne teknikken reduserer tiden som brukes i det lokale søket betydelig. I tillegg presenteres en mer effektiv måte å initialisere populasjonen på ved å bruke såkalt "k-means clustering" for å splitte opp problemet.

The vehicle routing problem (VRP) has been subject of research over sixty years due to its theoretical complexity and importance in many application areas. Many real-life applications have an increased need to deliver to thousands of customers while taking multiple constraints into account. In addition, real-life applications are often dependent on retrieving the results of the VRP quickly, which means that the problem must be solved in a short amount of time, defined as 30 minutes in this thesis. Yet, few studies thus far have focused on solving large-scale instances with multiple constraints within this time limit. This thesis investigates how a state-of-the-art hybrid genetic algorithm thus can be adapted to more efficiently solve multi-constraint large-scale instances and how this will affect its performance.

A new technique to avoid redundant computations in the local search is introduced, which focuses on reusing information from predecessor solutions with similar features. Results shows that this technique reduces the time used in the local search significantly. In addition, a more efficient technique to initialize the population by using k-means clustering to decompose the problem is presented.