6

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?

Improve this question
5
  • 1
    Interesting. Can you tell us what the end application is? I'm intrigued to know a scenario where quickest is not best.
    – Mark Ireland
    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.
    – RichW
    Commented Mar 2, 2011 at 18:22
  • 1
    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.
    – whuber
    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.
    – whuber
    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.
    – RichW
    Commented Mar 3, 2011 at 9:09

1 Answer 1

Reset to default
4

In general terms, you're dealing with a Knapsack problem by trying to choose route legs (based on time) to add up to a specific time [rather than finding the fastest/shortest routes]. Look online for Dynamic and Greedy algorithms for Knapsack to help optimize the speed, otherwise it's NP-complete and you're looking at exponential run time.

Improve this answer
8
  • Interesting concept! I'm struggling to visualise it though, with the knapsack problem you specify boxes, their constraints and values. Presumably the constraint in this case would be time required of the route leg. However, I'm not sure what the value would be. Also, I assume you have to link the boxes together to represent they are route legs that link together - or would you just run one instance of the algorithm for each route? Hope that makes sense!
    – RichW
    Commented Mar 2, 2011 at 18:59
  • whuber above gave you 1 example of a "greedy" algorithm. Basically pick a strategy and run with it and deal with imperfect results. Comparing your problem to Knapsack - Your constraint is the "desired total time" e.g. 3 hrs. Then you have to start rummaging around with your "trip legs" and find individual ones "aha, this 20 min leg + that 50 min leg" and so on until it adds up to your constraint. Of course all of this has to be checked at the end if it's a valid route.
    – Vadim
    Commented Mar 2, 2011 at 20:18
  • Here's another greedy algorithm. Say you know the # of stops for your trip [assuming there are stops]. Then start picking up legs/edges that are closest to the average leg time. E.g. Target time = 3 hrs with 7 stops/vertexes (where each stop = 0hrs). Then start looking for legs that are closest 3hrs/(7-1) = 30 mins. Pick up 6 legs, make a connected non-cyclical graph and time should be close. You also have a slew of other issues - circular graphs ok? Are the paths directed or not? You might have an easier time finding an algorithm if you think of the problem in terms of graph theory.
    – Vadim
    Commented Mar 2, 2011 at 20:28
  • 1
    @Vadim This is simpler than a knapsack problem, because (unless stated otherwise) a leg of a route can be traversed more than once and one can wait at vertices. The method I gave is not greedy (the shortest route is usually not found with a greedy algorithm); it merely points out that--unless the problem is made more precise--the total time is a continuous surjective function from the path space onto an infinite interval of real values and therefore has at least one solution (and in fact infinitely many).
    – whuber
    Commented Mar 2, 2011 at 20:43
  • Another reason this is not a knapsack problem is that the selected legs must form a contiguous (directed) route. It therefore is easy, and asymptotically tractable, to perform a systematic search for solutions. This problem does not look NP complete at all.
    – whuber
    Commented Mar 2, 2011 at 21:58

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.