hrvatski

Problem usmjeravanja vozila i metaheuristika tabu pretraživanja

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.

problem usmjeravanja vozila ; tabu pretraživanje ; metaheuristike

nije evidentirano