• Supported versions:

# pgr_TSPeuclidean¶

• `pgr_TSPeuclidean` - Aproximation using metric algorithm.

Availability:

• Version 3.2.1

• Metric Algorithm from Boost library

• Simulated Annealing Algorithm no longer supported

• The Simulated Annealing Algorithm related parameters are ignored: max_processing_time, tries_per_temperature, max_changes_per_temperature, max_consecutive_non_changes, initial_temperature, final_temperature, cooling_factor, randomize

• Versión 3.0.0

• Cambio de nombre de pgr_eucledianTSP

• Versión 2.3.0

• Nueva función Oficial

## Descripción¶

### Problem Definition¶

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

### General Characteristics¶

• This problem is an NP-hard optimization problem.

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

### Characteristics¶

• Duplicated identifiers with different coordinates are not allowed

• The coordinates are quite the same for the same identifier, for example

```1, 3.5, 1
1, 3.499999999999 0.9999999
```
• The coordinates are quite different for the same identifier, for example

```2 , 3.5, 1.0
2 , 3.6, 1.1
```
• Any duplicated identifier will be ignored. The coordinates that will be kept is arbitrarly.

## Firmas¶

Resumen

```pgr_TSPeuclidean(Coordinates SQL, [start_id], [end_id])
RETURNS SETOF (seq, node, cost, agg_cost)
```
Ejemplo

With default values

```SELECT * FROM pgr_TSPeuclidean(
\$\$
SELECT id, st_X(the_geom) AS x, st_Y(the_geom)AS y  FROM edge_table_vertices_pgr
\$\$);
seq | node |      cost      |   agg_cost
-----+------+----------------+---------------
1 |    1 |              0 |             0
2 |    2 |              1 |             1
3 |    8 |  1.41421356237 | 2.41421356237
4 |    7 |              1 | 3.41421356237
5 |   14 |  1.58113883008 | 4.99535239246
6 |   15 |            1.5 | 6.49535239246
7 |   13 |            0.5 | 6.99535239246
8 |   17 |            1.5 | 8.49535239246
9 |   12 |  1.11803398875 | 9.61338638121
10 |    9 |              1 | 10.6133863812
11 |   16 | 0.583095189485 | 11.1964815707
12 |    6 | 0.583095189485 | 11.7795767602
13 |   11 |              1 | 12.7795767602
14 |   10 |              1 | 13.7795767602
15 |    5 |              1 | 14.7795767602
16 |    4 |   2.2360679775 | 17.0156447377
17 |    3 |              1 | 18.0156447377
18 |    1 |  1.41421356237 |    19.4298583
(18 rows)

```

## Parámetros¶

Parámetro

Tipo

Descripción

`TEXT`

An SQL query, described in the Coordinates SQL section

start_vid

`BIGINT`

`0`

The first visiting vertex

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

end_vid

`BIGINT`

`0`

Last visiting vertex before returning to `start_vid`.

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

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

## Consulta interna¶

### Coordinates SQL¶

Coordenadas SQL: una consulta SQL, que debe devolver un conjunto de filas con las siguientes columnas:

Columna

Tipo

Descripción

id

`ANY-INTEGER`

Identifier of the starting vertex.

x

`ANY-NUMERICAL`

y

`ANY-NUMERICAL`

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

Columna

Tipo

Descripción

seq

`INTEGER`

Secuencia de filas.

node

`BIGINT`

cost

`FLOAT`

Coste que se debe recorrer desde el `nodo` al siguiente `nodo` en la secuencia de ruta.

• `0` for the last row in the tour sequence.

agg_cost

`FLOAT`

Costo agregado del `nodo` en `seq = 1` hacia el nodo actual.

• `0` for the first row in the tour sequence.

Ejemplo

Test 29 cities of Western Sahara

This example shows how to make performance tests using University of Waterloo’s example data using the 29 cities of Western Sahara dataset

Creating a table for the data and storing the data

```CREATE TABLE wi29 (id BIGINT, x FLOAT, y FLOAT, geom geometry);
INSERT INTO wi29 (id, x, y) VALUES
(1,20833.3333,17100.0000),
(2,20900.0000,17066.6667),
(3,21300.0000,13016.6667),
(4,21600.0000,14150.0000),
(5,21600.0000,14966.6667),
(6,21600.0000,16500.0000),
(7,22183.3333,13133.3333),
(8,22583.3333,14300.0000),
(9,22683.3333,12716.6667),
(10,23616.6667,15866.6667),
(11,23700.0000,15933.3333),
(12,23883.3333,14533.3333),
(13,24166.6667,13250.0000),
(14,25149.1667,12365.8333),
(15,26133.3333,14500.0000),
(16,26150.0000,10550.0000),
(17,26283.3333,12766.6667),
(18,26433.3333,13433.3333),
(19,26550.0000,13850.0000),
(20,26733.3333,11683.3333),
(21,27026.1111,13051.9444),
(22,27096.1111,13415.8333),
(23,27153.6111,13203.3333),
(24,27166.6667,9833.3333),
(25,27233.3333,10450.0000),
(26,27233.3333,11783.3333),
(27,27266.6667,10383.3333),
(28,27433.3333,12400.0000),
(29,27462.5000,12992.2222);
```

Adding a geometry (for visual purposes)

```UPDATE wi29 SET geom = ST_makePoint(x,y);
```

Getting a total cost of the tour, compare the value with the length of an optimal tour is 27603, given on the dataset

```SELECT *
FROM pgr_TSPeuclidean(\$\$SELECT * FROM wi29\$\$)
WHERE seq = 30;
seq | node |     cost      |   agg_cost
-----+------+---------------+---------------
30 |    1 | 2266.91173136 | 28777.4854127
(1 row)

```

Getting a geometry of the tour

```WITH
tsp_results AS (SELECT seq, geom FROM pgr_TSPeuclidean(\$\$SELECT * FROM wi29\$\$) JOIN wi29 ON (node = id))
SELECT ST_MakeLine(ARRAY(SELECT geom FROM tsp_results ORDER BY seq));
st_makeline
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Visualy, The first image is the optimal solution and the second image is the solution obtained with `pgr_TSPeuclidean`.