engleski

Traveling Salesman Problem Solving by Classic and Advanced Algorithms

Problem trgovačkog putnika je vrlo poznat i proučavan problem kombinatorne optimizacije. Od početka njegovog proučavanja do danas, za njegovo rješavanje primjenjivani su mnogi algoritmi, s različitim uspjehom. U ovom diplomskom radu su predstavljena četiri popularna približna algoritma ili heuristike koji se mogu koristiti za rješavanje problema trgovačkog putnika. Algoritam najbližeg susjeda i 2-opt algoritam mogu se svrstati u klasične algoritme, dok se genetski algoritam i algoritam elitističkog mravljeg sustava, kao i njihove inačice s ugrađenom lokalnom pretragom, mogu svrstati u napredne algoritme ili metaheuristike. Prikazani su načini rada navedenih algoritama, te programsko rješenje u koje su ugrađeni, razvijeno u svrhu njihove analize. Analizom su prikazane dobre i loše strane algoritama, odnosno njihova učinkovitost pri rješavanju problema trgovačkog putnika na temelju dobivenih rješenja i vremena izvođenja. Uz, u radu provedena unaprjeđenja nekih od navedenih algoritama, dane su smjernice za moguća daljnja unaprjeđenja u konkretnom, ali i u općem slučaju.

2-opt algorithm; elitist ant system algorithm; nearest neighbor algorithm; genetic algorithm; traveling salesman problem

nije evidentirano