SÍNTESIS DE LA INFORMACIÓN: MAPA MENTAL Y RESUMEN

Solución del problema de múltiples agentes viajeros resuelto mediante técnicas heurísticas

Eliana Mirledy Toro Ocampo, Rubén Iván Bolaños, Mauricio Granada Echeverri

El problema a resolver por el grupo cuatro consta de un problema de distribución de piezas a ensamblar para la zapatería requiere la elaboración de una ruta que visite a cada trabajador una sola vez y que todos los camiones de distribución partan de la misma planta de producción de la empresa, de modo que el kilometraje sea el mínimo. El paper presentado muestra un posible método de solución a este problema (el método de m-agentes viajeros), además que presenta de forma detallada el planteamiento del problema por programación lineal, de esta forma se podrá comparar quizá ambos métodos o se colocarán como antecedentes investigativos, en el camino a encontrar el método que optimice más la cantidad de kilometraje recorrido, lo que se traduce en reducción de costos para la empresa.

 A continuación se desarrollarán los puntos más importantes que se van a extraer para la investigación.

1.- El transporte en la cadena de suministro

Los clientes demandan tiempos de entrega más rápidos y más precisos; debido a ello las empresas deben contar con un sistema formal de planeación estratégica que le permita tomar las decisiones oportunas mediante la utilización de técnicas y métodos de planificación por medio del manejo de información actualizada a lo largo de cada eslabón de su cadena logística. La importancia que representa para las empresas contar con un buen sistema de transporte que garantice el suministro oportuno de insumos así como también la entrega en el tiempo y lugar requerido por sus clientes.

En cualquier red de distribución hay aspectos importantes como:

i) Hacer que los productos o servicios estén disponibles para los consumidores.

ii) Cumplir con las cuotas de ventas determinadas en unidades monetarias y/o en número de clientes atendidos.

iii) Eliminar los problemas relacionados con la distribución. Tales como tamaño de los vehículos, tiempos de entrega, etc.

iv) El nivel de servicio de los clientes debe ser mejorado continuamente.

v) Los costos generales y logísticos deben ser minimizados.

Vi) El intercambio de información debe ser preciso y oportuno para generar planes de contingencia.

vii) Ubicación de los depósitos centrales. Se debe tener en cuenta que en ellos se realizan las actividades de cargue y descargue de mercancías.

1.1.-  Tipologías de las rutas

Pétalo o moño: Cada vehículo atiende consumidores específicos. Normalmente se utiliza para clientes dispersos con menos demanda que la del vehículo asignado.

Radial: Cada vehículo atiende uno o un limitado número de consumidores .Usualmente se usa para consumidores con gran demanda (cercana o igual a la capacidad del vehículo).Volumen de demanda medio y alto.

Periférico: Cada vehículo atiende a clientes dispersos geográficamente con gran densidad de demanda (áreas o ejes comerciales).Volumen de demanda medio y bajo.

2.- Problema de m-TSP

El problema del m-TSP puede definirse un grafo completo G= (V, A), donde V es un conjunto compuesto por n+1 vértices y A={(i,j): i,j ÎV, i ¹ j} el conjunto de arcos. El vértice cero hace referencia al depósito o ciudad de origen donde los m agentes viajeros (vehículos) están ubicados. Para cada arco (i,j)ÎA existe un costo Cij=dij, donde dij corresponde a la distancia entre los nodos i y j. La solución del problema consiste en encontrar las rutas de los m agentes viajeros, teniendo en cuenta que cada ruta empieza y termina en el depósito y además cada nodo puede ser visitado una única vez, el objetivo es minimizar el costo total de visitar todos los clientes.

El m-TSP puede ser utilizado para resolver las variantes del problema de ruteamiento de vehículos, entre ellos calcular el mínimo número de vehículos requeridos para atender un conjunto de clientes en el problema de VRP que tiene en cuenta restricciones de distancia

2.1.- Aplicaciones del problema m-TSP y conexiones con otros problemas.

Las aplicaciones del m-TSP aparecen principalmente en varios problemas de ruteamiento y programación, algunas aplicaciones reportadas en la literatura se presentan:

1. Programación de impresión de periódicos
2. Ruteamiento de rutas escolares
3. Problema de programación de grupos o tripulaciones
4. Problema de programación de entrevistas
5.  Diseño del sistema global de navegación por satélite

2.2.-  Formulación matemática

Se considera un grafo G= (V, A) donde V es el conjunto de nodos y A es el conjunto de arcos. A cada arco (i,j)ÎA, se le asocia un costo o una distancia cij . Se asume que el depósito se encuentra ubicado en el nodo 0 y que hay m agentes viajeros en el mismo. Se define una variable binaria xij que toma el valor de 1 si el arco (i,j) es incluido en el tour y toma el valor de 0 en caso contrario. Para cada sub-tour se consideran restricciones de eliminación, se define una variable entera μi que indica la posición del nodo i en el tour, adicionalmente se define un valor p que indica el máximo número de nodos que pueden ser visitados por cada agente viajero.

...