Ruteo

Problema del viajero de negocios (TSP)

Traveling Salesman Problem (TSP)

Consideraciones generales…
Varios problemas de optimización no pueden ser resueltos usando métodos exactos, es decir, no es posible encontrar su solución óptima con esfuerzos computacionales aceptables aunque se pueda contar con computadores de alta velocidad operando en paralelo. Un gran problema de la optimizaciónes el fenómeno llamado explosión combinatorial, que significa, que cuando crece el número de variables de decisión del problema, el número de decisiones factibles y el esfuerzo computacional crecen en forma exponencial. Dentro de estos problemas combinatoriales se encuentra el problema TSP. Los problemas combinatoriales pueden ser divididos en dos grandes grupos considerando la existencia dealgoritmos polinomiales para resolver cada tipo de problema:
– Problema tipo P (polinomial) – Problema tipo NP (no polinomial)

Clasificación del problema TSP
Se pueden plantear dos tipos de TSP: simétrico y asimétrico. TSP Simétrico: La distancia de i a j es la misma que la distancia de j a i.

TSP Asimétrico: La distancia son distintas dependiendo de la ciudad de partida.

ComplejidadComputacional del TSP
• En un problema de TSP Simétrico, si solo hay dos ciudades el problema es trivial, ya que solo un tour es posible. Para el caso simétrico un TSP de 3 ciudades es también trivial!!!. Si todas las conexiones están presentes entonces hay (n-1)! Tours diferentes para un TSP asimétrico con n ciudades. Si tomamos cualquier ciudad como la primera- entonces hay n-1 opciones para elegir lasegunda ciudad visitada, n-2 para la tercera, etc. Para el caso simétrico tenemos solo la mitad de las distintas soluciones (n-1)!/2 para un TSP de n ciudades, así que la búsqueda exhaustiva es impráctica.

•

•

Complejidad Computacional del TSP (2)
Se podrá enumerar las siguientes soluciones y encontrar la mejor? • • • • • • • 5 ciudades ≈≈ 24 posibilidades 10 ciudades ≈ 362.000posibilidades. 100 ciudades ≈ 9 x10155 posibilidades. 1,000 ciudades ≈ 9 x102.565 posibilidades. 33,810 ciudades ≈ 10138.441 posibilidades. Edad del universo ≈ 1018 segundos. Número de átomos en el universo: < 10100.

Enumeración solo es posible para problemas muy pequeños!!!!!

El problema TSP
14

14

(1,12)
12

(1,12 )

12

10

10

8

(2,8)

Coordenadas Y

Coordenadas Y(6,8)

(2,8)
8

(6,8)

(-3,7)
6

(-3,7)

6

4

(4.5,5)

(4.5,5)
4

2

2

(0,0)
0 -4 -3 -2 -1 0 1 2 3 Coordenadas X 4 5 6 7

0 -4 -3 -2 -1

(0,0)
0 1 2 3 Coordenadas X 4 5 6 7

Ruta deficiente (hay cruces): Distancia total = 37.4454

Ruta mejorada (no hay cruces): Distancia total = 35.0540

The Travelling Salesman Problem
A continuación se muestra la distanciaentre 9 lugares. Cual será el tour mas corto? 1 1 2 3 4 5 6 7 8 2 41.0 3 53.0 25.8 4 5 6 62.9 106.3 86.2 17.1 69.6 60.8 31.9 67.3 72.3 53.9 44.2 37.0 7 78.2 48.2 57.9 31.2 32.5 14.5 8 74.5 46.6 58.6 29.9 37.6 14.3 5.1 9 47.7 36.4 59.3 28.8 67.0 39.5 35.0 30.2

90

The TSP, Best Solution =284.3
5 3

60 North
2 4 8 7 6

30
9 1

0 0 30 East 60 90

Problema de Asignación (AP)...un paso alTSP
Indices: Parameters: Variables: Model AP: i = teacher, j = course. cij = value if teacher i is assigned to course j. xij = 1 if teacher i is assigned to course j, else 0. 1) Max ∑i ∑j cijxij subject to 2) ∑j xij = 1, for all i, 3) ∑i xij = 1, for all j, 4) xij ∈ {0,1}, for all i,j. Explanation: 1) Maximise value of assignments. 2) Assign each teacher i to one course. 3) Assign each course jto one teacher. Almost the TSP. Is AP a possible formulation for the TSP? Indices: i, j = city. Parameter: cij = cost to go from city i to city j. Variables: xij = 1 if we drive from city i to city j, else 0.

Problema de Asignación (AP) funciona?

Una solución menor a la encontrada? Sol Anterior = 284.3

Problema de Asignación (AP) funciona?

Las variables de las diagonales son cero....