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
Contenido
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 |
|
0 |
La parte ambiciosa de la implementación utilizará este identificador. |
end_vid |
|
0 |
El último vértice de visita antes de volver a start_vid. |
max_processing_time |
|
+infinity |
Detenga el proceso de recocido cuando se alcance el valor. |
tries_per_temperature |
|
500 |
Número máximo de veces que se busca a un(os) vecino(s) en cada temperatura. |
max_changes_per_temperature |
|
60 |
Número máximo de veces que se cambia la solución en cada temperatura. |
max_consecutive_non_changes |
|
100 |
Número máximo de veces consecutivas que la solución no cambia en cada temperatura. |
initial_temperature |
|
100 |
Temperatura de inicio. |
temperatura_final |
|
0.1 |
Temperatura final. |
factor_de_enfriamiento |
|
0.9 |
Valor entre 0 y 1 (sin incluir) utilizado para calcular la siguiente temperatura. |
aleatorizar |
|
true |
Elija la semilla aleatoria
|
Descripción de las columnas de devolución¶
Devuelve el CONJUNTO DE (seq, node, cost, agg_cost)
Columna |
Tipo |
Descripción |
|---|---|---|
seq |
|
Secuencia de filas. |
node |
|
Identificador del nodo/coordenada/punto. |
cost |
|
|
agg_cost |
|
|