Shortest path through complex vector layer?

Question

I have a vector layer with complex geometry with many dead ends and breaks.

I want to find the shortest path that will go through all segments of that vector.

Here is a sample of how my vector looks like:

I used the pgr_TSP from the pgRouting module, but the result does not satisfy my need. The solution I got really does not seem to be the shortest... The path jumps from one side of the vector to another, and after going through one segment goes back to the previous segment, 50km away. I've tried to prepare the vector data for pgr, but I could make mistakes.

Here is core of the code I used:

    CREATE TABLE TSP_solution_fc AS
    SELECT * FROM pgr_TSP('
    SELECT node_id as id, ST_X(ST_GeometryN(geom, 1)) AS x, 
    ST_Y(ST_GeometryN(geom, 1)) AS y  FROM vertices
    ',34345,38770);

The problem is also that not all segments are connected, ie. I have 100km connected in one area, and 100km ten kilometers away, and I need the path to go through all that.

Also, it requires points as an input, so I densified vertices to 1m distance (from many tries I did, it is the max distance between vertices, otherwise the route will skip parts of my vector on junctions). It is problematic itself because my vector is more than 1200km long, so I have over 1.2 million of points to calculate, and it takes hours to calculate. So I do my attempts only on the 70km part of the vector, but I will have to make it faster somehow at some point.

Ideally, the path would take into account that it is possible to go not only through the vector, but that it can jump from one end of a segment to another close segment, and that sometimes it would be possible to go multiple times through one segment, which sometimes could make the path shorter.

Does anyone have any idea how can I approach this problem?

I'm not a coder, but I can deal with some PostgreSQL (PostGIS especially) and Python commands.

Answer 1

Without a distance matrix, pgr_TSP (or pgr_eucledianTSP for pgRouting > 2.3) returns an euclidean distance calculation between the input points (nodes) geometries, not along the network (note how you only pass in nodes and no edges). Thus the 'jumps' you see in your results; there is no relation to the edge network.
A distance matrix will calculate the actual distance on the network between the input nodes, however there will also be no edge reference in the output when passed to pgr_TSP; you´ll get a similar visual result, albeit with correct cost values. Also, the TSP is defined to visit each input node exactly once, and is therefor unsolvable with your dangling edges.

Now, this would possibly not matter that much if you simply pass all network nodes into the function (do I get you right with this, you want the whole network traversed?)...if I´m not mistaken, you´ll need a computer the size of the Moon to get results in a lifetime...