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

...

[pic 2]

La ecuación (1) Corresponde a la minimización de costos totales por visitar los arcos xij. La ecuación (2) corresponde a que cada agente viajero sale del depósito. La ecuación (3) indica que cada agente viajero regresa al depósito. La ecuación (4) garantiza que exactamente un tour ingrese a cada nodo. La ecuación (5) garantiza que exactamente un tour salga de cada nodo. La ecuación (6) incluyen las restricciones de eliminación de subtours de Miller-Tucker-Zemlin.

Resolución del problema de enrutamiento de vehículos con limitaciones de capacidad utilizando un procedimiento metaheurístico de dos fases

Julio Mario Daza

Jairo R. Montoya

Francesco Narducci

El paper en mención plantea la resolución de un problema de ruteo de vehículos considerando las limitaciones de capacidad, lo cual es lo problema real que hay que considerar para nuestro tema de investigación (problema de distribución de piezas a ensamblar para la zapatería). La idea podría ser utilizar un VCRP. EL paper tiene en su contenido distintos métodos/ algoritmos que brindan respuesta a nuestro problema de distribución con distintos problemas derivados del problema del agente viajero que resultan de la combinación de dos algoritmos.

Como antecedentes investigativos podemos considerar:

1.- Problema de ruteo de vehículos (VRP)

A grandes rasgos un problema de ruteo de vehículos (VRP) consiste en, dado un conjunto de clientes y depósitos dispersos geográficamente y una flota de vehículos, determinar un conjunto de rutas de costo mínimo que comiencen y terminen en los depósitos, para que los vehículos visiten a los clientes máximo una vez. Dentro de esta definición, el problema se ubica en un amplio conjunto de variantes:

- CVRP

- MDVRP

- PVRP

2.- Problema del agente viajero (TSP)

El TSP constituye la situación general y de partida para formular otros problemas combinatorios más complejos, aunque más prácticos, como el ruteo de vehículos y la programación de tareas dependientes del tiempo de alistamiento. En el TSP se dispone de un solo vehículo que debe visitar a todos los clientes en una sola ruta y a costo mínimo.

No suele haber un depósito (y si lo hubiera, no se distinguiría de los clientes), no hay demanda asociada a los clientes y tampoco hay restricciones temporales.

Denotaremos por Δ+(i) y Δ–(i) al conjunto de nodos adyacentes e incidentes al nodo i, es decir,

Δ+(i) = {j_V | (i, j)_E} y Δ–(i)={j_V | (j, i)_E}. De manera similar, el conjunto de arcos incidentes hacia el exterior e interior del nodo i se definen como δ+(i) = {(i, j)_E} y δ-(i) = {(j, i) _E}.

3.- Complejidad del TSP y aproximaciones

La mayor parte de los problemas de ruteo de vehículos son generalizaciones del TSP. En ese sentido, puede considerarse el VRP más simple.

No obstante, pertenece a la clase de problemas NP, debido a que tomando una secuencia cualquiera (certificado) ésta podría ser verificada en tiempo polinomial. Además, este problema puede considerarse del tipo NP-completo lo cual puede comprobarse reduciéndose el problema de optimización a uno de decisión mediante un ciclo hamiltoniano de la siguiente manera: dado un grafo G, ¿es posible determinar una ruta a través de todos los nodos de

G una sola vez? (Garey y Johnson, 1979).

El tiempo de cálculo necesario para resolver el TSP se incrementa con rapidez a medida que aumenta el número de ciudades n. En un caso general el número de rutas factibles que debe considerarse es (n – 1)!/2, puesto que hay (n – 1) posibilidades para la primera ciudad después de la ciudad de residencia del agente, (n – 2) posibilidades para la siguiente ciudad y así sucesivamente. El denominador 2 surge porque cada ruta presenta una ruta inversa equivalente con la misma distancia (TSP simétrico).

Así, mientras un TSP con 10 ciudades tiene no menos de 200.000 soluciones factibles que deben ser consideradas, un problema con 20 ciudades tiene alrededor de 1016 soluciones factibles, mientras que un problema con 50 ciudades tiene alrededor 1062

(Hillier y Lieberman, 2001).

3.- Métodos de solución

En la actualidad, la atención se ha centrado más y más en el uso de métodos de optimización combinatoria, debido a la complejidad de estos problemas en la obtención de soluciones óptimas en tiempo polinomial. Estas técnicas se dividen en técnicas de optimización local convencional (heurísticas) y técnicas de optimización local inteligente (metaheurísticas). A diferencia de un enfoque algorítmico “exacto”, un método de optimización no tiene una base de matemática formal que lo sustente, es desarrollado más o menos por intuición (Ignizio y Cavalier, 1994).

La idea más genérica del término heurística está relacionada con la tarea de resolver inteligentemente problemas reales usando el conocimiento disponible (Narducci, 2005). Heurística proviene de una palabra griega con un significado relacionado con el concepto de encontrar y se vincula a la supuesta exclamación eureka de Arquímedes al descubrir su famoso principio (De la Cruz, 2003).