En el sector de utilities, l'eficiència en la planificació de rutes és un factor clau per a la millora de la distribució de productes i serveis, reduint costos operatius i temps de lliurament, conduint així a l'èxit empresarial. Un dels problemes més comuns en el món de l'optimització, per la seva complexitat i la seva gran utilitat en aquest sectors és el problema d'encaminament de vehicles capacitatsles sigles en anglés dels quals són CVRP, cosa que significa \textit{Capacitated Vehicle Routing Problem}.. Aquest clàssic problema tracta de transportar mercaderies des d'un centre logístic a diversos clients. Cada client demanda una determinada quantitat de mercaderies i els vehicles tenen una capacitat de transport limitada. Resoldre aquest tipus de problemes és computacionalment car i es consideren de naturalesa NP-hard pel que s'ha estimulat el desenvolupament de mètodes heurístics per a obtenir bones solucions per a problemes amb conjunts de dades grans. En aquest treball s'apliquen dos enfocaments de resolució per a abordar una variant no estàndard i bastant complexa del CVRP: un model de programació lineal enter mixt que obté una solució òptima, i un algorisme genètic, que actua com metaheurística i troba una solució quasi-òptima. No obstant això, els resultats indiquen que, en problemes de gran grandària, els algorismes genètics són capaços de trobar solucions d'alta qualitat mentres que, al mateix temps, aconseguixen reduir considerablement els temps d'execució. En este context, el projecte abasta una anàlisi de resultats per a problemes de diferents grandàries, amb la finalitat de comparar el rendiment dels mètodes proposats. Paraules claus: Programació lineal sencera mixta, Algorismes genètics, CVRP. Codis de la Mathematic Subject Classification: [90C11, 90C59, 68W50].

En el sector de utilities, la eficiencia en la planificación de rutas es un factor clave para la mejora de la distribución de productos y servicios, reduciendo costes operativos y tiempos de entrega, conduciendo así al éxito empresarial. Uno de los problemas más comunes en el mundo de la optimización, por su complejidad y su gran utilidad, es el problema de enrutamiento de vehículos capacitados cuyas siglas en inglés son CVRP, lo que significa \Capacitated Vehicle Routing Problem. Este clásico problema trata de transportar mercancías desde un centro logístico a varios clientes. Cada cliente demanda una determinada cantidad de mercancías y los vehículos tienen una capacidad de transporte limitada. Su resolución es computacionalmente cara y se considera de naturaleza NP-hard por lo que se ha estimulado el desarrollo de métodos heurísticos y metaheurísticos para obtener buenas soluciones cuando el conjunto de datos es grande. En este trabajo se aplican dos enfoques de resolución para abordar una variante no estándar y bastante compleja del CVRP: un modelo de programación lineal entero mixto que obtiene una solución óptima, y un algoritmo genético, que actúa como metaheurística y encuentra una solución cuasi-óptima. Sin embargo, los resultados indican que, en problemas de gran tamaño, los algoritmos genéticos son capaces de encontrar soluciones de alta calidad mientras que, al mismo tiempo, logran reducir considerablemente los tiempos de ejecución. En este contexto, el proyecto abarca un análisis de resultados para problemas de diferentes tamaños, con el fin de comparar el rendimiento de los métodos propuestos. Palabras claves: Programación lineal entera mixta, Algoritmos genéticos, CVRP. Códigos de la Mathematic Subject Classification: [90C11, 90C59, 68W50].

In the utilities sector, efficient route planning is a key factor in improving the distribution of products and services, reducing operating costs and delivery times, thus leading to business success. One of the most common problems in the world of optimisation, due to its complexity and its great utility in this sector is the capacitated vehicle routing problem, CVRP. This classic problem deals with transporting goods from a logistics centre to several customers. Each customer demands a certain quantity of goods and the vehicles have a limited transport capacity. Solving such problems is computationally expensive and they are considered NP-hard in nature, so the development of heuristic methods to obtain good solutions for problems with large data sets has been encouraged. In this paper, two solving approaches are applied to deal with a non-standard and rather complex variant of the CVRP: a mixed integer linear programming model that obtains an optimal solution, and a genetic algorithm, which acts as a metaheuristic and finds a quasi-optimal solution. However, the results indicate that, on large problems, genetic algorithms are able to find high quality solutions while, at the same time, managing to reduce execution times considerably. In this context, the project covers an analysis of results for problems of different sizes in order to compare the performance of the proposed methods. Keywords: Mixed integer Linear Programming, Genetic Algorithms, CVRP. Mathematic Subject Classification codes: [90C11, 90C59, 68W50].