Vendedor Viajante - Familia de funciones

  • pgr_TSP -Cuando la entrada se da como información de una celda de matriz.

  • pgr_TSPeuclidean - Cuando lo que entra son coordenadas.

Información general

Definición del Problema

En el problema del vendedor viajante (TSP) hace la siguiente pregunta:

Dada una lista de ciudades y las distancias entre cada par de ciudades, que corresponde con la ruta más corta posible que para visite cada ciudad exactamente una vez y regrese a la ciudad de origen?

Origen

El problema de los vendedores ambulantes fue estudiado en el siglo 18 por matemáticos

Sir William Rowam Hamilton y Thomas Penyngton Kirkman.

Una discusión sobre el trabajo de Hamilton & Kirkman se puede encontrar en el libro Graph Theory (Biggs et al. 1976).

  • ISBN-13: 978-0198539162

  • ISBN-10: 0198539169

Se cree que la forma general del TSP ha sido estudiada por primera vez por Kalr Menger en Viena y Harvard. El problema fue promovido más tarde por Hassler, Whitney & Merrill en Princeton. Una descripción detallada sobre la conexión entre Menger & Whitney, y el desarrollo del TSP se puede encontrar en On the history of combinatorial optimization (till 1960)

Para calcular el número de recorridos diferentes a través de \(n\) ciudades:

  • Dada una ciudad de partida,

  • Hay \(n-1\) opción para la segunda ciudad,

  • Y \(n-2\) opciones para la tercera ciudad, etc.

  • Multiplicando estos juntos obtenemos \((n-1)! = (n-1) (n-2) . . 1\).

  • Ahora, dado que los costos de viaje no dependen de la dirección tomada alrededor del recorrido:

    • este número por 2

    • \((n-1)!/2\).

Características generales

  • Este problema es un problema de optimización NP-duro.

  • Se utiliza el algoritmo métrico

  • La implementación genera soluciones que son el doble de largas que el recorrido óptimo en el peor de los casos cuando:

    • El grafo es no dirigido

    • El grafo está completamente conectado

    • Grafo donde los costos de viaje en los segmentos cumplen con la desigualdad del triángulo.

  • En un grafo no dirigido:

    • Los costos del viaje son simétricos:

    • Los costos del viaje de u a v son tanto como viajar de v a u

Ver también

Referencias

Índices y tablas