Metodos de optimizacion aplicados

[pic 1][pic 2]

[pic 3]

1. Introducción

En la actualidad no es de asombrar que el área de logística y específicamente el área de transporte de las empresas, juegan un rol clave en todas las organizaciones, tal es su importancia que en los últimos 50 años, han surgido formas analíticas - matemáticas para dar solución a todas las problemáticas asociadas. (Morales, 2007), y como para dar solución a estas problemáticas, se encuentran las empresas que se dedican a realizar servicios de despacho o retiro de pedidos, las cuales deben analizar un sinfín de variables para hacer eficientes sus procesos, y ahora bien, a esto le debe adicionamos restricciones como especificaciones de geográficas (prohibiciones de tránsito en un horario determinado), distintas rutas, límites horarios de recepción por parte del cliente; entre otros, se obtiene, un sinnúmero de situaciones que no están previstas y que inciden directamente en la planificación de las operaciones, cumplimiento de los objetivos comerciales, aumento de gastos y en el cumplimiento de las necesidades del cliente. (Sitrack, 2019).

Basado en este contexto, el problema de enrutamiento de vehículos, desde ahora VRP por sus siglas en inglés, el cual fue introducido a fines de la década del 50, siendo ampliamente estudiado debido a sus múltiples aplicaciones y alta complejidad. Durante estos años de investigación, han surgido distintas extensiones entre las que destacan: la inclusión de capacidad, la recolección y entrega de pasajeros u objetos, la consideración de ventanas de tiempo y la incorporación de dinamismo en el problema (Bonet Flores, 2018).

Este es el tipo de problema que ha sido abordado, en el presente trabajo enfocado en el artículo “A review of dynamic vehicle routing problem” del autor V. Pillach. Desde el cual se planteará en primera instancia una descripción general de la problemática a estudiar, el modelo matemático asociado para sus posibles soluciones, y finalizando en conclusiones asociadas al estudio, este tema tambien fue descrito por Allan Larsen en su libro The DynamicVehicle Routing Problem, quien propuso ecuaciones que permitían calcular el grado efectivo de dinamisnmo, en problemas de ruteo de vechículos.

En el caso de los problemas de enrutamiento reales, existen diferentes métodos de solución como son los algoritmos heurísticos y los metaheurístico, esto debido a las innumerables restricciones presentes, por lo cual en el presente trabajo se expondrá un supuesto a través del cual se realizará el análisis de la solución de una problemática en base a este contexto dinámico, a través de un método exacto (algoritmo propuesto por Chu-Beasley), y a través del soporte considerando el análisis propuesto por la minería de datos o Data Minning, con el fin de visualizar la complejidad de las soluciones frente problemáticas de enrutamiento dinámico.

1. Definición de la prooblemática

2.1 Definición General

Primero que todo se debe considerar que el problema de ruteo de vehículos (VRP) consiste en, dado un conjunto de clientes, destinos dispersos geográficamente y una flota de equipos, determinar un conjunto de rutas de costo mínimo, procurando que los clientes sean visitados máximo una vez (Daza, Montoya, & Narducci, 2009).

Basada en esta definición, se contemplan dimensiones importantes al momento de aplicar VRP, como evolución y calidad de la información. Entendiéndose como evolución, la evolución de la información y calidad de la información como la posible incertidumbre de los datos. Con ello se identifican 4 categorías de problemas de enrutamiento. (Pillac V. , 2012).  Según como se muestra en la siguiente imagen

[pic 4]

Ilustración 1 Categorías de los problemas de enrutamiento

Fuente: “A review of dynamic vehicle routing problem” (Pillac V. , 2012)

Sin embargo, en este trabajo se realizará un estudio enfocado únicamente al enrutamiento dinámico.

1.  Enrutamiento dinámico

El enrutamiento dinámico de vehículos (DVRP, Dynamic Vehicle Routing Problem), permite analizar los sistemas considerando variables de carácter dinámico, ajustando el ruteo a nuevas restricciones y/o comportamientos del desarrollo en tiempo real (Sánchez, 2015).

En relación a la inclusión del dinamismo en este tipo de problemas. “Se denotará dinámico cuando los datos de entrada del problema se reciben o actualizan en simultáneo con la determinación de las rutas; en caso contrario, si el input del problema es conocido antes de generar las rutas y posteriormente no se modifica, el problema se considera estático. Ejemplos clásicos de dinamismo en los problemas de ruteo, es cuando la información de los clientes se revela únicamente cuando se reciben los llamados, ya sea relacionado con la ubicación del cliente o con la cantidad de producto demandado” (Bonet Flores, 2018).

Otros autores, bajo el contexto de DVRP, definen dinamismo a partir de niveles, caracterizados usualmente por dos variables; la frecuencia de los cambios y la urgencia de las solicitudes. (Sánchez, 2015).

En el caso de los DVRP, algunos parámetros del modelo dependen del tiempo, los cuales son conocidos como TDVRP, Time Dependent Vehicle Routing Problems y VRP, Vehicle Routing Problem. Este tipo de problemas consiste en optimizar las rutas de una flota de vehículos con capacidad fija cuando los tiempos de viaje son restricciones críticas (Guasmayan-Guasmayan & Toro-Ocampo, 2016).

1. Problemática del enrutamiento dinámico

En contraste con el enrutamiento estático de vehículos, el DVRP incluye nuevos elementos que incrementan la complejidad de la toma de decisiones, por lo cual no sólo se intenta minimizar el costo de ruta, si no, que el DVRP contempla otras nociones, tales como nivel de servicio, número de salidas y maximización de utilidad. Además, teniendo en cuenta la noción de respuesta a un cliente, se introduce la definición de tiempo de respuesta, asociado a la reducción de las demoras, en relación a las llegadas y su tasa de servicio. (Muslino, Polimeni, Rindone, & Vitetta, 2013).

...