Make your own free website on Tripod.com

Investigación Operativa

El Viajante de Comercio

 

Ejemplo clásico del Viajante de Comercio

El Problema del Viajante de Comercio

Modelo Matemático del Viajante de Comercio

Ejemplos del Viajante de Comercio

Algoritmos del Viajante de Comercio

 

Ejemplo clásico del Viajante de Comercio

 Un viajante de comercio que vive en Las Lomitas parte de su casa y debe recorrer las ciudades: El Reyuno, San Homero, Cubillos, Dolores y Quilapaguay para hacer sus ventas. Finalmente, debe regresar a su casa. Como tiene varias alternativas para recorrer las ciudades, se quiere encontrar en qué orden debe hacer su recorrido para minimizar el trayecto total recorrido. En el mapa se muestran las ciudades, las rutas existentes y las distancias entre ciudades. A partir de este mapa se construye la matriz de distancias en kilómetros, indicándose con una x (equis) los casos en que no hay rutas que conecten dos ciudades. Obsérvese que en este caso la matriz es simétrica.

 

 

 

Las Lomitas

El Reyuno

San Homero

Cubillos

Dolores

Quilapaguay

Las Lomitas

0

8

x

3

x

4

El Reyuno

8

0

1

5

9

x

San Homero

x

1

0

7

2

21

Cubillos

3

5

7

0

x

3

Dolores

x

9

2

x

0

35

Quilapaguay

4

x

21

3

35

0

Al resolver este problema con Invop, resulta:

Solución óptima o cercana al óptimo

Las Lomitas - El Reyuno - Dolores - San Homero - Cubillos - Quilapaguay - Las Lomitas

Costo= 33

Es decir, que para recorrer todas las ciudades sin pasar más de una vez por cada una, debe recorrer 33 kilómetros.

 

El Problema del Viajante de Comercio

En el viajante de comercio, se tiene una red de nodos, que pueden ser ciudades o simplemente lugares de una ciudad. Se parte de un lugar inicial, y deben recorrerse todos sin pasar más de una vez por cada lugar, volviendo al lugar inicial. Para cada arco, se tiene un valor Cij, que indica la distancia o el costo de ir del nodo i al nodo j.

Se trata de encontrar en qué orden recorrer los nodos de la red, de modo de minimizar la distancia total recorrida.

Dado que en definitiva se busca un circuito o tour completo, es indiferente el lugar que designemos como origen.

Es ciertamente sin sentido para algunas aplicaciones la restricción de que no debe pasarse más de una vez por cada ciudad. Sin embargo, si los nodos representan lugares de una ciudad, no hay razón para pasar dos veces por el mismo lugar, y el problema del viajante de comercio se puede aplicar con todo éxito.

Este problema también se conoce con el nombre del Agente Viajero, y en inglés, Traveling Salesman Problem (TSP).

El problema del viajante de comercio es la base para muchas aplicaciones de reparto de mercadería en una ciudad. Las situaciones reales suelen complicarse con: más de un vehículo de reparto; horarios de reparto impuestos por los clientes; demoras en los lugares de entrega; capacidades en los vehículos, que limitan los recorridos, etc.

 

Modelo Matemático del Viajante de Comercio

Sean n nodos, y Cij la distancia para ir de i a j. Sea también Xij una variable entera tal que:

Xij = 0 si no se pasa por el arco i,j.

Xij = 1 si se pasa por el arco i,j.

Entonces, el modelo matemático es:

 

 

 

 

Las restricciones de la primera sumatoria nos dicen que se debe llegar a todas las ciudades una vez.

Las restricciones de la segunda sumatoria nos dicen que se debe salir de todas las ciudades una vez.

Ejemplos del Viajante de Comercio

El caso del Reparto

Ejemplo de la fábrica de llantas

Secuencia de producción

El Caso de las pinturas

 

El caso del Reparto

La firma Mauro & Co. tiene una casa Matriz y 5 sucursales. Con un solo camión de reparto, debe recorrer, comenzando con la casa Matriz, todas las sucursales y finalizar en la casa Matriz. ¿En qué orden debe recorrerse las sucursales de modo de minimizar la distancia total recorrida?

 

 

Matriz

Suc1

Suc2

Suc3

Suc4

Suc5

Matriz

0

