Experimental comparison of hill climbing variants on CVRP

Abstract

Ruteoptimalisering forekommer overalt i samfunnet. Fra postleveringer til fabrikkering av kretskort spiller det å finne ruter som minimerer et eller annet kriterie en sentral rolle i et mangfold av industrier. Denne oppgaven handler om å utforske et konkret slik optimaliseringsproblem, nemlig Vehicle Routing Problem. Å beregne den optimale løsningen på et slikt problem er NP-hardt, som vil si at i større tilfeller vil det kreve ekstreme mengder datakraft å beregne den beste løsningen. Dette er ikke praktisk i en rekke anvendelser som raskt må løse mange slike problemer. Det er derfor vanlig å bruke heuristikker som tilnærmer løsningen. Noe av utfordringen med det er at effekten av heuristikkene varierer fra problem til problem.

Gjennom oppgaven ble et system laget som kunne håndtere en flåte av varebiler og de ulike ordrene de skulle hente, i tillegg til effektiv ruteoptimalisering som utnyttet den tilgjengelige bilparken. I oppgaven ble et eksperiment gjennomført der flere kjente algoritmer ble tilpasset til å fungere for det konkrete brukstilfellet i oppgaven. Overordnet sett fungerte alle algoritmene ved å hurtig fremstille en midlertidig løsning, deretter gradvis forbedre den gjennom små justeringer. Når dette implementeres i form av et lokalsøk er det kjent som hill climbing.

Dokumentet introduserer problemet først, deretter legger den legger det teoretiske grunnlaget for begrepene som er brukt og problemet som undersøkes. Metodene for både utviklingen av produktet og de vitenskapelige eksperimentene blir forklart før resultatene. De utførte eksperimentene blir så tolket for å svare på problemstillingen, som handler om sammenligning av forskjellige ruteoptimaliserings-algoritmer som bygger på teknikken hill climbing. Eksperimentene testet kjøretiden til de ulike algoritmer og kvaliteten på rutene som ble generert. Den ingeniørfaglige tilnærmingen til prosjektet og utviklingsprosessen bak produktet som bruker algoritmene er også dokumentert. Etter resultatene diskuterer et kapittel hvordan man tolker resultatene og hva dataen indikerer. Oppgaven avsluttes med noen innskudd til videre arbeid, både for produktet som er utviklet og ruteoptimaliseringen.

Eksperimentene indikerte at gruppens implementasjon av Adaptive Iterated Local Search skalerte verre enn vanlig hill climbing og simulated annealing, men lagde jevnlig bedre ruter. Forskjellen i skalerbarhet blir betydelig når omfanget av ruten er stort nok. Dette begrenser mengden anvendelser av algoritmen.

Routing problems in its different forms are ubiquitous in society. From postman deliveries to computer chip manufacturing, finding paths that minimize some criteria play a central role in many different industries. This thesis involves exploring such a concrete optimization problem, namely the vehicle routing problem. Determining an optimal solution to this problem is NP-hard, meaning that computing an optimal route in complex cases requires an extreme amount of computing power. This is not practical for applications that should quickly and reliably deliver solutions to these problems. It is therefore common to use heuristics that approximate the solution. The challenge with this is that the performance of different heuristics are situational and specific to the problems.

This thesis saw the creation of a system that could handle truck fleets and orders to be picked up, in addition to efficient routing for picking up the orders utilizing the available fleet. Within the thesis, experiments were conducted to test how certain known algorithms would perform when adjusted to work on a specific use case of the vehicle routing problem. Very broadly the algorithms tested all work by quickly producing a placeholder solution and gradually improving it in small increments, when done in a certain way it is known as hill climbing.

This document introduces the problem first, then lays the theoretical foundation of the terms used and the problem to be studied. Subsequently, the method of both development and the scientific experiments is described before the results are presented. The conducted experiments will answer the thesis question, which revolves around comparing different route-optimizing algorithms that build on the principle of hill climbing. The experiment tested the run time of different algorithms and the quality of the routes produced.The engineering professional approach and the development process of the product utilizing the algorithms are also documented. After the results, a chapter will discuss how to interpret the results and what the data indicates. The thesis is concluded with some pointers to further work for both the product developed and to route optimization will be left for the reader.

The experiments indicated that the teams implementation of Adaptive Iterated Local Search scaled worse than normal hill climbing and simulated annealing, but reliably provided better routes. The difference in scalability is significant as the sheer size of the route grows large limiting certain applications using this algorithm.