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.

SyD Colombia S.A.S, es una organización que en los últimos años ha presentado un crecimiento en el número de operaciones, el cual ha venido acompañado de altos costos logísticos y problemas relacionados con el servicio al cliente debido al uso de empresas de mensajería externas para la distribución de sus productos. Para resolver esta problemática se diseñó un sistema de ruteo vehicular usando la metodología Cluster First-Route Second, en la que se realiza la formación de clústeres por medio de una adaptación del método de barrido, para luego elaborar una ruta dentro de cada uno de estos, usando un modelo matemático del Problema de Ruteo de Vehículos con Capacidad, con soporte del software de uso libre llamado “Grafos”. Finalmente, se validó el diseño propuesto con los datos de un día de operación en la empresa SyD Colombia S.A.S, donde se evalúan diferentes indicadores, los cuales son esenciales para medir la efectividad de la nueva metodología. Como resultado del diseño desarrollado, se logró una disminución del 25.08% en la distancia recorrida en comparación con la metodología actual de la empresa, acompañada de una reducción de 13.75% en los costos de fletes. Se espera que con la adaptación realizada en la etapa de clusterización, la empresa logre reducir el porcentaje de inconformidad presentado por los clientes preferenciales. SyD Colombia S.A.S, is an organization that in recent years has presented a growth in the number of its operations, which has been accompanied by high logistics costs and problems related to customer service due to the use of external courier companies for the distribution of their products. To solve this problem, a vehicle routing system was designed using the Cluster First - Route Second methodology, in which clusters are formed by adapting the Sweep Algorithm, and then a route is created within each of these, using a mathematical model of the capacitated vehicle routing problem with support from the free software called "Grafos". Finally, the proposed design was validated with data from one day of operation in the company SyD Colombia S.A.S, where different indicators are evaluated, which are essential to measure the effectiveness of the new methodology. As a result of the design developed, a 25.08% decrease in the distance traveled was achieved in comparison with the company's current methodology, accompanied by a 13.75% reduction in freight costs. It is expected that with the adaptation made in the clustering stage, the company will be able to reduce the percentage of dissatisfaction presented by preferential clients.

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.

Combinatorial optimization problems on graphs arise in many practical applications. One of the most studied practical combinatorial optimization problem is the Vehicle Routing Problem (VRP). When coupled with modern in-car navigation and fleet management software, real world applications of VRP optimization result in significant cost savings. In this paper novel multiple improvements pivoting rule for Capacitated VRP (CVRP) is proposed. Its application significantly reduces computational time needed for CVRP optimization. A novel pivoting rule is implemented as part of the search step selection mechanism in the iterated local search algorithm. Augmented iterated local search algorithm is tested on 4 large scale real- world problems in Croatia with up to 7065 customers and 236 vehicles and on standard CVRP benchmark sets. Real-world problem data was obtained from a large Croatian logistics company. Comparison of well known first and best pivoting rules with proposed novel multiple improvements pivoting rule regarding travel distance, number of search moves and computational time is given. Achieved computational speed-ups are up to 29 times compared to the first and 9 times compared to the best improvement pivoting rule, without any substantial degradation in quality of the obtained solution.

Combinatorial optimization problems on graphs arise in many practical applications. One of the most studied practical combinatorial optimization problem is the Vehicle Routing Problem (VRP). When coupled with modern in-car navigation and fleet management software, real world applications of VRP optimization result in significant cost savings. In this paper novel multiple improvements pivoting rule for Capacitated VRP (CVRP) is proposed. Its application significantly reduces computational time needed for CVRP optimization. A novel pivoting rule is implemented as part of the search step selection mechanism in the Iterated Local Search algorithm. Augmented iterated local search algorithm is tested on 4 large scale real-world problems in Croatia with up to 7, 065 customers and 236 vehicles, and on standard CVRP benchmark sets. Real-world problem data was obtained from a large Croatian logistics company. Comparison of well known first and best pivoting rules with proposed novel multiple improvements pivoting rule regarding travel distance, number of search moves and computational time is given. Achieved computational speed-ups are up to 29 times compared to the first improvement pivoting rule and 9 times compared to the best improvement pivoting rule, without any substantial degradation in quality of the obtained solution., Kombinatoričke optimizacije na grafu pojavljuju se u mnogim aplikacijama u praksi. Jedan od najviše proučavanih kombinatoričkih optimizacijskih problema je problem usmjeravanja vozila. Ukoliko se optimizacija usmjeravanja vozila poveže sa suvremenim u vozila ugrađenim sustavima navigacije i nadgledanja voznog parka moguće je postići značajne uštede u troškovima dostave. U ovom radu je predložen novi mehanizam odabira smjera lokalnog pretraživanja zasnovan na višestrukim poboljšanjima za rješavanje kapacitivnog problema usmjeravanja vozila. Predloženi novi mehanizam je implementiran kao dio mehanizma odabira smjera lokalnog pretraživanja u algoritmu iterativnog lokalnog pretraživanja. Prošireni algoritam iterativnog lokalnog pretraživanja je provjeren na 4 vrlo velika optimizacijska problema sa stvarnim podacima iz Hrvatske (skup od 7.065 kupaca i 236 dostavnih vozila) i na standardnim testnim skupovima. Stvarni testni podaci dobiveni su od jedne velike hrvatske logističke tvrtke. U radu je napravljena usporedba između mehanizama odabira smjera lokalnog pretraživanja zasnovanih na prvom i najboljem poboljšanju te predloženog mehanizma poboljšanja lokalne pretrage. Usporedba je napravljena prema prijeđenom putu, broju pomaka lokalnog pretraživanja i vremenu izračuna. Dobiveni rezultati pokazuju ubrzanje u vremenu izračuna za 29 puta u usporedbi sa prvim smjerom poboljšanja lokalne pretrage te 9 puta u usporedbi sa najboljim smjerom poboljšanja lokalne pretrage bez značajnijih degradacija u kvaliteti dobivenog rješenja.