• Author / Uploaded
• Jp Vidal

• Categories
• Hormiga
• Optimización Matemática
• Transporte
• Matemáticas Aplicadas
• Áreas de informática

Citation preview

INFORME PROFESIONAL MII 505 Métodos de Optimización Aplicados  Grupo: 1  Integrantes: Luis Navarro – Francisco Pacheco  Fecha: 21/04/2019

Introducción En el transporte urbano uno de los problemas de mayor impacto es la asignación de rutas, esto se debe a las nuevas necesidades comerciales como consecuencia de la globalización y los avances en tecnologías de la información y la comunicación, fomentada en gran parte por la aparición y consolidación del internet, lo que implica una conexión permanente, por lo cual empresas que se dedican al transporte de mercancías deben tener la capacidad de procesar la información en tiempo real. Las redes de transporte de mercancías surgen por la necesidad de conectar y transportar los bienes de consumo desde su punto de producción (localización empresa) hasta el mercado (clientes). Durante la fase de distribución, el conductor puede realizar varias paradas en diversos lugares hasta llegar a su destino final, sin embargo, las ineficiencias de estas redes por las asimetrías de los envíos o su variación temporal puede generar altos costos de transporte e incremento de la insatisfacción del cliente, por ende, la mejora y optimización de las redes de transporte de mercancías y una actualización dinámica de los tiempos de viaje es esencial para la disminución de costos de los viajes. Uno de los problemas más conocidos y ampliamente estudiado, es el denominado “Vehicle Routing Problem” (VRP), o Problema de Enrutamiento de Vehículos en español. Este problema consiste en el reparto de un producto a varios clientes que se encuentran geográficamente dispersos, cada cliente presenta una demanda, se tiene un depósito y una flota de vehículos con capacidad limitada. El objetivo es realizar las entregas en un tiempo requerido con el menor costo posible, en donde cada vehículo sirve una única ruta durante el periodo de planificación, teniendo que iniciar y terminar en un depósito central. Para este informe, se abordará el Sistema de Colonias de Hormigas como estrategia de resolución al Problema de Ruta de Vehículos (VRP), en el cual los clientes tienen localizaciones geográficas distintas durante el tiempo en que se realiza el reparto, permitiendo encontrar un conjunto de recorridos factibles con un mínimo total de viajes, permitiendo que un nodo o ruta se visite sólo una vez.

Descripción del Problema En el “Problema de Enrutamiento de Vehículos” (VPR) el propósito es encontrar una configuración de rutas que reduzca de forma óptima el nivel de pérdidas en el sistema de la distribución, recorriendo el camino total más corto posible. Para esto, algunos de los objetivos que se plantean son: · El despachador comunica periódicamente a los conductores las nuevas visitas asignadas, por ende, el conductor siempre tiene conocimiento sobre los próximos clientes asignados a él. · Los vehículos que han salido del depósito no deben regresar al mismo lugar para tratar los nuevos pedidos asignados por el despachador. · Se tienen en cuenta capacidades y restricciones de los vehículos, lo que permite flexibilizar la entrega de productos y adaptarse mejor a las necesidades de los clientes. · Cuando se comunica un pedido a un conductor, el compromiso no se puede retractar, es decir, una vez que una orden se confirma a un conductor, esta asignación no se puede cambiar. · Entregar solución a todos los pedidos conocidos, aunque aún no se encuentren asignados y comprometidos. · Dividir la jornada laboral en segmentos con igual longitud. · Existe un tiempo límite para los pedidos recibidos, parámetro definido por el usuario, los pedidos no realizados durante ese tiempo se postergan para el siguiente día hábil. · Existe un tiempo de compromiso avanzado, en donde cada orden debe comprometerse con un conductor, el cual tiene un tiempo de reacción adecuado entre los diversos pedidos asignados. La aplicación de la metaheurística sobre la optimización basada en el “Sistema de Colonia de Hormigas”, la cual se inspira en el comportamiento que rige a las hormigas para encontrar los caminos más cortos entre las fuentes de comida y el hormiguero, se ha convertido en un campo de investigación importante a través del cual un gran número de autores han desarrollado modelos para solucionar de manera satisfactoria un gran número de problemas de optimización combinatoria. Un aspecto interesante del comportamiento de las hormigas, teniendo en cuenta que no poseen sentido visual, es su habilidad por encontrar los caminos más cortos entre sus hormigueros y las fuentes de alimento, esto se debe a que mientras se mueven depositan una sustancia química denominada feromona. Mientras mayor sea la cantidad de feromona depositada en el terreno, mayor es la tendencia se seguir el rastro, estableciéndose un medio de comunicación que hace que el comportamiento global del hormiguero tenga características inteligentes de optimización.

