## pgr_TSP

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

• Version 2.3.0

• Signature change

• Old signature no longer supported

• Version 2.0.0

• Official function

### Description

#### Problem Definition

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

Given a list of cities and the distances between each pair of cities, which is the shortest possible route that visits each city exactly once and returns to the origin city?

#### 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

• Can be Used with Cost Matrix - Category functions preferably with directed => false .

• With ``` directed => false ```

• Will generate a graph that:

• is undirected

• is fully connected (As long as the graph has one component)

• all traveling costs on edges obey the triangle inequality.

• When ``` start_vid = 0 OR end_vid = 0 ```

• The solutions generated is garanteed to be twice as long as the optimal tour in the worst case

• When ``` start_vid != 0 AND end_vid != 0 AND start_vid != end_vid ```

• It is not garanteed that the solution will be, in the worse case, twice as long as the optimal tour, due to the fact that end_vid is forced to be in a fixed position.

• With ``` directed => true ```

• It is not garanteed that the solution will be, in the worse case, twice as long as the optimal tour

• Will generate a graph that:

• is directed

• is fully connected (As long as the graph has one component)

• some (or all) traveling costs on edges might not obey the triangle inequality.

• As an undirected graph is required, the directed graph is transformed as follows:

• edges (u, v) and (v, u) is considered to be the same edge (denoted (u, v)

• if ``` agg_cost ``` differs between one or more instances of edge (u, v)

• The minimum value of the ``` agg_cost ``` all instances of edge (u, v) is going to be considered as the ``` agg_cost ``` of edge (u, v)

• Some (or all) traveling costs on edges will still might not obey the triangle inequality.

• When the data is incomplete, but it is a connected graph, the missing values will be calculated with dijkstra algorithm.

### Signatures

Summary

```pgr_TSP(Matrix SQL, [start_id], [end_id])
RETURNS SETOF (seq, node, cost, agg_cost)
```

Example: Using pgr_dijkstraCostMatrix to generate the matrix information

• Line 5 Vertices 15 to 18 are not included because they are not connected.

``` 1SELECT * FROM pgr_TSP(
2  \$\$
3  SELECT * FROM pgr_dijkstraCostMatrix(
4    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
5    (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 14),
6    directed => false)
7  \$\$);
8 seq  node  cost  agg_cost
9-----+------+------+----------
10   1     1     0         0
11   2     2     1         1
12   3     3     1         2
13   4     4     1         3
14   5     9     1         4
15   6    12     1         5
16   7     6     2         7
17   8     5     1         8
18   9     8     1         9
19  10     7     1        10
20  11    10     3        13
21  12    11     1        14
22  13    13     2        16
23  14     1     4        20
24(14 rows)
25
```

### Parameters

Parameter

Type

Default

Description

Matrix SQL

``` TEXT ```

An SQL query, described in the Matrix 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

### Inner query

#### Matrix SQL

Matrix SQL : an SQL query, which should return a set of rows with the following columns:

Column

Type

Description

start_vid

``` ANY-INTEGER ```

Identifier of the starting vertex.

end_vid

``` ANY-INTEGER ```

Identifier of the ending vertex.

agg_cost

``` ANY-NUMERICAL ```

Cost for going from start_vid to end_vid

### Result Columns

Returns SET OF ``` (seq, node, cost, agg_cost) ```

Column

Type

Description

seq

``` INTEGER ```

Row sequence.

node

``` BIGINT ```

Identifier of the node/coordinate/point.

cost

``` FLOAT ```

Cost to traverse from the current ``` node ``` to the next ``` node ``` in the path sequence.

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

agg_cost

``` FLOAT ```

Aggregate cost from the ``` node ``` at ``` seq = 1 ``` to the current node.

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

Example :

Start from vertex \(7\)

• Line 9 ``` start_vid => 7 ```

``` 1SELECT * FROM pgr_TSP(
2  \$\$
3  SELECT * FROM pgr_dijkstraCostMatrix(
4    'SELECT id, source, target, cost, reverse_cost FROM edge_table',
5    (SELECT array_agg(id) FROM edge_table_vertices_pgr WHERE id < 14),
6    directed => false
7  )
8  \$\$,
9  start_id => 7
10);
11 seq  node  cost  agg_cost
12-----+------+------+----------
13   1     7     0         0
14   2     8     1         1
15   3     5     1         2
16   4     2     1         3
17   5     1     1         4
18   6     3     2         6
19   7     4     1         7
20   8     9     1         8
21   9    12     1         9
22  10    11     1        10
23  11     6     1        11
24  12    10     2        13
25  13    13     1        14
26  14     7     4        18
27(14 rows)
28
```
Example :

Using points of interest to generate an asymetric matrix.

To generate an asymmetric matrix:

• Line 5 The ``` side ``` information of pointsOfInterset is ignored by not including it in the query

• Line 7 Generating an asymetric matrix with ``` directed => true ```

• \(min(agg\_cost(u, v), agg\_cost(v, u))\) is going to be considered as the ``` agg_cost ```

• The solution that can be larger than twice as long as the optimal tour because:

• Triangle inequality might not be satisfied.

• ``` start_id != 0 AND end_id != 0 ```

``` 1SELECT * FROM pgr_TSP(
2  \$\$
3  SELECT * FROM pgr_withPointsCostMatrix(
4    'SELECT id, source, target, cost, reverse_cost FROM edge_table ORDER BY id',
5    'SELECT pid, edge_id, fraction from pointsOfInterest',
6    array[-1, 3, 5, 6, -6],
7    directed => true)
8  \$\$,
9  start_id => 5,
10  end_id => 6
11);
12 seq  node  cost  agg_cost
13-----+------+------+----------
14   1     5     0         0
15   2    -6   0.3       0.3
16   3    -1   1.3       1.6
17   4     3   1.6       3.2
18   5     6     1       4.2
19   6     5     1       5.2
20(6 rows)
21
```
Example :

Connected incomplete data

Using selected edges (2, 4, 5, 8, 9, 15) the matrix is not complete but it is connected

``` 1SELECT source AS start_vid, target AS end_vid, 1 AS agg_cost
2FROM edge_table WHERE id IN (2, 4, 5, 8, 9, 15);
3 start_vid  end_vid  agg_cost
4-----------+---------+----------
5         2        3         1
6         2        5         1
7         3        6         1
8         5        6         1
9         6        9         1
10         9       12         1
11(6 rows)
12
```

Edge (5,12) does not exist on the initial data, but it is calculated internally.

``` 1SELECT * FROM pgr_TSP(
2  \$\$
3  SELECT source AS start_vid, target AS end_vid, 1 AS agg_cost
4  FROM edge_table WHERE id IN (2, 4, 5, 8, 9, 15)
5  \$\$);
6 seq  node  cost  agg_cost
7-----+------+------+----------
8   1     2     0         0
9   2     3     1         1
10   3     6     1         2
11   4    12     1         3
12   5     9     1         4
13   6     5     1         5
14   7     2     1         6
15(7 rows)
16
```

The queries use the Sample Data network.