Caso aplicativo del Mercader Viajero

...

a) Se comienza con un tour parcial consistente de una unica ciudad a1 elegida arbitrariamente.

b) Si el tour parcial es a1, ..., ak, y ak+1 es la ciudad más cercana a ak entre las que no se encuentran en el tour, se agrega ak+1.

c) Se analiza cuando el tour contiene todas las ciudades.

Teorema: Para cada k ≥ 1, existe una instancia del TSP con n = 2k+1 vértices y un tour óptimo de tamaño 2k+1 a la que al aplicarle el algoritmo codicioso se construye un tour de tamaño (k+4)2k−1 (los costos cumplen con la condición expuesta al comienzo). En otras palabras, la razón entre los tamaños del tour hallado por el algoritmo y el óptimo resulta (3 + log n)/4.

ALGORITMO DE LIN Y KERNIGHAN

Dado un grafo de par G = (V,E) donde V es un conjunto de elementos finitos que llamamos vértices y E es un conjunto de pares de vértices que denominamos ramas. Se buscará desarrollar un ciclo, para una sucesión de vértices u1, u2, u3,..., up tales que u1, u2, u3,…, up-1 son distintos, up = u1 y (ui, ui + 1) ∈ E; al ciclo que contiene todos los vértices presentes en el grafo se le llama Ciclo Hamiltoniano.

[pic 2]

Figura 2

Fuente

Para nuestro caso particular, el TSP para un grafo que tiene asignado para cada una de sus ramas un cierto peso es el problema de encontrar un ciclo Hamiltoniano de mínimo peso, entendiéndose por peso del ciclo a la suma de los pesos de todas las ramas que pertenecen a él.

Para el caso particular de aplicación puede describirse como un problema de optimización que para un conjunto finito E, una función f: E R y una familia F de subconjuntos factibles de E, se quiere encontrar un x ∈ F tal que f(x) sea máximo o mínimo sobre todos los miembros de F.

Para la resolución de problemas del tipo TSP se pueden tener algoritmos cuyo tiempo de ejecución sea rápido o uno que encuentre un tour óptimo, pero no uno que cumpla con ambas condiciones. Por tal motivo emplearemos el algoritmo de Lin y Kernighan que intenta encontrar una solución “buena” en una cantidad de tiempo aceptable.

La estructura general del algoritmo de Lin y Kernighan es la siguiente:

1. Generar al azar una solución factible T, en otras palabras, formar un tour tal que pase por todos los vértices del grafo y retorne al punto de partida.

2. Tratar de encontrar una solución factible mejor T´ por alguna transformación de T

3. Si se encuentra una solución mejor, f(T´)

4. Si no se puede encontrar una solución mejor, T es una solución óptima local

Repetir desde el paso 1 hasta que se termine el tiempo fijado o que la respuesta hallada sea satisfactoria

FORMULACIÓN DEL TPS MEDIANTE PROGRAMACIÓN ENTERA

El modelo básico para la resolución del problema del agente viajero sin considerar heurísticos, parafraseando lo descrito en libro Investigación de Operaciones, Wiston 4ta edición, este plantea lo siguiente.

El problema consiste en la existencia de nodos o “ciudades” 1, 2, 3,…, N; donde Cij es la distancia desde la ciudad i hasta la ciudad jen relación a las distancias reales según sea el caso para todo i distinto de j. Y todo Cii tomará un valor muy grande M para asegurar que el viajero no realizará un viaje a la ciudad i habiendo partido de i.

También se definirá como variable a Xij de tipo binario; donde Xij tomará el valor de 1 en la solución del problema se realiza el viaje del nodo i al nodo j; y el valor de 0 si no sucede así.

Por lo tanto, la solución resulta de resolver

[pic 3]

Como resultado, la función objetivo proporcionará la distancia total del recorrido en el tour. Las primeras restricciones descritas verifican que se debe llegar y abandonar una ciudad. Y las últimas restricciones aseguran que: cualquier conjunto Xij que contiene un subtour será no factible; y que cualquier conjunto Xij que forma un tour será factible.

Este modelo posibilita llegar a una solución pero si se llegará a plantear un problema similar con gran cantidad de nodos no sería de gran utilidad.

Modelo propuesto en Lingo

El modelo siguiente es el propuesto para la resolución de nuestro caso particular de la lavandería.

MODEL:

SETS:

CITY/1..14/:U;

LINK (CITY, CITY): DIST,X;

ENDSETS

DATA:

DIST=

1000000 1000000 1000000 1000000 1000000 5 1000000 8 8 1000000 10 12 1000000 1000000

1000000 1000000 1 2 3 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000

1000000 1 1000000 0.865 1000000 1000000 1000000 1000000 1000000 3 1000000 1000000 1000000 1000000

1000000 2 0.865 1000000 3 1000000 1000000 1000000 1000000 5 1000000 1000000 1000000 1000000

1000000 3 1000000 3 1000000 1000000 7 1000000 1000000 1000000 1000000 1000000 1000000 9

5 1000000 1000000 1000000 1000000 1000000 1000000 4 4 1000000 1000000 1000000 1000000 1000000

1000000 1000000 1000000 1000000 7 1000000 1000000 6 1000000 4 1000000 1000000 4 4

8 1000000 1000000 1000000 1000000 4 6 1000000 2 3 1000000 1000000 1000000 1000000

8 1000000 1000000 1000000 1000000 4 1000000 2 1000000 1000000 1000000 1000000 1000000 1000000

1000000 1000000 3 5 1000000 1000000 4 3 1000000 1000000 1000000 1000000 1000000 9

10 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 2 1000000 1000000

12 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 2 1000000 7 10

1000000 1000000 1000000 1000000 1000000 1000000 4 1000000 1000000