Uporaba simboličke regresije za rješavanje problema usmjeravanja vozila

master's thesis

• Title (english): Solving vehicle routing problems with symbolic regression
• Author: Luka Kraljević
• Mentor: Domagoj Jakobović (mentor)
• Committee member: Domagoj Jakobović (predsjednik povjerenstva)
• Committee member: Leonardo Jelenković (član povjerenstva)
• Committee member: Ante Đerek (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2019-07-12, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

U ovom radu glavno je pitanje kako riješiti statičku i dinamičku varijantu problema koristeći metode simboličke regresije. Opisan je temeljni sadržaj problema usmjeravanja vozila kao i njegove varijante koje su se rješavale u radu, a to su CVRP (kaacitivni problem usmjeravanja vozila), VRPTW (problem usmjeravanja vozila s vremenskim prozorima) te VRPPD (problem usmjeravanja vozila s prikupljanjima i dostavama). Potom je napravljen detaljan uvid u neke od najpoznatijih radova koji su doprinijeli riješavanju obiju varijanti problema, a zatim su opisane metode koje se koriste u ovom radu, a to su genetičko programiranje i analitičke programiranje. Slijede detalji implementacije sustava za rješavanje VRP poput korištenih instanci, pseudokoda algoritama te korištenja razvijenog sustava. Na kraju su prikazani rezultati za statičke i dinamičke varijante te su metode simboličke regresije uspoređene s jednostavnim heuristikama.

Abstract (english)

In this paper, the main question is how to solve the static and dynamic variants of the problem using symbolic regression methods. The basic contents of the vehicle routing problem as well as its variants that have been dealt with in the work are described, namely CVRP (Capacitated Vehicle Routing Problem), VRPTW (Vehicle Routing Problem with Time Windows) and VRPPD (Vehicle Routing Problem with Pickup and Delivery). Then a detailed insight into some of the most famous papers contributed to the solution of both variants of the problem and then the methods used in this paper were described, namely genetic programming and analytical programming. Following are the details of deploying VRP solution systems such as instances used, pseudocode of used algorithms, and the usage of developed system. Finally, the results for static and dynamic variants are presented, and the methods of symbolic regression are compared with simple heuristics.

• Keywords: VRP; simbolička regresija; genetičko programiranje; analitičko programiranje; hiperheuristike; dinamička simulacija
• Keywords (english): VRP; symbolic regression; genetic programming; analytical programming; hyperheuristics; dynamic simulation
• Language: croatian
• URN:NBN: urn:nbn:hr:168:914255
• 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: 2020-01-07 19:21:54