Ejemplo clásico del Viajante de Comercio
El Problema del Viajante de Comercio
Modelo Matemático del Viajante de Comercio
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 |
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
Ejemplo de la fábrica de llantas
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.
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.
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