Izrada programskog sučelja za rješavanje problema vremenski ovisnog usmjeravanja vozila

undergraduate thesis

• Title (english): Development of a Program Interface for Time Dependent Vehicle Routing Problem
• Author: Filip Ribić
• Mentor: Tomislav Erdelić (mentor)
• Committee member: Tonči Carić (predsjednik povjerenstva)
• Committee member: Miroslav Vujić (član povjerenstva)
• Committee member: Pero Škorput (član povjerenstva)
• Granter: University of Zagreb; Faculty of Transport and Traffic Sciences; (Division of Intelligent Transport Systems and Logistics); (Department of Intelligent Transport Systems); Zagreb
• Defense date and country: 2020-09-15, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Traffic and Transport Technology; Intelligent Transport Systems and Logistics

Abstract

Problem usmjeravanja vozila problem je vezan za područje inteligentnih transportnih sustava i logistike. Rješenje problema predstavlja skup ruta vozila za dostavu robe/dobara svim korisnicima u problemu. Matematički se problem modulira pomoću teorije grafova. Problem usmjeravanja vozila uobičajeno se prikazuje u statičkim uvjetima gdje su vremena putovanja između korisnika konstantne, vremenski nepromjenjive. U stvarnome svijetu brzina na prometnici vremenski je promijenjiva veličina te se i vremena putovanja između korisnika mijenjaju ovisno o trenutku polaska. Ovaj rad prikazuje računalno rješenje problema vremenski ovisnog usmjeravanja vozila izrađenog pomoću razvojnog okruženja Microsoft Visual Studio i programskog jezika C#. Vrijeme trajanja cijelokupne dostave diskretizirano je u nekoliko vremenskih intervala kako bi se prikazala stvarna slika prometa. Ovisno o trenutku polaska od korisnika, vozilo će se do sljedećeg korisnika kretati brzinom specifičnom za vremenski interval unutar kojega se vozilo kreće. Ovaj problem može se primjeniti na stvarni svijet na temelju sljedeće pretpostavke: „vrijeme obavljanja posla i prijeđeni put vozila biti će različiti ukoliko se do korisnika dođe u 08:00 sati ujutro ili u 18:00 sati popodne“. Ovisnost o vremenu prikazana je na ukupnom prijeđenom putu i ukupnom vremenu putovanja potrebnom da bi se posjetili svi korisnici. Da bi se što bolje prikazala promjena varijabli ukupnog prijeđenog puta i vremena, programsko riješenje testirano je se na više primjera različitih vremenskih intervala s različitim pripadajućim brzinama. Rješenje je prikazano na dvije vrste testnih problema s manjim i većim brojem korisnika. Završni rezultat rada prikazuje uštedu u vremenu i udaljenosti ovisno o brzini, te se rezultati rada mogu primijeniti u mnogim današnjim prometnim problemima opskrbe korisnika, prijevoza robe te smještaja električnih i benzinskih pumpi. Primjenom rezultata u praksi može se doći do smanjenja transportnih troškova.

Abstract (english)

Vehicle routing problem is related to the field of intelligent transport systems and logistics. The solution of the problem represents a set of vehicle routes to deliver goods to customers in the problem. The matematical interpretation of the problem is modeled by graph theory. Vehicle routing problem usually consideres static conditions where travel times between the customers are time invariant. In the real world vehicle speed changes through time, and the travel times between customers vary, depending on the departure time. This work presents a computer solution of time dependent vehicle routing problem created with use of Microsoft Visual Studio development environment and the C# programming language. The delivery time is discretizied in several time intervals in order to represent real traffic conditions. Depending on the time interval in which the vehicle leaves the customer it will move to the next customer at a speed specific to that time interval. This problem can be applied to the real world based on the following assumption: „the time of work and distance traveled by the vehicle will be different if the user is reached at 08:00 in the morning or at 18:00 in the afternoon“. The time dependency is reflected in the total traveled distance and the time required to visit all customers. To better represent the change of total distance traveled and total travel time variables, the software solution will be tested on several examples with different time intervals and different corresponding speeds. The solution is shown on two type test problems with smaller and larger number of users. The final result of the work shows savings in time and distance depending on the speed. The results of the paper can be applied in many of today's traffic problems of customer supply, transport of goods and placement of electric and gas stations. Applying the results in practice can reduce transport costs.

• Keywords: problem usmjeravanja vozila; vremenski ovisno usmjeravanja vozila; heuristički algoritmi; lokalna pretraga; Visual Studio; C#
• Keywords (english): vehicle routing problem; time dependent vehicle routing problem; total distance traveled; total time; Visual Studio; C#
• Language: croatian
• URN:NBN: urn:nbn:hr:119:876898
• Study programme: Title: Intelligent Transport Systems and Logistics; specializations in: Intelligent Transport Systems, Logistics; Course: Intelligent Transport Systems; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka prometa (sveučilišni/a prvostupnik/prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka prometa)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-11-06 10:28:25