METAHEURÍSTICA VIRAL SYSTEM APLICADA AL PROBLEMA DE RUTEO DE VEHÍCULOS CON FLOTA HETEROGÉNEA Y VENTANAS DE

TIEMPO (FSMVRPTW)

KARIM YANETH PÉREZ MARTÍNEZ

SERGIO RAMÓN MAURY OTERO

UNIVERSIDAD DE CÓRDOBA

FACULTAD DE CIENCIAS BÁSICAS E INGENIERÍAS

PROGRAMA DE INGENIERÍA INDUSTRIAL

MONTERÍA – CÓRDOBA

2010

TABLA DE CONTENIDO

Pág.

CAPÍTULO 1: GENERALIDADES

1.1 INTRODUCCIÓN…………………………………………………………………………………………………

1.2 PLANTEAMIENTO DEL PROBLEMA

1.2.1 ANTECEDENTES………………………………………………………………………………………………

1.2.2 PROBLEMA………………………………………………………………………………………………………

1.2.3 SÍNTOMAS DEL PROBLEMA……………………………………………………………..………………

1.2.4 CAUSAS DEL PROBLEMA………………………………………………………………………………….

1.2.5 PRONÓSTICO…………………………………………………………………………………………………..

1.2.6 CONTROL AL PRONÓSTICO………………………………………………………………………………

1.2.7 INTERROGANTES Y FORMULACIÓN DEL PROBLEMA…………………………………………

1.3 OBJETIVOS

1.3.1 OBJETIVO GENERAL………………………………………………………………………………………….

1.3.2 OBJETIVOS ESPECÍFICOS…………………………………………………………………………………..

1.4 JUSTIFICACIÓN……………………………………………………………………………………………………….

1.5 ALCANCES Y LIMITACIONES…………………………………………………………………………………….

1.6 DELIMITACIÓN……………………………………………………………………………………………………….

2. CAPÍTULO 2: MARCO DE REFERENCIA TEÓRICO GENERAL

2.1 MARCO TEÓRICO

2.2 MARCO CONCEPTUAL

2.3 BIBLIOGRAFÍA

CAPÍTULO 1: GENERALIDADES

1.1 INTRODUCCIÓN

1.2 PLANTEAMIENTO DEL PROBLEMA

1.2.1 ANTECEDENTES

Encontrar rutas eficientes para un conjunto de vehículos es un importante problema logístico que ha sido estudiado desde hace varias décadas y que cuenta con muchas aplicaciones en la vida real; tal es el caso de los Centros de acopio, Distribución de Combustible, mensajería e incluso aquellas organizaciones que distribuyen sus productos en forma directa, para los cuales la tarea de identificar la secuencia en que deben ser visitados sus clientes de tal forma que reciban sus productos oportunamente se convierte en un problema que requiere especial cuidado. Este tipo de problemas (VRPs) está estrechamente relacionado con el conocido Traveling Salesman Problem (TSP), y en esencia busca determinar el mejor conjunto de rutas que deben ser seguidas por una flota de vehículos para satisfacer la demanda de un conjunto de clientes; El VRP representa un problema de optimización combinatoria en el que el número de soluciones factibles aumenta exponencialmente con el número de clientes y del que no se conoce un algoritmo polinomial que encuentre la solución óptima en cuestión de segundos, por tanto es considerado un problema NP-hard [1]. Motivados por esto, desde hace varios años se han dedicado muchos esfuerzos para entender el comportamiento de este tipo de problemas y encontrar soluciones de buena calidad y en tiempos computacionales aceptables; los primeros en considerar este tema fueron Dantzing y Ramser [2], los cuales hicieron la primera formulación matemática del VRP para una aplicación a un problema de distribución de combustible, posteriormente Miller, Tucker y Zemlin [3] con base a la formulación anterior incorporaron una mejora para algunas de las restricciones del problema, Después de esto Clarke y Wright [4] proponen El algoritmo de Ahorros como un método de solución avanzado que ofrece soluciones aceptables para el problema. A partir de allí han surgido varias extensiones del modelo original VRP basadas en la inclusión de variables existentes en la vida real; tal es el caso del modelo FSMVRP (Fleet Size and Mix Vehicle Routing Problem) el cual fue propuesto por Golden, Assad y Levy [5]; El problema VRP que considera el intervalo (Ventana) de tiempo en el que los clientes están dispuestos para recibir el servicio, Modelo VRPTW (Vehicle Routing Problem with Times

Windows) el cual fue formulado por Cordeau, Desaulniers, Desrosiers, Solomon y Soumis [6]; El problema con múltiples depósitos MDVRP (Multi-Depot Vehicle Routing Problem); VRP teniendo en cuenta entregas y devoluciones VRPPD (Vehicle Routing Problem with Pickup and Delivery); Problemas con valores al azar como número de clientes, tiempos de servicio, demanda etc. SVRP (Stochastic Vehicle Routing Problem) [7]; Además de estos principales modelos, se han considerado también una mezcla entre ellos, como es el caso del modelo de interés para este estudio FSMVRPTW (Fleet Size and Mix Vehicle Routing Problem with Times Windows) planteado por primera vez por Liu y Shen en 1999 [8] en el cual además de considerar el intervalo de tiempo en que los clientes pueden ser servidos, tiene en cuenta un sistema de flota heterogénea, es decir, distintos tipos de vehículos que involucran distintas capacidades y costos de operación.

