Heurísticas para resolver problemas de rutas de vehículos con flota heterogénea y varios viajes por vehículo

Abstract

[EN] Nowadays, in order to enhance competitiveness, there is a large amount of companies offering logistics services to their customers. However, these companies are all facing the same challenge of distributing products to hundreds of clients with higher efficiency, namely, optimizing distances, costs and time. According to the terminology of the scientific literature, we can call these optimization problems as Vehicle Routing Problem (VRP).

Specifically, the VRP is a genetic problem which is about to find the shortest or the most economical routes between the depots and the customers. Therefore, the focus of the VRP is determining the routes of a fleet of vehicles that start and finish from one of the depots to serve the customers which belongs to a transport network.

Since solving the VRP is a good way to save resources, provide better services, improve business competitions, and so on, it is very important to study this problem. However, the VRP belongs to problems of NP-hard. That means with the traditional methods, exact methods, we are not able to reach an optimal solution within a reasonable time range. Thus, we will apply heuristics or metaheuristics to investigate the VRP, so that it can bring us good solutions in a reasonable time.

In this master thesis, we will develop heuristics based on the well-known algorithm, the Clarke & Wright algorithm, for sophisticated problems of VRP and their generalizations. Besides, a complete computational evaluation will be conducted to evaluate the performance of the proposed methods.

[ES] Hoy en día existe una cantidad elevada de empresas que proponen servicios logísticos y que se enfrentan al reto de distribuir productos a cientos de clientes de manera más efectiva, es decir, optimizando distancias, costes y tiempo. Todo eso lo podemos denominar como problemas de rutas de vehículos o Vehicle Routing Problem (VRP) según la terminología de la literatura científica. En concreto, el VRP es un problema genético donde se trata de encontrar las rutas más cortas o económicas entre los almacenes y los clientes. Por lo que el VRP consiste en determinar las rutas de una flota de vehículos que inician y finalizan desde uno de los almacenes para atender a los clientes que están en una red de transporte. Dado que resolver el VRP puede ahorrar recursos, ofrecer mejores servicios a los clientes, aumentar la competencia de la empresa, etc., es muy relevante estudiar este problema. Sin embargo, el VRP pertenece al grupo de problemas complejos o NP-hard. Esto quiere decir que con los métodos tradicionales, los métodos exactos, no es posible alcanzar una solución óptima en un tiempo razonable. Por tanto, vamos a investigar el VRP mediante los métodos heurísticos y/o metaheurísticos, con los cuales es posible encontrar soluciones buenas en un tiempo razonable. En este trabajo fin de máster, desarrollaremos algoritmos heurísticos, basados en la conocida técnica de Clarke & Wright, para complejos problemas de rutas de vehículos de tipo VRP y sus generalizaciones. Se llevará a cabo una completa evaluación computacional para evaluar el rendimiento de los métodos propuestos