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

Autor: Paolo Priore-Moreno, Verónica Villanueva-Madrileño, Isabel Fernández-Quesada, Raúl Pino-Diez, Carlos Martínez-Carcedo
Rok vydání: 2012
Předmět:
Zdroj: Dirección y Organización. :46-55
ISSN: 2171-6323
1132-175X
DOI: 10.37610/dyo.v0i48.411
Popis: En este trabajo se describe el desarrollo e implementacion de un Sistema de Soporte a la Decision (DSS) que ayudara en el proceso de calculo de rutas y llenado de camiones, que tienen que transportar un numero considerable de vehiculos desde 8 origenes y distribuirlos entre mas de 3.000 posibles destinos repartidos por Espana y Portugal (incluidos algunos de Francia, Alemania, etc.). Se analiza, en primer lugar, el comportamiento de distintas metodologias a la hora de resolver un problema de rutas del tipo MDVRP y VRPTW. Tras ello, se opta por la utilizacion de la heuristica GRASP como nucleo del optimizador que sera desarrollado como una aplicacion Web. El resultado es una mejora en la utilizacion del cubicaje de los vehiculos, y una racionalizacion en las rutas que se traducen en un descenso de los costes de transporte. Palabras clave : calculo de rutas, inteligencia artificial, heuristicas. 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.
Databáze: OpenAIRE
Externí odkaz: