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.

Versiones anteriores de esta página

Información general

Definición del Problema

En el problema del vendedor viajante (TSP) se 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 XVIII 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)

Características

  • Los costes de viaje son simétricos:
    • los costos de viaje de la ciudad A a la ciudad B son tanto como viajar de B a A.
  • Este problema es un problema de optimización NP-duro.
  • 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 bien, dado que nuestros costos de viaje no dependen de la dirección que tomemos alrededor del recorrido:
      • este número por 2
      • \((n-1)!/2\).

Algoritmo de Recocido Simulado

El algoritmo de recocido simulado se inspiró originalmente en el proceso de recocido en el trabajo de metal.

El recocido implica calentar y enfriar un material para alterar sus propiedades físicas debido a los cambios en su estructura interna. A medida que el metal se enfría, su nueva estructura se fija, haciendo que el metal conserve sus propiedades recién obtenidas.

Pseudocódigo

Dada una solución inicial, el proceso de recocido simulado, comenzará con una alta temperatura y se enfriará gradualmente hasta que se alcance la temperatura deseada.

Para cada temperatura, se calcula una nueva solución vecina newSolution. Cuanto mayor sea la temperatura, mayor será la probabilidad de aceptar la nueva solución como posible mejor solución.

Una vez alcanzada la temperatura deseada, se devuelve la mejor solución encontrada

Solution = initial_solution;

temperature = initial_temperature;
while (temperature > final_temperature) {

    do tries_per_temperature times {
        newSolution = neighbour(solution);
        If P(E(solution), E(newSolution), T) >= random(0, 1)
            solution = newSolution;
    }

    temperature = temperature * cooling factor;
}

Output: the best solution

Implementación de pgRouting

La implementación de pgRouting agrega algunos parámetros adicionales para permitir algunos controles de salida dentro del proceso de recocido simulado.

  • max_changes_per_temperature:
    • Limita el número de cambios en la solución por temperatura
    • El recuento se restablece a \(0\) cuando la temperatura cambia
    • El recuento aumenta en :math: 1 cuando la solución cambia
  • max_consecutive_non_changes:
    • Limita el número de no cambios consecutivos por temperatura
    • El recuento se restablece a \(0\) cuando la solución cambia
    • El recuento aumenta en :math: 1 cuando la solución cambia
  • max_processing_time:
    • Limita el tiempo en que se realiza el recocido simulado.
Solution = initial_solution;

temperature = initial_temperature;
WHILE (temperature > final_temperature) {

    DO tries_per_temperature times {
        newSolution = neighbour(solution);
        If Probability(E(solution), E(newSolution), T) >= random(0, 1)
            solution = newSolution;

        BREAK DO WHEN:
            max_changes_per_temperature is reached
            OR max_consecutive_non_changes is reached
    }

    temperature = temperature * cooling factor;
    BREAK WHILE WHEN:
        no changes were done in the current temperature
        OR max_processing_time has being reached
}

Output: the best solution found

Selección de parámetros

No hay una regla exacta sobre cómo se deben elegir los parámetros, dependerá de las características especiales del problema.

  • Si el tiempo de cálculo es crucial, entonces limite el tiempo de ejecución con max_processing_time.
  • Haga el tries_per_temperture dependiendo del número de ciudades (\(n\)), por ejemplo:
    • Es útil para estimar el tiempo que se tarda en hacer un ciclo: use 1
      • esto ayudará a establecer un max_processing_time razonable
    • \(n * (n-1)\)
    • \(500 * n\)
  • Para una disminución más rápida de la temperatura, establezca cooling_factor en un número menor y establezca un número mayor para una disminución más lenta.
  • Cuando para los mismos datos dados se necesitan los mismos resultados, establezca randomize en falso.
    • Al estimar cuánto tiempo se tarda en hacer un ciclo: use false

Una recomendación es jugar con los valores y ver lo que se ajusta a los datos en particular.

Descripción de los Parámetros de Control

Los parámetros de control son opcionales y tienen un valor predeterminado.

Parámetro Tipo Valores predeterminados Descripción
start_vid BIGINT 0 La parte ambiciosa de la implementación utilizará este identificador.
end_vid BIGINT 0 El último vértice de visita antes de volver a start_vid.
max_processing_time FLOAT +infinity Detenga el proceso de recocido cuando se alcance el valor.
tries_per_temperature INTEGER 500 Número máximo de veces que se busca a un(os) vecino(s) en cada temperatura.
max_changes_per_temperature INTEGER 60 Número máximo de veces que se cambia la solución en cada temperatura.
max_consecutive_non_changes INTEGER 100 Número máximo de veces consecutivas que la solución no cambia en cada temperatura.
initial_temperature FLOAT 100 Temperatura de inicio.
temperatura_final FLOAT 0.1 Temperatura final.
factor_de_enfriamiento FLOAT 0.9 Valor entre 0 y 1 (sin incluir) utilizado para calcular la siguiente temperatura.
aleatorizar BOOLEAN true

Elija la semilla aleatoria

  • true: Utilice el tiempo actual como semilla
  • falso: Use 1 como semilla. Usando este valor obtendrá los mismos resultados con los mismos datos en cada ejecución.

Descripción de las columnas de devolución

Devuelve el CONJUNTO DE (seq, node, cost, agg_cost)

Columna Tipo Descripción
seq INTEGER Secuencia de filas.
node BIGINT Identificador del nodo/coordenada/punto.
cost FLOAT
Coste que se debe recorrer desde el nodo al siguiente nodo en la secuencia de ruta.
  • 0 para la última fila de la secuencia de ruta.
agg_cost FLOAT
Costo agregado del nodo en seq = 1 hacia el nodo actual.
  • 0 para la primera fila de la secuencia de ruta.