Algoritmer och simulation för en dynamiskt uppdaterbar ruttplanerare

Abstract

Bzzt AB is a logistics company that focuses on optimised routes for deliveries. A problem that occurs when building software to optimise routes is the traveling salesman problem (TSP). TSP can be applied to many areas including the vehicle routing problem (VRP). Both VRP and TSP are two well documented areas of research, and there are multiple variations of the problems. A study of industrystandard solutions was conducted before moving on to development. This report presents and compares three different solutions to a modified version of TSP, a bruteforce solution, an euclidean approximation and a greedy approximation. Based on the results derived from testing the algorithms onto four different scenarios the conclusion is that the euclidean approximation consistently calculates suitable routes based on the criterias stated. To conduct this comparison a simulation- and testing environment has also been developed. This software is engineered to represent a real world scenario by generating events and simulating the passing of time. The simulation- and testing software also gathers the information from the calculations and condenses the data into a readable format. New algorithms can be tested through the simulation-software to analyse the efficiency based on stated criteria.