Algoritmer och simulation för en dynamiskt uppdaterbar ruttplanerare
Typ
Examensarbete på kandidatnivå
Bachelor Thesis
Bachelor Thesis
Program
Publicerad
2022
Författare
JAKOBSSON, OSKAR
AXETORN, JONATAN
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Vehicle routing problem , Traveling salesman problem , logistics , algorithms , simulation , software