Naslov
Problem usmjeravanja vozila i metaheuristika tabu pretraživanja
(Vehicle Routing Problem and Taboo Search Metaheuristics)

Autori
Korenčić, Damir

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, diplomski rad

Fakultet
Prirodoslovno matematički fakultet - Matematički odjel

Mjesto
Zagreb

Datum
20.06

Godina
2008

Stranica
64

Mentor
Manger, Robert

Ključne riječi
problem usmjeravanja vozila ; tabu pretraživanje ; metaheuristike
(vehicle routing problem ; taboo search ; metaheuristics)

Sažetak
Ovaj rad daje osnovni pregled problema usmjeravanja vozila, uz detaljniji opis jedne osnovne varijante. Daje se kratak pregled algoritama grananja i ograničavanja te grananja i rezanja, a detaljnije se opisuju najbolje heurističke i metaheurističke metode rješavanja. Najviše pažnje posvećeno je metaheuristici tabu pretraživanja. Na kraju se opisuje autorova implementacija te metaheuris- tike, te se ocjenjuje njezina uspješnost. U prvom poglavlju se prvo opisuje općeniti problem usmjeravanja vozila i daje se definicija osnovnog CVRP problema i nekih složenijih varijanti. Slijedi kratak opis raznih pristupa rješavanju ; od formulacija pomoću linearnog programiranja te algoritama za egzaktno rješavanje do heuristika i metaheuristika. Govori se o metaheurističkom pristupu optimizaciji, te o metaheuristici tabu pretraživanja koja se pokazala vrlo uspješnom za mnoge probleme pa i za problem usmjeravanja vozila. U drugom poglavlju se detaljnije opisuju najvažnije i najučinkovitije heuristike, a u trećem poglavlju metaheuristike. Ocjenjuje se njihova (relativna) uspješnost, a za neke algoritme napisan je pseudokod. Dan je opis najbitnijih ideja svakog algoritma. U četvrtom poglavlju opisuje se moj vlastiti algoritam tabu pretraživanja za CVRP-K varijantu problema, kao i implementacija dvije heuristike za rješavanje istog problema. Dani su rezultati testiranja, a tabu algoritam usporeden je s većinom ostalih tabu algoritama opisanih u ovom radu.

Izvorni jezik
Hrvatski

Znanstvena područja
Računarstvo

POVEZANOST RADA