Search

U navedenom radu opisan je problema usmjeravanja vozila sa ograničenim kapacitetom. Objašnjeni su Clarke-Wrightov algoritam, Holmes-Parkerov algoritam, Sweep algoritam i Fisher-Jaikumarov algoritam, uspoređene su njihove performanse, vizualno su demonstrirani i prikazani su detalji njihove izvedbe. The following paper deals with vehicle routing problem with capacity constraints. The problem is explained, and we present several heuristics used for finding adequate solutions to the problem. The following heuristics are explained: Clarke-Wright algorithm, Holmes-Parker algorithm, Sweep algorithm and Fisher-Jaikumar algorithm. Their performances are compared, and we show visual representation of the solutions.

Nastojanje da se bilo kakav nepotreban trošak prijevoza robe do klijenata smanji, potaknulo je razvoj mnogih metoda za rješavanje ovog optimizacijskog problema, nazvanog problem usmjeravanja vozila (VRP). Postoju brojne inačice VRP-a ovisno o zadanim ograničenjima, predmet ovog rada je problem usmjeravanja vozila s kapacitetnim ograničenjima (CVRP). Heurističke metode, koje iako ne pronalaze uvijek optimalno rješenje, se često primjenjuju i danas kod rješavanja većih problema (s 100 ili više klijenata) zbog puno veće brzine pronalaska rješenja u odnosu na egzaktne metode. Programskom implementacijom heurističkih metoda, Clarke & Wright-ova i Sweep algoritma, uspoređeni su rezultati u ovisnosti o broju klijenata i klijentskim potražnjama te predložena poboljšanja. The effort to reduce any unnecessary cost of transporting goods to customers has prompted the development of many methods for solving this optimization problem, called vehicle routing problem (VRP). There are numerous variants of VRP depending on the given constraints, the subject of this paper is the Capacitated vehicle routing problem (CVRP). Heuristic methods, although they do not always find the optimal solution, are often used today in solving larger problems (with 100 or more clients) due to the much higher speed of finding solutions compared to exact methods. The software application of heuristic methods, Clarke & Wright’s and Sweep algorithm, compares the results depending on the number of clients and their demands, improvements are proposed based on the results.

Ovaj rad obrađuje problem usmjeravanja vozila, te njegove instance s ograničenim kapacitetom, vremenskim prozorima i mogućnošću preuzimanja tereta i dostave. Dan je detaljan opis problema i korištenih metaheurističkih algoritama: genetskog algoritma turnirske eliminacije i algoritma evolucijske strategije. Implementirana su tri oblika zapisa rješenja, operatori mutacije i križanja i dva lokalna operatora. Istraživana je ovisnost kvalitete rješenja o obliku zapisa, korištenom algoritmu i korištenju lokalnih operatora. Dobiveni rezultati prikazani su grafički i analizirani. This paper deals with vehicle routing problem and its instances with limited capacity, time windows and pick-up and delivery. Detailed description of the problem is given, as well as of the two metaheuristic algorithms that were used: genetic algorithm with tournament selection and evolution strategy algorithm. Three forms of results, mutation and crossover operators and two local operators were implemented. The dependence of the quality of the solution on the form of result, used algorithm and the use of local operators was explored. The obtained results are shown graphically and analyzed.

U ovom radu opisan je i obrađen problem usmjeravanja vozila i rješavanje tri inačice tog problema metaheurističkim pristupom, konkretno genetskim algoritmom. Navedene su postojeće metode rješavanja problema i ostvarena je vlastita implementacija rješenja u tri oblika zapisa u statičkim uvjetima. Kao dinamička komponenta za različite genotipe i inačice problema ispitana je brzina konvergencije rješenja ka rješenjima dobivenim heurističkim pristupom kao i brzina pronalaska rješenja za fiksni broj evaluacija. Rezultati su uspoređeni međusobno te prikazani grafički. In this thesis, vehicle routing problem and solving three variants of it is described. Problem variants were solved using metaheuristic approach, specifically genetic algorithm. The existing methods of solving the VRP problem were mentioned as well as the solution implementation that was recorded in three forms in static conditions. As a dynamic component for different genotypes and variants of the problem, convergence speed to the solutions obtained by heuristic approach was examined as well as the speed of finding a solution for a fixed number of evaluations. The results were compared and presented graphically.