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

master's thesis

• Title (english): Methods for solving the dial-a-ride problem
• Author: Stjepan Zelić
• Mentor: Marko Đurasević (mentor)
• Committee member: Marko Đurasević (predsjednik povjerenstva)
• Committee member: Jan Šnajder (član povjerenstva)
• Committee member: Domagoj Jakobović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-07-02, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: Problem naručivanja vozila; DARP; Genetski algoritmi; Optimizacija
• Keywords (english): Dial a ride problem; Genetic Algorithms; Optimization; DARP
• Language: croatian
• URN:NBN: urn:nbn:hr:168:891065
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-15 11:28:43