1

I used to use Dijkstra to find the shortest path between two points. Now I have a shortest route, which uses a street forbidden to use because of internal rules (too slow due to shopping mall).

Now I would like to add a stopover on an alternative road and use a two segments Dijkstra. Is this the best way or should I better work with a turn-restriction network? The latter allows to set the costs for the shortest path / the street in question higher as usual.

The TSP is currently only implemented with Euclidian distance - this is not accurate enough for European street layouts.

Improve this question
4
  • if it's forbidden why not just take it out of the calculation. Dijkstra's algorithm adapts easily to cost/impedance so you could weight this one heavily so that it's only chosen if it's the only way to get there; then this would give you an option to light weight preferred paths like better/multi-lane roads, such that even if it's not the shortest path a preferred route will be traversed. Perhaps default each line at 1 (for 1 x length) and go 100 for forbidden paths and 0.9 for preferred routes and see how that works out.
    – Michael Stimson
    Commented May 17, 2014 at 11:26
  • Ok, it is forbidden for the standard route. Nevertheless, it should still be accessible. If I had increased the costs of the edge, I would change the original data and risk increased traveling times in this area. It is possible, but there must be a nicer way keeping the original network untouched...?
    – Frank
    Commented May 17, 2014 at 11:48
  • Ok, I made a simple manual select ... where gid in (x,y) inside the routing statement.
    – Frank
    Commented May 17, 2014 at 14:59
  • Please use the edit link on your question to add additional information. The Post Answer button should be used only for complete answers to the question.
    – Paul
    Commented May 17, 2014 at 15:25

1 Answer 1

Reset to default
2

TSP has 2 alternative ways to be called: one uses the euclidean distance as you said, the second one requires a distance matrix as the first argument:

SELECT seq, id FROM pgr_tsp('{{0,1,2,3},{1,0,4,5},{2,4,0,6},{3,5,6,0}}'::float8[],1);

 seq | id
-----+----
   0 |  1
   1 |  2
   2 |  3
   3 |  0
(4 rows)

It's up to you how to calculate the distance matrix. If you have many stop points, pgRouting's shortest path functions might not be fast enough.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.