This thesis consists of two parts: text and programming part. It is divided into seven chapters. Its main goal is to compare heuristics for dynamic traveling salesman problem in a few perspectives. The text part of this thesis theoretically describes heuristic methods and in the programming part are wake up to life via VBA in MS Excel. The results of computational experiments on these heuristic methods are presented in the last chapter. In the first part, the traveling salesman problem and its solution are being described. Characteristic of the modification in a form of dynamic traveling salesman problem follow. Next chapter presents the programming solution chosen heuristics. The final chapter presents experimental results obtain with programmed heuristics.

Ant Colony Optimization (ACO) algorithms have been successful in solving a wide variety of NPhard optimization problems. The Traveling Salesman Problem (TSP) has served as a benchmarking problem for many novel ACO algorithms. The slightly harder Dynamic Traveling Salesman Problem (DTSP) is more realistic in the sense that real-time changes happen in the graph belonging to a TSP instance. This thesis studied the original ACO algorithm: the Ant System, and how the amount of pheromone deposited by the ants within the algorithm affected the performance when solving both TSP and DTSP problems. Additionally, 2-opt local search was added to the algorithm, to see how it impacted the performance. We found that when the ants deposited a greater amount of pheromone, the performance for TSP increased, while the performance for DTSP decreased. We concluded that the Ant System in its original form is unsuitable for solving the DTSP. 2-opt local search improved the performance in all instances. / Ant Colony Optimization-algoritmer (ACO) har visat sig vara bra på att lösa många olika NP-svåra optimeringsproblem. För att mäta prestandan för nya ACO-algoritmer har i många fall Handelsresandeproblemet (eng. TSP) använts. Den dynamiska varianten av TSP (eng. DTSP), är ett något svårare problem då förändringar i grafen kan ske i realtid. Denna uppsats utredde hur olika mängder feromon som avges av myrorna inuti algoritmen Ant System, påverkade prestandan för både TSPoch DTSP-instanser. Utöver detta studerades hur den lokala sökningsheuristiken 2-opt påverkade prestandan. Resultaten visade att om myrorna tilläts släppa mer feromoner, ökade prestantan för TSP, men minskade för DTSP. Därav drog vi slutsatsen att algoritmen Ant System i sin ursprungliga form ej är lämplig för att lösa DTSP. Den lokala söknigsheuristiken 2-opt förbättrade prestandan i alla tester.