Solution to the travelling salesman problem with space-filling curves.

Examensarbete för kandidatexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/158566
Download file(s):
File Description SizeFormat 
158566.pdfFulltext922.54 kBAdobe PDFView/Open
Type: Examensarbete för kandidatexamen
Bachelor Thesis
Title: Solution to the travelling salesman problem with space-filling curves.
Authors: Hall, Simon
Henriksson, Andreas
Khalafi, Hakim
Abstract: I denna rapport har vi utforskat olika metoder som löser handelsresandeproblemet med hjälp av rumsfyllande kurvor. Vi har utgått från en klassisk algoritm av Bartholdi och Platzman och förbättrat den med avseende på lösningslängd med två egna algoritmer. Vi har under arbetets gång utvecklat programvara som använder dessa algoritmer. Vi har undersökt körningstid, lösningslängd och stabilitet för de olika algoritmerna och analyserat resultaten. Rapporten innehåller även en inledande teoretisk beskrivning av planfyllande kurvor och NP-komplexitet.
Keywords: Grundläggande vetenskaper;Annan matematik;Basic Sciences;Other Mathematics
Issue Date: 2012
Publisher: Chalmers tekniska högskola / Institutionen för matematiska vetenskaper
Chalmers University of Technology / Department of Mathematical Sciences
URI: https://hdl.handle.net/20.500.12380/158566
Collection:Examensarbeten för kandidatexamen // Bachelor Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.