10

2

34

18

12

Suc1

10

0

20

9

11

3

Suc2

2

20

0

12

4

11

Suc3

34

9

12

0

21

5

Suc4

18

11

4

21

0

10

Suc5

12

3

11

5

10

0

 

Ejemplo de la fábrica de llantas

Gomas S.A., fabrica llantas en su planta y tiene almacenes a lo largo del país, uno de los cuales está ubicado en Santa Brígida. De este almacén regional, se hacen entregas semanales a cinco tiendas locales minoristas mediante un camión. Los tiempos de manejo en minutos entre cualquier dos tiendas y entre el almacén regional y cualquier tienda se dan a continuación:

 

 

Almacén

Tienda 1

Tienda 2

Tienda 3

Tienda 4

Tienda 5

Almacén

 

40

55

45

60

65

Tienda 1

 

 

60

55

60

50

Tienda 2

 

 

 

55

70

90

Tienda 3

 

 

 

 

50

70

Tienda 4

 

 

 

 

 

70

 

Determinar si el conductor del camión puede hacer todas las entregas y regresar al almacén en 8 horas, permitiendo 30 minutos para descarga en cada tienda.

 

Secuencia de producción

Química S.A. fabrica seis compuestos diferentes. Debido a economías de escala, cada compuesto es producido una vez durante un día de 24 horas. La ganancia obtenida depende no sólo del compuesto que se produce, sino también del siguiente compuesto producido. Esto ocurre debido a que cada compuesto deja algunas impurezas que afectan la calidad del siguiente compuesto producido. Las ganancias (en dólares) se indican en la siguiente tabla:

 

SEGUIDO DE

COMPUESTO

A

B

C

D

E

F

A

 

250

300

100

X

170

B

250

 

160

X

270

150

C

300

160

 

230

X

140

D

100

X

230

 

220

X

E

X

270

X

220

 

100

F

170

150

140

X

100

 

 

El problema es determinar una secuencia para la producción de los diferentes componentes, de tal modo que la ganancia se maximice.

Suponga que también se necesita producir un nuevo compuesto, G, que no puede producirse inmediatamente antes o después de A. Las ganancias asociadas con los compuestos posteriores a G son las mismas que cuando esos compuestos son posteriores a A. Modifique adecuadamente el problema y determine la nueva secuencia en la cual producir los compuestos que maximicen las ganancias diarias.

 

Caso de las pinturas

Una empresa de pinturas produce cinco colores de pinturas cada mes. Al cambiar de uno a otro color, la máquina mezcladora debe limpiarse y prepararse para el siguiente color. Este tiempo de disposición depende del color que acaba de producirse y del color que se producirá a continuación. Los tiempos de disposición, en segundos, al cambiar entre todas las parejas de colores se muestran en la siguiente tabla:

A

DE

Blanco

Amarillo

Naranja

Rojo

Negro

Blanco

0

150

120

100

110

Amarillo

170

0

110

90

100

Naranja

200

170

0

80

100

Rojo

220

190

100

0

90

Negro

300

210

180

130

0

Determinar la secuencia en la cual producir los cinco colores con el fin de minimizar el tiempo de disposición total.

 

Algoritmos del Viajante de Comercio

El único método que garantiza un óptimo es buscar todos los caminos posibles. Esto conduce a problemas muy grandes, ineficientes desde el punto de vista del tiempo de ejecución. Normalmente, los programas de optimización utilizan métodos heurísticos para resolverlo.

Los métodos heurísticos son algoritmos que no garantizan un óptimo, pero suelen encontrar soluciones aproximadas al óptimo.

En Invop, está implementado:

Heurística de construcción: Inserción más cercana, que parte de un tour inicial elemental: origen a origen, y luego va insertando en el tour el más cercano a cualquiera de los nodos.

Heurística de mejoramiento: Cambio en el orden de todos los nodos, y evaluación del recorrido.

Puede verse una descripción completa de estos métodos en Foulds, L.R., Combinatorial Optimization for Undergraduates . Springer - Verlag. 1984.

Recomendamos ver el excelente programa realizado por alumnos de la Universidad Tecnológica Nacional (Facultad Regional Mendoza), con la descripción del método heurístico implementado en http://atilioranzuglia.tripod.com

 Volver a la página principal