Paralelo al planteamiento de los diversos modelos VRP, han surgido varios métodos heurísticos y aplicaciones metaheurísticas orientadas a la búsqueda de soluciones de alta calidad y eficiencia computacional para este problema; dentro de estos tenemos las heurísticas de Inserción como la secuencial de Mole & Jameson y la Inserción en paralelo de Christofides, Mingozzi y Toth; Métodos de asignar primero y rutear después como la Heurística de Barrido o Sweet, Heurística de asignación generalizada de Fisher y Jaikumar y la Heurística de localización de Bramel y Simchi – Levi ; Métodos de Rutear primero

Asignar después ; Así como los algoritmos de búsqueda local (Operador -intercambio, Operador Or – opt , entre otros). Continuo a esto, se han aplicado al VRP y sus variaciones algunas de las metaheurísticas más importantes desarrolladas hasta hoy como lo son ACS (Ants Colony System), Search Tabú la cual ha sido aplicada para VRPs y VRPTW, Algoritmos Genéticos [9], Simulated Annealing y Neural Networks [7]. Recientemente se han implementado diversos métodos para el modelo en estudio FSMVRPTW como lo es Adaptive Memory Programming [10] y A Well- Scalable Metaheuristic para el mismo [11] los cuales han arrojado soluciones aceptables para éste tipo de problemas y con los cuales buscamos confrontar los resultados de esta investigación.

1.2.2 PROBLEMA

En la actualidad el principal problema que afronta cualquier organización es mantenerse dentro de un entorno altamente competitivo, variable y exigente y el cual solo puede superar si orienta sus actividades hacia la satisfacción total del cliente y la realización de las operaciones a un menor costo. Ésta última incluye no solamente los costos de producción y operación, sino también los costos asociados a la distribución del producto o costos de transporte los cuales representan entre el 10% y 20% del costo total de los bienes [7]. Orientar esfuerzos hacia la reducción en los costos de transportes es una tarea que debe ser abordada primordialmente por las organizaciones que funcionan como

centros de distribución o centros de acopio, debido a que esto representa su actividad principal; Este proceso incluye determinar la mejor composición de la flota de vehículos y un conjunto de rutas eficientes. Debido a que este tipo de organizaciones cuentan con un amplio número de clientes, ésta tarea tiene un alto grado de complejidad y por lo general su planeación se hace de manera subjetiva, lo que consecuentemente genera rutas más largas, costos de transporte elevados e incluso multas para las organizaciones que no cuentan con una flota de vehículos propia. Es por esto que actualmente y para conveniencia de estas organizaciones se hace necesario la investigación e implementación de métodos eficientes para la solución de éste problema.

1.2.3 SÍNTOMAS DEL PROBLEMA

