• Unsupported versions:

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

The travelling salesperson problem (TSP) asks the following question:

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 and 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\).

  • Now since the travel costs do not depend on the direction taken around the tour:

    • este número por 2

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

General Characteristics

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

  • Metric Algorithm is used

  • Implementation generates solutions that are twice as long as the optimal tour in the worst case when:

    • Graph is undirected

    • Graph is fully connected

    • Graph where traveling costs on edges obey the triangle inequality.

  • On an undirected graph:

    • The traveling costs are symmetric:

    • Traveling costs from u to v are just as much as traveling from v to u

Ver también

Referencias

Índices y tablas