1

I have a raster with each cell representing a travel cost. I need to find the least cost path from one point on the raster to another point on the raster. One additional twist: the path cannot exceed 50% of the distance of the most direct route.

I'm using numpy and scikit for managing my graph, but I'm open to other solutions (except non-free software such as ArcGIS).

Example costs:

[ 2,  2,  2,  2,  2,
 10,  9,  2,  7,  2,
 11, 12, 13, 14,  2,
 20, 19, 18, 17,  2,
  2,  2,  2,  2,  2 ]

If I'm evaluating a route from the top left to the bottom left, the absolute least cost route follows the edges along the top, right, and bottom of the graph (total cost=26):

[ 1,  1,  1,  1,  1,
  0,  0,  0,  0,  1,
  0,  0,  0,  0,  1,
  0,  0,  0,  0,  1,
  1,  1,  1,  1,  1 ]

The shortest distance is 5 cells:

[ 1,  0,  0,  0,  0,
  1,  0,  0,  0,  0,
  1,  0,  0,  0,  0,
  1,  0,  0,  0,  0,
  1,  0,  0,  0,  0 ]

In this case, the absolute least cost path is too long (13 cells compared with 5). The answer I'm looking for would be:

[ 1,  1,  0,  0,  0,
  0,  0,  1,  0,  0,
  0,  1,  0,  0,  0,
  0,  0,  1,  0,  0,
  1,  1,  0,  0,  0 ]

Total cost: 40, total distance: 7 cells. This is the minimum cost within the allowable path distance (5 cells * 150% = 7.5 cells).

Are there packages that offer algorithms to solve this?

I don't see anything out of the box in scikit.

Short of calculating every possible shortest path, what is a good strategy for solving this problem?

  • Travel the shortest distance down and you'll get better solution than 46, 7. It will be 45, 5 – FelixIP Apr 23 '17 at 10:02
  • @FelixIP good catch. I tweaked the grid to make my solution the correct one at a cost of 40 and 7 cells. – spencerrecneps Apr 24 '17 at 0:35

Your Answer

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

Browse other questions tagged or ask your own question.