Las situaciones que caracterizan la presencia de este tipo de problemas son:

– Tiempos de viaje extremadamente largos.– Altos costos de transporte.– Clientes con demanda insatisfecha.– Flota de vehículos muy grande.(aparentemente necesarios para suplir la demanda)– Retraso en la entrega de los bienes.– Tiempo ocioso de los vehículos que componen la flota.– Poca capacidad de reacción ante las variaciones del mercado.

1.2.4 CAUSAS DEL PROBLEMA

Entre las causas que pueden generar la presencia de este tipo de problemas en las organizaciones, se encuentra lo mencionado a continuación:

– Nivel de complejidad de esta tarea.– El desconocimiento de métodos o procedimientos específicos que dan solución a

este problema y permiten la programación de la distribución para las organizaciones relacionadas.

– Altos costos en los que se incurren al adquirir un software que ayude al proceso o una persona especializada en el tema.

– Amplio número de clientes, lo que dificulta el proceso.– Falta de información acerca de la ubicación geográfica de cada uno de los clientes.– Variación constante de los elementos del problema como la demanda y el número

de clientes.

1.2.5 PRONÓSTICO

Debido a la situación actual altamente competitiva, si las organizaciones que tienen relación con el problema planteado, continúan realizando la planeación de la distribución de los bienes en forma empírica; se verán afectadas considerablemente por la competencia, debido a que estarán incapacitados para reducir los costos de operación y mantenimiento de transporte, así como para abarcar nuevos segmentos de demanda y satisfacer oportunamente a los clientes existentes. De esta manera, si la competencia es voraz y crece rápidamente, este tipo de organizaciones tienden a desaparecer.

1.2.6 CONTROL AL PRONÓSTICO

Con el fin de mitigar el impacto que generan las consecuencias del problema en estudio, las organizaciones enmarcadas en actividades de entrega de bienes, deben hacer uso de un aplicativo sistemático y eficiente que le permita determinar con precisión la secuencia en la cual deben ser visitados sus clientes, así como la composición de los recursos a utilizar, de tal forma que esta tarea involucre el menor costo y tiempo posible, y le de flexibilidad para reaccionar ante las variaciones del medio.

1.2.7 INTERROGANTES Y FORMULACIÓN DEL PROBLEMA

La descripción del problema realizada permite la formulación del siguiente interrogante: ¿Puede aplicarse la Metaheurística Viral System al problema de ruteo de vehículos con flota heterogénea y ventanas de tiempo, obteniendo buenos resultados en materia de calidad de la solución y eficiencia computacional?, a su vez este cuestionamiento incluye: ¿Cuál es el modelo Matemático que representa el FSMVRPTW?, ¿Qué métodos se han utilizado hasta hoy para dar solución al problema planteado?, ¿Cuáles de estos métodos han generado las mejores soluciones?, ¿Puede Viral System generar mejores soluciones que los algoritmos anteriores para este problema?, ¿Son las soluciones obtenidas con Viral System costosas o económicas en términos computacionales?.

1.3 OBJETIVOS

1.3.1 OBJETIVO GENERAL

Implementar la Metaheurística Viral System como una herramienta de solución para el problema de Ruteo de Vehículos con Flota Heterogénea y Ventanas de Tiempo (FSMVRPTW) con el fin de medir y comparar la calidad de las soluciones obtenidas y la eficiencia computacional de la aplicación con los métodos existentes.

1.3.2 OBJETIVOS ESPECÍFICOS

– Exponer la descripción general y formulación matemática del Problema de ruteo de Vehículos con Flota Heterogénea y Ventanas de Tiempo (FSMVRPTW).

– Dar a conocer y adaptar La Metaheurística Viral System al problema de ruteo de vehículos.

– Solucionar el Problema en cuestión a través de la Metaheurística planteada.

– Medir la calidad de las soluciones obtenidas verificando la cercanía que estas presenten con respecto al óptimo.

– Valorar el tiempo de ejecución del algoritmo planteado (Eficiencia Computacional).

