Viajante de Comercio
Programa de resolución de rutas
Algoritmo
Ejemplo
Créditos
Download
| Investigación Operativa - U.T.N. F.R.M.
El
programa consiste básicamente en:
- asignar lugares por recorrer, teniendo en cuenta que siempre debemos
volver a la ciudad inicial
- establecer pesos a las diferentes rutas, si una fuera muy costosa le
colocamos un número elevado, en cambio, si fuera prohibida le colocamos -1
- establecer unas series de opciones para el cálculo a realizar
El algoritmo es uno nuevo
diseñado por nosotros. Comienza seleccionando un orden de recorrido de las
ciudades al azar y a partir de allí genera un árbol con diversas posibilidades
de intercambios de 2 rutas al azar.
Lo interesante del algoritmo es que es un poco menos susceptible a los
mínimos y máximos locales que la mayoría de los que conocemos. Este algoritmo
puede encontrar una opción de recorrido bastante mala en uno de sus nodos, pero
al seguir eligiendo cambios de rutas al azar a partir del dicho nodo puede
encontrar valores muy cercanos al óptimo.
Cuando genera el árbol completo selecciona la mejor opción y a partir de la
misma comienza con un nuevo árbol.
Podemos establecer una serie de parámetros antes de realizar los cálculos:
- apertura del árbol en cada uno de sus niveles
- cantidad de niveles del mismo
- cantidad de árboles a realizar por el algoritmo
En el primer cuadro que dice árbol colocamos la cantidad de rama que va
a tener en cada nodo de cada nivel.
En el cuadro que dice tamaño
colocamos la cantidad de niveles del árbol.
Y, por último, en el tercer
cuadro colocamos la cantidad de árboles a generar por el
algoritmo.
Vamos a establecer que se generen 8 árboles, cada
uno con 4 niveles de profundidad, 10 ramas en el primer nivel y 2 en los
restantes:
Realizado por:
Néstor Marsollier
Pablo Leónidas Chamorro
Atilio Ranzuglia
David
Abdala