The goal of routing is usually finding the route with minimum cost. That cost can be distance, time, calories or some other value but still our desire is to find the route that costs least.

But what if I want to find a route with desired cost? Not the fastest route but the route that will take around an hour (let's assume I have an hour to walk from point A to B and I want to see as much on my way there as I can). Or that I want a route that will be around 2 kilometres long.

Using a standard routing algorithm and rejecting the proposed routes until one with desired cost is found will probably lead to something like "Head straight from A to B and then circle around B a few times".

Is there any previous work on this? Does anyone have any ideas?

  • For time: Take the minimum-time route. Stop an instant before arriving at the destination and wait until the desired time has elapsed. Continue to the end. For distance: take the minimum-distance route to the destination, then wander around to make up the desired distance. These solutions are not facetious: they show that the problem is underdetermined. It only becomes a genuine problem with interesting answers once you provide an additional objective function to optimize and express the desired cost as a constraint. What is your objective?
    – whuber
    Sep 17 '13 at 20:07
  • My objective is to create an excercise route that will burn the desired number of calories on the way from point A to point B (or for the time part, send a friend to his b-day party so won't get there before we set everything up yet he won't get suspicious about having to wait or driving around the roundabout 50 times). How about a restriction of not traversing the same edge twice? Sep 17 '13 at 20:20
  • 1
    That restriction may work in some cases. You still have to modify the problem formulation, though, because now typically there will be no solutions. Instead, you might ask to find a non-self-intersecting path from A to B of least cost that is greater than or equal to the target cost. A more flexible and realistic approach is to penalize solutions according to how much they depart from the target cost and then find a solution with the minimum penalty. In your examples I would be tempted to find paths near the target cost that maximize some measure of beauty (the "scenic route"). :-)
    – whuber
    Sep 17 '13 at 20:25
  • If I were to take the most scenic route I'm afraid my route from work to home would lead me on a trip around the world. Hmm...Maybe the key to the problem lies in choosing which nodes we should consider while routing? IF the cost of straight line from A to B is 50 and the desired cost is 200 then obviously no point in the route can be further than 75 from the straight line. That certainly should make for easier computing. Sep 17 '13 at 21:32
  • I didn't propose most scenic without constraints! The idea is most scenic, subject to not exceeding X cost, where you specify "X". Although stipulating key nodes or edges can work, it puts the burden on you to find good key nodes or edges. Posing this as a constrained optimization problem puts all the burden on the computer and thereby allows you to discover unexpectedly good solutions.
    – whuber
    Sep 17 '13 at 21:54

In cost-surface analysis, which is similar to your problem, the goal is to find an optimal route based on minimizing some cost as you traverse a landscape. If you have some factor that is actually beneficial factor, that is you would like to maximize it, then you simply need to express it as a cost factor using the following method:

x' = 1 - (x - xmin) / (xmax - xmin)

In this way, it can be incorporated into the analysis along with any other cost factors.

  • I don't need neither minimum nor maximum. A formula along of cost = abs(1 - (x/desired_cost)) could be used to grade the routes but still I don't have a better idea than: Calculate every possible route, stop when destination is reached or the cost exceeds the cost of current best solution. Continue until the solution has good enough precision. I'll look into cost-surface analysis though in case I missed something, +1. Sep 17 '13 at 16:18
  • I'm not sure what your problem domain is, but if you are working with raster type data then it is likely that you're looking for a cost-surface analysis. Most GIS can do this. For example, take a look at the tools in the Cost-Distance Analysis toolbox of Whitebox GAT. They are capable of finding an optimal route based on the spatial pattern of cost/benefit without having to check every possible route. They effectively use a steepest descent algorithm to do so.
    – user21951
    Sep 17 '13 at 17:04
  • I'll be working with a graph (road network) with weight assigned to each edge. I'm toying with a concept of an exercise application that will create a route from point A to point B that will cost X callories to go through. Assigning cost to the route based on it's length/terrain profile is relatively easy task but I'm trying to find out how to create a path thru the graph that will be closest to the desired cost. Sep 17 '13 at 18:54
  • Yes, this certainly sounds more like a network analysis type problem than a cost surface analysis problem. I'm sorry I couldn't be more helpful.
    – user21951
    Sep 17 '13 at 19:03

You could create a point C, halfway between A and B. Calculate cost from A-C and C-B. Depending upon how far it is from your desired cost, adjust location of C to either side and try again. And depending upon how accurate you want it and how complex your graph is, it could take quite some tries to get it correct.

  • That's quite crude but probably will be easiest to implement and therefore might be most effective. Sep 17 '13 at 18:56
  • It's effective but far too complicated computationally. Simpler ways are given in my comment to the question.
    – whuber
    Sep 17 '13 at 20:08
  • Asking "to wander around" isn't a serious response. You could as well have told him to take the fastest path and then slow down until the desired time matches. Sep 18 '13 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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