– Comparar la calidad de las soluciones y la eficiencia computacional obtenida, con los resultados de los métodos metaheurísticos ya aplicados a este tipo de problemas.

– Definir si la Metaheurística Viral System es una herramienta eficiente para la solución de los problemas de Ruteo de Vehículos.

1.4 JUSTIFICACIÓN

Como ya se ha mencionado anteriormente, las organizaciones de Hoy necesitan hacer uso de aplicaciones rápidas y efectivas para facilitar y asegurar la planeación de todas sus actividades y la buena ejecución de las mismas.

Motivados por ésta situación y teniendo en cuenta que en nuestro medio se presenta comúnmente una afinidad entre la situación vivida por las organizaciones y las características del problema planteado, ya que éstas poseen flotas heterogéneas y deben cumplir restricciones de tiempo y demanda, consideramos de gran utilidad la generación de una nueva aplicación que satisfaga la necesidad existente.

1.5 ALCANCES Y LIMITACIONES

El problema específico al que se pretende dar solución es derivado del VRP tradicional, denominado FSMVRPTW (The Fleet Size and Mix Vehicle Routing Problem with Times Windows); El cual busca determinar un conjunto de rutas que partan y retornen a un mismo punto o depósito, las cuales deben ser seguidas por una flota de vehículos heterogénea con diferentes capacidades y costos. Cada cliente tiene una demanda conocida y debe ser servido por exactamente un vehículo, dentro de un intervalo de tiempo preestablecido por el mismo [10]. Además de esto para nuestra investigación asumiremos Hard Time Window, es decir, el intervalo de tiempo indicado por el cliente no puede ser violado bajo ninguna circunstancia [12].

La Metaheurística Viral System se aplicará al problema descrito y tendrá como objetivo minimizar el costo y el tiempo total de la operación.

BIBLIOGRAFÍA

[1] John E. Bell, Patrick R. McMullen. Ant Colony Optimization for the Vehicle Routing problem. Advance Eingeneering Informatics 18 (2004) 41- 48

[2] Dantzig, G., Ramser, J.: The truck dispatching problem. Management Science 6 (1959) 80–91

[3] C. Miller, A. Tucker, R. Zemlin: Integer programming formulation of traveling salesman problems. Journal of the ACM 7 (1960) 326–329

[4] Clarke, G., Wright, W.: Scheduling of vehicles from a central depot to a number of delivery points. Operations Research 12 (1964) 568–581

[5] Golden, B., Assad, A., Levy, L., Gheysens, F.: The fleet size and mix vehicle routing problem. Computers & Operations Research 11 (1984) 49 – 66

[6] Cordeau, F., Desaulniers, G., Desrosiers, J., Solomon, M., Soumis, F.: The VRP with time windows. Technical Report Cahiers du GERAD G-99-13, École des Hautes Études Commerciales de Montréal (1999)

[7] The Vehicle Routing Problem (2002). Paolo Toth, Daniele Vigo. Capitulo 1: An overview of The Vehicle Routing Problem. 10-22. Capitulo 6: Metaheuristic for the capacited VRP. M. Gendreau, G. Laport, J-Y Potvin. 130-133,146.

[8] Liu, F.H., Shen, S.Y., 1999. The fleet size and mix routing problem with time windows. Journal of the Operational Research Society 50 (7), 721–732. (1999)

[9] Alfredo Olivera 2004: Heurísticas para Ruteo de Vehículos. 10-49

[10] P.P. Repoussis, C.D. Tarantilis. Solving The Fleet Size and Mix Vehicle Problem with Times Windows via Adaptive Memory Programmig. Transportation Research Part C (2009)

[11] Olli Bräysy a, Pasi P. Porkka b, Wout Dullaert c,d, Panagiotis P. Repoussis e, Christos D. Tarantilis(2008). A Well scalable Metaheuristic for The Fleet Size and Mix Vehicle Routing Problem with Times Windows.

[12] Column Generation Book (2005). Guy Desaulniers, Jacques Desrosiers and Marius M. Solomon. Capítulo 3: The Vehicle Routing Problem with Times Windows. 67.