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

The traveling sales person problem was studied in the 18th century by mathematicians 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\).

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

Characteristics

  • 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:

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

TSP optional parameters

Column

Type

Default

Description

start_id

ANY-INTEGER

0

The first visiting vertex

  • When 0 any vertex can become the first visiting vertex.

end_id

ANY-INTEGER

0

Last visiting vertex before returning to start_vid.

  • When 0 any vertex can become the last visiting vertex before returning to start_id.

  • When NOT 0 and start_id = 0 then it is the first and last vertex

Ver también

Referencias

Índices y tablas