Por su parte, los algoritmos de hormigas (Ant Colony Optimización) son esencialmente algoritmos constructivos: en cada iteración del algoritmo, cada hormiga construye una solución al problema recorriendo un grafo de construcción. El modo de funcionamiento se resume así: se inicia el algoritmo colocando una hormiga en cada nodo, para la construcción de caminos se utiliza una regla probabilística que asigna una probabilidad igual a cero si el nodo ya fue visitado y diferente a cero para el caso contrario. La hormiga visita el nodo que tenga una probabilidad mayor. En cada arco se actualiza la feromona y finaliza si se obtiene una solución inferior a una cota preestablecida, de lo contrario se recalculan las probabilidades y la hormiga sigue construyendo soluciones. Figura del problema EL VPR puede ser representado con nodos los cuales representan los clientes que necesitan ser visitados y en la ruta los vehículos a utilizar partiendo de un nodo inicial (1).Para satisfacer las necesidades de mejor manera y evitar perdidas se deben asignar rutas altamente eficientes, es decir un modelo ordenado logrando así la minimización de costos principalmente por el correcto enrutamiento de los vehículos, consideremos que estos tienen un desgaste y una depreciación a medida que pasa el tiempo, como también hay costos directos de combustible y salarios de conductores. Para el VPR debemos buscar una solución para lograr Low Cost. Figura Nodo Clientes

de Autor desconoc ido estáá bájo licenciá

DEPOSITO

de Autor desconoc ido estáá bájo licenciá

de Autor desconoc ido estáá bájo licenciá

Aquí se representa una figura clásica del VRP, donde un depósito central se asignan camiones para atender las rutas que llevan a los clientes (12) y su regreso al depósito. Desde al deposito hasta al cliente (Nodo) hay una distancia X la cual se debe considerar a la solución del VPR teniendo en cuenta que estas son todas diferentes, lo cual impacta en variables de tiempo, Kilometraje, geografía, capacidades, asignación y prioridades. EL VRP en un problema de gran complejidad (NP) por lo cual se proponen variados métodos para encontrar la solución mas optima considerando exactos y aproximados Métodos heurísticos son empleados como aproximados para la solución compleja del VRP, cabe destacar que la heurística no son garante de la solución óptima, pero si otorga una buena solución al problema. Para este caso los llamaremos algoritmo de enjambre basado en e comportamiento de colonias de insectos. El algoritmo inicia con una solución factible de las rutas deseadas y con la comparación de otras rutas factibles donde se debe rescatar la mejor teniendo en cuenta el objetivo de minimizar de cotos sin dejar desatendidos a los clientes, la repetición de estos algoritmos suele ser repetitivo hasta encontrar la solución mas optima bajo las condiciones establecidas para la resolución del problema (Variantes) Solucioá n 1

Solucioá n 2 5

7

7

8

1

6

5

2

5

2 3

4

Ambas soluciones pueden ser factibles y optimas

6

1

3

4

MODELO MATEMATICO Heurística ¿Como llegamos a H más rápidamente con menos costo partiendo desde A?

17

8 4

E

B

G 20

A

KM 9

15

12

D H

3

C

NODOS CLIENTES

2

4

22 F

En respuesta a la pregunta SOLVER nos dice que la mejor ruta es A-C-F, minimizando la distancia a 29 KM. Al encontrar la mejor ruta minimizo costos de traslados.

MODELANDO

CONCLUSIONES VRP es un problema latente y relevante que se genera cuando buscas procesos y operaciones eficientes, si bien diversos autores (B. Chen, et. al, “Un sistema de colonias de varias hormigas para problemas de enrutamiento de vehículos con tiempos de viaje dependientes del tiempo” IEEE International),(B. Yu et. al, "Una optimización mejorada de la colonia de hormigas para el problema del enrutamiento de vehículos" European Journal of Operational Research vol. 196, Número 1, (julio de 2009), págs. 171-176), han presentado métodos de solución estos también son acompañado de modelos matemáticos, cabe señalar que el apoyo de la tecnología actual también conlleva a asumir costos computacionales. La heurísticaaplicada en este problema más el apoyo tecnológico aporta unasolución no del todo óptima, pero es aceptable y de buena calidad en un tiempo aceptable. Debemos explorar diversas combinaciones que no generen posibilidad de minimizar la complejidad del problema con variadas y mejores soluciones que presentan diversos autores quienes presentan métodos, quienes buscan la solución mas optima incluyendo las variantes y restricciones al problema VRP el cual hasta nuestros días sigue siendo un problema abierto, el cual busca día a día con apoyo de la computaciónel mejoramiento de algoritmos que entreguen una solución óptima.