Aplicación de la metodología GRASP al problema de Rutificación de Vehículos

Resumen

En este trabajo se describe el desarrollo e implementación de un Sistema de Soporte a la Decisión (DSS) que ayudará en el proceso de cálculo de rutas y llenado de camiones, que tienen que transportar un número considerable de vehículos desde 8 orígenes y distribuirlos entre más de 3.000 posibles destinos repartidos por España y Portugal (incluidos algunos de Francia, Alemania, etc.). Se analiza, en primer lugar, el comportamiento de distintas metodologías a la hora de resolver un problema de rutas del tipo MDVRP y VRPTW. Tras ello, se opta por la utilización de la heurística GRASP como núcleo del optimizador que será desarrollado como una aplicación Web. El resultado es una mejora en la utilización del cubicaje de los vehículos, y una racionalización en las rutas que se traducen en un descenso de los costes de transporte.

Palabras clave: cálculo de rutas, inteligencia artificial, heurísticas.


Application of GRASP methodology to Vehicle Routing Problem

Abstract: This work describes the development and implementation of a Decision support system (DSS) that will help in the process of calculation of routes and filling of trucks for a logistics operator. The aim is to improve the process of designing the routes to follow by a heterogeneous fleet of trucks that transport a large number of vehicles (of different features (volume, cost, etc.), from 8 major origins to more than 3,000 possible destinations spread both across the Iberian peninsula (Spain and Portugal), and some destinations in the rest of Europe (mainly France and Germany). The pursued improvements compared to the current situation, embrace the maximum occupancy of trucks, the total travelled distance, reduction of delivery times, minimization of distance travelled with minimal or no occupation of the truck, etc. Firstly a review of the methodologies currently used for the resolution of this type of problem is presented. Within the VRP problems (Vehicle Routing Problem), our case can be classified as a hybrid between the VRPTW problem (VRP with Time Windows) and the MDVRP (Multi Depot VRP, VRP with multiple locations). After analyzing both the exact and the approximate resolution methods, delving more into the latter given that they better conform to the problem that concerns us, the paper review different types of algorithms: local search, two stages, evolutionary, GRASP, smart colonies and solutions with multi-agent systems. Among them, GRASP algorithm was finally chosen for the problem resolution. Furthermore, a friendly WEB application has been developed to be offered to the operator responsible for the design of the routes. The Web will provide the operator with possible solutions for him to evaluate and validate based on their experience. After a series of tests, the use of this optimization tool reveals to bring improved solutions, particularly as regards the reduction of the delivery times and maximization of the occupation of the trucks. One of the main problems in current operations is the delay in the delivery of some orders, when there is no enough demand to fill a truck. The application resolves this problem by placing vehicles in trucks that are already filled with highly demanded vehicles for a nearby target. The delay in any of these specific vehicles to give out to the isolated ones is a preferred solution. Another problem that the application solves is the minimization of the distance travelled empty, ensuring that the end of the routes, are close to loading points. In short, although the application is still in testing phase, it has offered an important aid to the operator responsible for the routes design.

Keywords: route calculation, artificial intelligence, heuristics.