Rutas y algoritmos genéticos

.

Primer Congreso de Logística y Gestión de la Cadena de Suministro Zaragoza, 12 y 13 de Septiembre de 2007

LOGÍSTICA INVERSA Y RUTEO DE VEHÍCULOS: BÚSQUEDA DISPERSA APLICADA AL PROBLEMA DE RUTEO DE VEHÍCULOS CON COLECTA Y ENTREGA SIMULTÁNEA
N. G. Maquera Departamento de Engenharia de Produção Universidade Federal Fluminense, Niterói - RJ, Brasil D. Abensur Programa de Engenharia deProdução Universidade Federal do Rio de Janeiro - RJ, Brasil A. Parracho Departamento de Engenharia de Produção Universidade Federal Fluminense, Niterói - RJ, Brasil Abstract Scatter Search (SS) is a method based on improving solutions by working on a set of solutions, named reference set. Although presenting similarities with Genetic Algorithms, SS differs from those in foundations such as the use ofsystematic instead of random strategies. An important aspect of Scatter Search is its ability of driving search to promising regions with high quality. Scatter Search provides a flexible mark that allows for the development of algorithms with different complexity degrees to diverse stages of the search. This works describes an application to solve the vehicles routing problem with simultaneousdelivery and pick-up (PRVCES). Preliminary results of testing instances in the literature of PRVCES are presented. Keywords: Reverse logistics, transportation, vehicles routing problem

Resumen La Metaheurística Búsqueda Dispersa (BD) es un método que combina soluciones a partir de un conjunto de referencia, con la finalidad de crear nuevas soluciones. Aun que presente similitudes con los AlgoritmosGenéticos, se diferencia de ellos en principios fundamentales, tal como el uso de estrategias sistemáticas en vez de aleatorias. Un aspecto importante de la BD es la fase de providenciar soluciones diversas y con alto grado de calidad para dirigir la búsqueda a regiones promisorias. BD proporciona un marco flexible que permite el desarrollo de diferentes algoritmos con distintos grados decomplejidad para las diferentes etapas de la búsqueda. En este trabajo presentamos una aplicación para la solución del Problema de Ruteo de Vehículos con Carga y Descarga Simultánea. Mostramos resultados preliminares, al testar instancias encontrados en la literatura del PRVCES. Palabras clave: Logística Inversa, transporte, ruteo de vehículos.

.

1. INTRODUCCIÓN La importancia de la eficacia y de laeficiencia de los sistemas de distribución se torna evidente cuando se considera el impacto de costos asociados a las operaciones de las empresas. La vigorosa industrialización del mundo moderno y la incorporación de nuevos hábitos de consumo, en la sociedad, hicieron surgir cada vez más residuos urbanos que deben ser gerenciados. El gerenciamiento de la destinación de los residuos urbanos es unconjunto de acciones normativas, operacionales, financieras y de planeamiento utilizando tecnologías compatibles con la realidad local. Para alcanzar el objetivo, en general se adopta la filosofía comúnmente denominada 3R que significa reducir, reutilizar y reciclar determinados materiales. Frecuentemente algunos o todos los materiales recuperados son transportados conjuntamente con pedidos deentregas, pues combinar colectas con las entregas resulta en costos más bajos de transporte de que considerar cada uno en rutas y en vehículos separados. La importancia del Problema de Ruteo de Vehículos (PRV) se refleja en la grande variedad de aplicaciones correspondientes en las áreas de investigación de operaciones, logística, distribución, transporte entre otros. En este trabajo, motivados porlas diferentes aplicaciones del PRV en logística inversa, integramos las estrategias de colecta con las estrategias de la ruta de entrega. El Problema de Ruteo de Vehículos con Colecta y Entrega Simultánea (PRVCES) es una variante del PRV con Cargas de Retorno, en el cual la demanda de cada cliente es compuesta de pedidos de entrega y/o de colecta. Se consideran situaciones en que las entregas...