Visualization and Comparison of Randomized Search Heuristics for Dynamic Traveling Salesperson Problems | Daniel-Cristian Loghin
| Abstract | The present thesis deals with implementing, analyzing and comparing randomized search heuristics for the traveling salesperson problem. Together with it, a software application was built, that implements ve choices of randomized search heuristics (Genetic Algorithm, (1+1) Evolutionary Algorithm, Randomized Local Search, Simulated Annealing and Min-Max Ant System) and the various implementation choices are discussed throughout the report.
The main goal of this Master Project is implementing and analyzing a system that allows the five algorithms to run in a dynamic environment. Four types of dynamic changes are implemented: interchanging the positions of two cities on the input map, having congested roads that get unusable from time to time, deleting and adding of cities. All these changes occur without restarting the algorithms, and the application's results on various tests are discussed in the latter stages of the report. | Type | Master's thesis [Academic thesis] | Year | 2013 | Publisher | Technical University of Denmark, Department of Applied Mathematics and Computer Science / DTU Co | Address | Matematiktorvet, Building 303B, DK-2800 Kgs. Lyngby, Denmark, compute@compute.dtu.dk | Series | M.Sc.-2013-99 | Note | DTU supervisor: Carsten Witt, cawi@dtu.dk, DTU Compute | Electronic version(s) | [pdf] | Publication link | http://www.compute.dtu.dk/English.aspx | BibTeX data | [bibtex] | IMM Group(s) | Computer Science & Engineering |
|