Reševanje problema trgovskega potnika s paralelnim simuliranim ohlajanjem

diplomsko delo

Matej Strašek (Author), Janez Brest (Mentor), Aleš Zamuda (Co-mentor)

Abstract

V diplomskem delu skušamo s paralelizacijo algoritma simuliranega ohlajanja izboljšati čas reševanja problema trgovskega potnika. S pomočjo vmesnika OpenMP implementiramo paralelizacije algoritmov sosednosti k-opt, simulirano ohlajanje in izboljšavo le-tega – sprejemljivo simulirano ohlajanje. Predstavimo algoritme in zberemo njihove rezultate za paralelizacijo zanke, paralelizacijo particij, paralelizacijo z različnim razponom in prilagodljivo paralelizacijo simuliranega ohlajanja. Prvi del predstavlja opis problema trgovskega potnika, vmesnika OpenMP, opis implementiranih algoritmov in njihovih paralelizacij. V zadnjem delu so predstavljeni rezultati na problemih trgovskega potnika iz knjižnice TSPLIB, njihova medsebojna primerjava ter možnosti za nadaljnje raziskave.

Keywords

problem trgovskega potnika;simulirano ohlajanje;paralelizacija simuliranega ohlajanja;

Data

Language:	Slovenian
Year of publishing:	2014
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	M. Strašek
UDC:	004.021:519.8(043.2)
COBISS:	19113238
Views:	1838
Downloads:	74
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Solving travelling salesman problem with parallel simulated annealing
Secondary abstract:	The diploma thesis focuses on improving the solving time for the travelling salesman problem, by parallelizing the simulated annealing algorithm. We implement parallelization of local k-opt algorithms, simulated annealing, and an improvement of this - the acceptance simulated annealing, by using OpenMP interface. We present algorithms and gather their results using the parallelization of the loops, parallelization of the partitions, parallelization with different range, and adaptable parallelization of simulated annealing. The first part covers the presentation of the travelling salesman problem, the OpenMP interface, and the description of the implemented algorithms and their parallelization. The last part features the results based on the travelling salesman problems from the TSPLIB library, their mutual comparison, and the possibilities for further research.
Secondary keywords:	traveling salesman problem;simulated annealing;simulated annealing parallelization;
URN:	URN:SI:UM:
Type (COBISS):	Bachelor thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Pages:	VI, 30 f.
ID:	9063593