# Best routing algorithm for this scenario

Trying to work out the most appropriate routing algorithm to use for this situation. Even better if it's available as part of pgrouting or similar..

Here's the requirements:

• Specified date/time for start point
• Specified date/time for end point
• Constant speed of travelling
• Possibility for a few additional minutes added per hour of travelling
• Take into account impedences/weights of certain routes
• The number of stages / legs doesn't matter
• Preferable not to retraverse stages / legs but can be done if required
• Start / end point could be the same
• The algorithm should return the top 3 matching routes (if possible)

The idea is that the routing algorithm would work out a near optimal route to take that will take from the start time until the end time. So for example, if the start time is 9am and the finish time is 12pm then a 3hr3min route would take preference to a 2hr route.

Any thoughts?

• Interesting. Can you tell us what the end application is? I'm intrigued to know a scenario where quickest is not best. Commented Mar 2, 2011 at 18:12
• I've got to be careful what I say as I don't want to give away the full project. It's basically travelling for enjoyment rather than for a purpose. Commented Mar 2, 2011 at 18:22
• Find an optimal route first to assure you can actually make it from start to finish in the allotted time. Then just go proportionately slower at each step! If you can't slow down (e.g., a minimum speed limit), then simply wait between stages along the route. If these kinds of solutions are unsatisfactory, that implies you have additional criteria in mind which you should disclose. Commented Mar 2, 2011 at 19:03
• How do you reconcile the "constant speed of traveling" with "tak[ing] into account impedances"? These seem like contradictory requirements. Commented Mar 2, 2011 at 21:54
• Good concept, but I'm not sure on the idea of slowing down or waiting at each stage.. the travelling should be constant and consistent. In regards to the constant speed of travelling vs. impedances, an impedance might be that one type of road is preferred to another, but the travelling speed can be the same. An example of this could be a horse walking down a road, but it'd prefer to do walk down a muddy path. Commented Mar 3, 2011 at 9:09