Neke inačice problema usmjeravanja vozila

master's thesis

• Title (english): Some variants of the vehicle routing problem
• Author: Lovro Nekić
• Mentor: Marko Erceg (mentor)
• Committee member: Marko Erceg (predsjednik povjerenstva)
• Committee member: Marko Vrdoljak (član povjerenstva)
• Committee member: Tomislav Pejković (član povjerenstva)
• Committee member: Ilja Gogić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2024-07-18, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: problem trgovačkog putnika; Hamiltonov ciklus; programski jezik Python
• Language: croatian
• URN:NBN: urn:nbn:hr:217:493921
• Study programme: Title: Applied Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: sveučilišni magistar matematike (sveučilišni magistar matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2024-07-24 12:31:15