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:

Algoritmo de Resolución

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:

  1. apertura del árbol en cada uno de sus niveles
  2. cantidad de niveles del mismo
  3. 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.


Ejemplo

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