Travelling Salesman Problem

Martin List Syberg, Frederik Lyngsøe, Ebubekir Kayhan & Sebastian Nørager

Studenteropgave: Basisprojekt

Abstrakt

The pollution from the transport sector is one of the biggest culprits in contaminating the
earth. This paper will describe and explain “Graph Theory” and “Travelling Salesman
Problem” and how these could be used to simplify delivery routes. This would minimize the
pollution from the given car routes. To examine the Travelling Salesman Problem the team
created a program that constructs a graph and hereafter runs two algorithms on the given
graph. The program will show the difference in distance after the algorithms has created a
new route on the graph. These two different values will be used to discuss optimization of
delivery routes, and how it would decrease the pollution from the given route. After
examining the results, it’s possible to conclude that using algorithms would greatly reduce the
length of the given route and thereby reduce the CO2 and NOx emission.

UddannelserBasis - Naturvidenskabelig Bacheloruddannelse, (Bachelor uddannelse) Basis
SprogDansk
Udgivelsesdato17 dec. 2019
Antal sider54
VejledereLine Reinhardt

Emneord

  • TSP
  • DATALOGI
  • OPTIMERING
  • 2-OPT
  • BRUTE FORCE
  • MILJØ