Metode za rješavanje problema naručivanja vožnji

diplomski rad

• Naslov (engleski): Methods for solving the dial-a-ride problem
• Autor: Stjepan Zelić
• Mentor: Marko Đurasević (mentor)
• Član povjerenstva: Marko Đurasević (predsjednik povjerenstva)
• Član povjerenstva: Jan Šnajder (član povjerenstva)
• Član povjerenstva: Domagoj Jakobović (č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: 2021-07-02, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Problem raspoređivanja vozila s vremenskim prozorima (DARP) je važan logistički NP-težak problem koji je začet kao verzija Problema usmjeravanja vozila (VRP), koji je pak podvrsta vrlo poznatog računalnog problema, Problema trgovačkog putnika (TSP). U ovom radu istražuju se stohastične metode optimizacije DARP-a, specifično genetski algoritmi. Genetski algoritmi iz obitelji Evolucijskih algoritama su se kroz nedavnu povijest pokazali kao važan alat moderne računarne znanosti u optimizaciji teških problema. Inspirirani prirodnom selekcijom, na razne načine imitiraju mehanizme preživljavanja najbolje prilagođenih jedinki jedne vrste, i odumiranja onih manje prilagođenih. U ovom radu primijenile su se neke generalne metode genetskih algoritama, ali su se razvile i nove metode specifične ovom problemu kako bi se dodatno proučio i unaprijedio proces optimizacije. Iskušane su različite verzije genetskih algoritama, te su se usporedili i komentirali dobiveni rezultati. Istražene su prednosti i mane ovakve optimizacije, te su postignuti rezultati uspoređeni s postojećim rezultatima drugih metoda. Implementirane su i jednostavne heuristike za optimizaciju, te su uspoređene s radom genetskih algoritama. Komentirana su i područja za poboljšanje metoda korištenih u ovom radu, kao i smjernice za budućnost.

Sažetak (engleski)

Dial-a-ride problem (DARP) is an important logistic NP-hard problem that was concieved as a version of the Vehicle Routing Problem (VRP), which is a subtype of a famous computer science problem, the Traveling Salesman Problem (TSP). In this thesis we explore stohastic methods for optimizing DARP, specifically the Genetic Algorithms. Genetic Algorithms, from the family of Evolutionary Algorithms, have in recent history proved themselves an important tool in modern computer science in optimizing hard problems. Inspired by natural selection, they imitate survival mechanisms of best adjusted individuals of a species in various ways, and also the mechanisms that deny less adjusted individuals reproduction and survival. Some general methods were used in genetic algorithms were applied in this thesis, but also some new methods specific to this problem were developed in order to additionaly explore and improve upon the optimization process. Various versions of genetic algorithms were tried, and the results were compared to the existing results of other methods. Also, simple heuristic methods were implemented, tested, and compared to the performance of genetic algorithms. Areas to improve this implementation were discussed, as well as points for the future.

• Ključne riječi: Problem naručivanja vozila; DARP; Genetski algoritmi; Optimizacija
• Ključne riječi (engleski): Dial a ride problem; Genetic Algorithms; Optimization; DARP
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:891065
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-15 11:28:43