1

I'm attempting to create an 'optimum' route that starts/ends at the same point and is (close to) X distance long, as opposed to just the absolute optimal route. For example, assuming my cost is a score of how scenic a road is; find the 'most scenic' drive possible from this location that is 25km long, or 50km long. Essentially I want to optimize the cost over the given distance, not find the overall optimal cost. This is perhaps a two part question:

  1. What algorithm should I use? pgr_ksp will allow me to find the 'K' best routes, which I can then use to select the one closest to X length. However, in some cases this takes a very long time to run as it requires K to be a very large value to get a long enough path.

  2. How can I use the same point as the start/end? Right now I am just using the two closest nodes as start/end nodes for testing purposes, but ideally the solution would start/end at the same node. Is this possible without inserting a new node and running pgr_createTopology again?

Improve this question
2
  • Find N nodes at approximately half distance from start. Go start to 1st point. Make traveled edges very heavy. Travel back. Repeat N times.
    – FelixIP
    Commented Oct 18, 2022 at 21:42
  • Hi @FelixIP - care to expand your comment into a full answer? Or at least clarify a bit what you mean by 'make traveled edges very heavy'? I think I understand the concept, but a bit more detail couldn't hurt.
    – Darren Cope
    Commented Oct 19, 2022 at 18:58

1 Answer 1

Reset to default
0

Graph shows road network and my aim is to create 9000 loop route. For that we can explore all nodes that 'slightly' further away than 4500 m. So pick one and find best route to it from START:

enter image description here

Backup and temporarily remove edges of that route from the graph and recalculate best route between same 2 nodes:

enter image description here

Merge new route with backup to store first computed option (9800 m total, so 4000 m threshold was too high!):

enter image description here

Restore edges, repeat with next candidate. Note if your START-FINISH node is dangling, removing edges won't work. So simply increase weight of travelled edges significantly (this is what I called make edges very heavy).

See also Creating laps... post

Improve this answer
2
  • Thanks @FelixIP - this is great and looks like it might work quite nicely. Do you have some code for this? I am pretty new at this, and while your concept is simple, it seems the implementation is not (for me!) I am able to select all possible end nodes within ~half the distance, and I can run the first 'shortest path' from there, but to then to do the 'backup' and 'temporarily remove' edges, and run again stage, and then run again on the next candidate--I am not sure where to even begin!
    – Darren Cope
    Commented Oct 20, 2022 at 16:23
  • I work with ArcGIS and use Python networkx module. Do you have all these? If so post new question and show some efforts using code I mentioned. Algorithm works well. Few years back I developed 50+ laps for tourist agency and for work worth few K they paid me $35.
    – FelixIP
    Commented Oct 20, 2022 at 19:42

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.