Neke inačice problema usmjeravanja vozila

diplomski rad

• Naslov (engleski): Some variants of the vehicle routing problem
• Autor: Lovro Nekić
• Mentor: Marko Erceg (mentor)
• Član povjerenstva: Marko Erceg (predsjednik povjerenstva)
• Član povjerenstva: Marko Vrdoljak (član povjerenstva)
• Član povjerenstva: Tomislav Pejković (član povjerenstva)
• Član povjerenstva: Ilja Gogić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2024-07-18, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu smo prikazali problem usmjeravanja vozila, kao poopćenje problema trgovačkog putnika. Zapis problema trgovačkog putnika kao problem traženja Hamiltonovog ciklusa najmanje težine smo sveli na problem optimizacije, jer je pronalaženje minimalnog Hamiltonovog ciklusa NP-težak problem. Optimizacijski problem trgovačkog putnika nam je bila motivacija zapisa problema usmjeravanja vozila u terminima minimizacijske zadaće. Dali smo pregled i opis problema iz općenite klase problema usmjeravanja vozila, fokusirajući se na probleme s vremenskim ograničenjima, probleme utovara-istovara, te periodičnih problema. Implementaciju optimizacijske formulacije problema usmjeravanja vozila smo izvršili u programskom jeziku Python, gdje smo uspjeli implementirali homogeni, heterogeni i problem s vremenskim ograničenjima na skupu podataka od 30 gradova.

Sažetak (engleski)

In this paper we have given an overview of the vehicle routing problem (VRP), a generalization of the travelling salesman problem (TSP). We have shown that TSP as a problem of a minimal Hamiltonian cycle can be written as an optimization problem, since the finding of a minimal Hamiltionian cycle is a NP-hard problem. TSP as an optimization problem also motivated us to write VRP as an optimization problem. We have given an overview of the generalized class of vehicle routing problems, of which we have focused on VRP with time windows, VRP with pickup-delivery, and periodic VRP. The implementation of the VRP as an optimization problem was achieved via Python programming language, where we have managed to implement homogeneous VRP, heterogeneous VRP and VRP with time windows, with a dataset of 30 cities.

• Ključne riječi: problem trgovačkog putnika; Hamiltonov ciklus; programski jezik Python
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:493921
• Studijski program: Naziv: Primijenjena matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: sveučilišni magistar matematike (univ. mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2024-07-24 12:31:15