Rješavanje problema usmjeravanja vozila hibridnim staničnim evolucijskim algoritmom

doctoral thesis

• Title (english): Solving the vehicle routing problem using hybrid cellular evolutionary algorithm
• Author: Ante Galić
• Mentor: Tonči Carić (mentor)
• Committee member: Hrvoje Gold (predsjednik povjerenstva)
• Committee member: Tonči Carić (član povjerenstva)
• Committee member: Domagoj Jakobović (član povjerenstva)
• Committee member: Sadko Mandžuka (član povjerenstva)
• Granter: University of Zagreb; Faculty of Transport and Traffic Sciences; Zagreb
• Defense date and country: 2018-01-25, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Traffic and Transport Technology; Road and Rail Transport
• Universal decimal classification (UDC): 656.1/.5 - Land transport

Abstract

Problem usmjeravanja vozila (VRP) kompleksan je kombinatorički problem s kojim se svakodnevno susreću tvrtke koje obavljaju dostavu robe. Njegovim učinkovitim rješavanjem moguće je značajno smanjiti troškove dostave. Metaheurističkim metodama moguće je relativno brzo pronaći visoko kvalitetna rješenja. Stanični evolucijski algoritam metaheuristički je algoritam kod kojeg su jedinke iz populacije raspoređene unutar toroidalne mreže i mogu biti u interakciji samo sa obližnjim jedinkama. Podešavanjem selekcijskog pritiska moguće je postići odgovarajući omjer diverzifikacije i intenzifikacije koji je ključan za uspješnost algoritma. Hibridizacija postupkom pretraživanja velikog susjedstva ubrzava pronalazak visoko kvalitetnih rješenja. Razvijeni algoritam testiran je na nekoliko skupova ispitnih zadataka te na problemima dostave hrvatskih tvrtki. Rezultati ostvareni na ispitnim zadacima pokazuju da učinkovitost algoritma ne odstupa mnogo od najboljih poznatih algoritama za ovu vrstu problema, dok rezultati ostvareni na problemima hrvatskih tvrtki pokazuju da je primjenom algoritma moguće postići značajne uštede.

Abstract (english)

Vehicle Routing Problem (VRP) is a complex combinatorial problem encountered daily by companies that are dealing with goods delivery. With its ecient solving it is possible to signicantly reduce the cost of delivery. Metaheuristic methods are capable of nding high-quality solutions in reasonable amount of time. The cellular evolutionary algorithm is a metaheuristic algorithm in which the individuals from the population are distributed within the toroidal grid and can interact only with nearby entities. By adjusting the selection pressure, it is possible to achieve the appropriate ratio of diversication and intensication that is crucial to the success of the algorithm. Hybridization by a large neighborhood search accelerates the nding of high quality solutions. The developed algorithm has been tested on several sets of benchmarks and on the delivery problems of Croatian companies. The results obtained on the benchmarks show that the eciency of the algorithm does not dier much from the best-known algorithms for this type of problem, while the results achieved on the problems of Croatian companies show that it is possible to achieve signicant savings by algorithm application.

• Keywords: problem trgovačkog putnika; TSP; problem usmjeravanja vozila; VRP; problem usmjeravanja vozila s vremenskim prozorima; VRPTW; metaheurističke metode; genetski algoritam; evolucijski algoritam; stanični evolucijski algoritam; cEA; stanični genetski algoritam; cGA; kombinatorička optimizacija
• Keywords (english): traveling salesman problem; TSP; vehicle routing problem; VRP; vehicle routing problem with time windows; VRPTW; metaheuristics; genetic algorithm; evolutionary algorithm; cellular evolutionary algorithm; cEA; cellular genetic algorithm; cGA; combinatorial optimization
• Language: croatian
• URN:NBN: urn:nbn:hr:119:580684
• Study programme: Title: Technological systems in traffic and transport; Study programme type: university; Study level: postgraduate; Academic / professional title: doktor/doktorica znanosti, područje tehničkih znanosti, polje tehnologija prometa i transport (doktor/doktorica znanosti, područje tehničkih znanosti, polje tehnologija prometa i transport)
• Type of resource: Text
• Extent: VI, 140 str. ; 30 cm
• File origin: Born digital
• Access conditions: Open access
• Created on: 2018-03-09 15:28:12