Primjena heurističkih algoritama u rješavanju problema usmjeravanja vozila s kapacitetnim ograničenjima

završni rad

• Naslov (engleski): Application of Heuristic Algorithms for Solving Capacitated Vehicle Routing Problem
• Autor: Andrija Samodol
• Mentor: Tomislav Burić (mentor)
• Član povjerenstva: Tomislav Burić (predsjednik povjerenstva)
• Član povjerenstva: Mervan Pašić (član povjerenstva)
• Član povjerenstva: Lenka Mihoković (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2020-07-06, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Nastojanje da se bilo kakav nepotreban trošak prijevoza robe do klijenata smanji, potaknulo je razvoj mnogih metoda za rješavanje ovog optimizacijskog problema, nazvanog problem usmjeravanja vozila (VRP). Postoju brojne inačice VRP-a ovisno o zadanim ograničenjima, predmet ovog rada je problem usmjeravanja vozila s kapacitetnim ograničenjima (CVRP). Heurističke metode, koje iako ne pronalaze uvijek optimalno rješenje, se često primjenjuju i danas kod rješavanja većih problema (s 100 ili više klijenata) zbog puno veće brzine pronalaska rješenja u odnosu na egzaktne metode. Programskom implementacijom heurističkih metoda, Clarke & Wright-ova i Sweep algoritma, uspoređeni su rezultati u ovisnosti o broju klijenata i klijentskim potražnjama te predložena poboljšanja.

Sažetak (engleski)

The effort to reduce any unnecessary cost of transporting goods to customers has prompted the development of many methods for solving this optimization problem, called vehicle routing problem (VRP). There are numerous variants of VRP depending on the given constraints, the subject of this paper is the Capacitated vehicle routing problem (CVRP). Heuristic methods, although they do not always find the optimal solution, are often used today in solving larger problems (with 100 or more clients) due to the much higher speed of finding solutions compared to exact methods. The software application of heuristic methods, Clarke & Wright’s and Sweep algorithm, compares the results depending on the number of clients and their demands, improvements are proposed based on the results.

• Ključne riječi: problem usmjeravanja vozila s kapacitetnim ograničenjima; CVRP; problem trgovačkog putnika; TSP; heurističke metode/algoritmi; Clarke & Wright-ov algoritam ušteda; Sweep algoritam; algoritam najbližeg susjeda
• Ključne riječi (engleski): Capacitated Vehicle Routing Problem; CVRP; Traveling Salesman Problem; TSP; heuristic methods/algorithms; Clarke & Wright's savings algorithm; Sweep algorithm; nearest neighbour algorithm
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:666864
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 13:45:34